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