智乃酱的静态数组维护问题多项式

差分维护多项式前缀和

前置知识

定理：最高次项为ｎ次的多项式做ｎ＋１次差分的余项为常数

题目最多为5次，所以做6次差分就够了。 如果次数小于6次，每多做一次差分增加一项余项，余项还是不超过6（可以直接去打印出来试试看）

现在开始解题

题目要求修改区间 $$l\sim r$$
实际上是给这个区间各个位置加上对应的多项式函数$$0，\cdots ，f(x_1),f(x_2),\cdots ,f(x_i),\cdots ,f(x_{r-l+1})$$
这样的时间复杂度是o(n)的，这个时候可以利用上面的那个定理，对原数组和多项式分别做6次差分再把他转换成修改区间
$$l\sim l+5$$
因为差分和前缀和是两个逆过程，原数组求差分可以得到差分数组，差分数组求前缀和可以得到原数组，差分数组和原数组可以相互转换。 所以可以把对原数组的区间修改转换为对差分数组的修改,修改结束后再把差分数组做对应次数的前缀和转换为原数组即可

题目的多项式最高次数只有5，对多项式的$$1\sim r-l+1$$做6次差分，就能保证余项一定在前6项，后面的项就都是0，对结果不影响，所以你只要把多项式6次差分得到的前6项修改到原数组的6次差分数组的前6项即可，这样时间复杂度就是O(1)




细说一下：你把区间$$l\sim r$$ 各自加上一个多项式 $$f(i),iϵ\left[1,r-l+1\right]$$
可以转换为先对多项式求6次差分，然后转换为对差分数组(做了6次差分后的原数组）的$$l\sim l+5$$ 进行修改。
然后若干次修改后，再做6次前缀和把差分数组还原成原数组即可。

重点来了

因为差分，所以要考虑对$$r+1\sim n$$ 的影响，所以要做一个抵消操作。

如何抵消？

假设现在对 $$l\sim r$$的区间，我们只做了对差分数组的
$$l\sim l+5$$的修改操作（假设原数组全0），这样直接做6次前缀和得到的结果为
$$0，\cdots ，f(x_1),f(x_2),\cdots ,f(x_i),\cdots ,f(x_{r-l+1}),f(x_{r-l+2}),\cdots ,f(x_{r-l+j}),\cdots ,f(x_{n-l+1})$$

多加了
$$f(x_{r-l+2}),\cdots ,f(x_{r-l+j}),\cdots ,f(x_{n-l+1})$$

如何抵消？我们给
$$r+1\sim n$$区间也做一次修改减去这些对应的项就行，也就是相当于对
$$r+1\sim n$$减去$$f(x_{r-l+2}),\cdots ,f(x_{r-l+j}),\cdots ,f(x_{n-l+1})$$

这个时间复杂度也是O(n）的，如何降低？很简单用同样方法就行！

你可以把这个修改也转换成做了6次差分后的修改。变成对做了6次差分后的原数组的
$$r+1\sim r+6$$ 减去做过6次差分后
的
$$f(x_{r-l+2}),\cdots ,f(x_{r-l+j}),\cdots ,f(x_{n-l+1})$$
即可。

因为这个是直接从r + 1做到n（末尾），已经没有剩余的区间受到影响了，所以直接做就行。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 20;
typedef long long ll;
const ll mod = 1e9 + 7;
ll a[N];
ll ceo1[12];
ll ceo2[12];
ll xishu[10];ll M(ll x,ll y){//取模return ( (x + y) % mod + mod ) %mod;
}void D(ll d[],int len, int ct){// 对长度为 len 的 d 数组求 ct 次差分while(ct--){for(int i = len; i ; --i)d[i] = M(d[i], - d[i-1]);}
}
void F(ll d[],int len, int ct){//对长度为 len 的 d 数组求 ct 次前缀和while(ct--){for(int i = 2; i <= len; ++i)d[i] = M(d[i], d[i-1]);}
}ll G(ll x,ll k){//求最高次项为 k 的 f(x)ll res = 0,base = 1;for(int i = 0; i <= k; ++i){res = M(res , base * xishu[i] % mod);base = base * x % mod;}return res;
}void get(ll d[], int l, int k, ll f){// 求得要修改的l ~ r的 前6项(l ,l + 1, …… l + 5)for(int i = 1; i <= 6; ++i){d[i] = f * G(l + i - 1,k);}
}int main(){//freopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);int n,m,q;  cin >> n >> m >> q;for(int i = 1; i <= n; ++i)cin >> a[i];D(a,n,6);while(m--) {int l,r,k;  cin >> l >> r >> k;for(int i = 0; i <= k; ++i)//输入系数cin >> xishu[k - i];get(ceo1, 1, k, 1);//获取 l ~ l + 5 对原数组的修改get(ceo2, r - l + 2, k, -1);//获取 r + 1 ~ n 对原数组的修改D(ceo1,6,6);// 将 l ~ l + 5 对原数组的修改求6次差分D(ceo2,6,6);// 将 r + 1 ~ n 对原数组的修改求6次差分for(int i = 1; i <= 6; ++i)//更新对差分数组的修改{a[i + l - 1] = M(a[i + l - 1],ceo1[i]);a[r + i] = M(a[r + i], ceo2[i]);}}F(a, n, 7);//做 6 + 1次前缀和，因为要求 l ~ r的区间和，所以多做一次前缀和while(q--) {int l,r;    cin >> l >> r;cout << M(a[r], -a[l - 1] ) << endl;}return 0;
}