一些函数复合问题
绝对值差
考虑有这样一个序列$x_1,x_2,\ldots x_n$，其中每个整数都不超过$10^6$，用这个数列可以唯一确定一个函数$f$，其接受一个参数$x_0$，这个函数会输出： \(|\ldots|||x_0-x_1|-x_2|-x_3|\ldots-x_n|\)
其代码大概为：
f(x0){
ans = x0;
for(int i = 1; i <= n; i++){
ans = |ans - a[i]|;
}
return ans;
}
现在我们有$m$个参数$a_1,a_2,\ldots,a_m$，其中$0\leq a_i\leq 10^6$，希望计算这$m$个输入下$f$的对应输出$f(a_1),f(a_2),\ldots, f(a_m)$。
其中$n,m \leq 10^6$。
很显然，我们可以在时间复杂度$O(nm)$内解决，但是会花掉过多的时间。
我们可以定义另外$n$个函数$f_1,f_2,\ldots, f_n$，其中$f_k$表示由序列后$k$个元素确定的函数，其代码应该为：
fk(x0){
ans = x0;
for(int i = n - k + 1; i <= n; i++){
ans = |ans - a[i]|;
}
return ans;
}
可以发现这$n$个函数之间具有递推关系：
\[f_i(j)=f_{i-1}(|a[n-i+1]-j|)\]我们可以将函数用一个数组表示，数组下标为i的元素的值表示输入为i时的输出。
我们自然地定义函数$f_{0}(x)=x$，因此$f_{0}$函数的数组表示为：
[0,1,2,3,4,...,n]
之后考虑函数$f_1$，其数组表示为：
[a[n],a[n]-1,a[n]-2, ..., 1, 0, 1, 2, ..., n - a[n]]
可以发现$f_1$实际上是将$f_0$的某段前缀翻转并放在了最前面，并删除部分的后缀。
同理我们可以推广出$f_i$到$f_{i+1}$的数组形式的变换。
接下来我们考虑如何快速计算出$f_1,f_2,\ldots, f_n$，我们可以递推处理，这里翻转拼接都可以用持久化平衡树（比如treap）来实现。
而$f=f_n$，因此我们也得到了$f$的数组表示，之后的m个请求可以$O(1)$高效处理。总的时间和空间复杂度为$O(n\log_2n+m)$。
阈值递增
给定$n$个整数$x_1,\ldots,x_n$。之后给定一个函数$f$，它的逻辑大概为：
f(a){
for(int i = 1; i <= n; i++){
if(a >= x[i]){
a = a + 1;
}
}
return a;
}
现在给定$m$，要求计算$f(0),\ldots,f(m)$，其中$0\leq a_i\leq m$。
其中$1\leq n,m\leq 10^6$。
记$f_i$表示仅考虑$x_1,\ldots,x_i$得到的函数。现在我们考虑如何得到$f_{i+1}$。如果我们把$f_i$和$f_{i+1}$看作是长度为$m+1$的向量，那么可以发现$f_i$是单调递增的向量。而$a_{i+1}$带来的影响是将$f_i$中所有大于等于$a_{i+1}$的元素，全部增加$1$，而这部分元素正好对应$f_i$的某个后缀。
我们可以用线段树维护$f_i$，之后在线段树上二分找到需要自增的后缀，之后一次区间增加$1$即可得到$f_{i+1}$，所有操作都是$O(\log_2m)$。
因此我们可以$O(n\log_2m+m)$得到$f_n$并回答所有的查询。