题目传送门
也是写上 HDU 的题解了。
关于 HDU 的杂谈
因为杭电的 OJ 只有一个测试点，所以有些题搬过来的时候改成多测，题目里有没有文字说明。
还有更坑人的：HDU 4027 Can you answer these queries?，区间 $[x,y]$，不保证 $x<y$。
题意分析
需要实现操作：区间赋值、区间乘、区间加，查区间一次、二次、三次和。
乘法优先于加法是简单的，也不难想到赋值优先于乘法。因此分别打三个标记 set、mul、add。
下方懒标记的时候顺序下方，修改 set 时清空 mul、add，修改 mul 时修改 add 即可。
还需要维护对应的 sum[1]、sum[2]、sum[3] 分别表示一次、二次、三次和。
赋值、乘法修改是简单的，主要考虑加法操作：设将 \(a_1,a_2,\cdots,a_n\) 加 \(x\)。
则有：
\[\begin{aligned}
\sum_{i=1}^n(a_i+x)^3&=\sum_{i=1}^n\left(a_i^3+3a_i^2x+3a_ix^2+x^3\right)\\
&=\sum_{i=1}^na_i^3+3x\sum_{i=1}^na_i^2+3x^2\sum_{i=1}^na_i+nx^3\\
\sum_{i=1}^n(a_i+x)^2&=\sum_{i=1}^n\left(a_i^2+2a_ix+x^2\right)\\
&=\sum_{i=1}^na_i^2+2x\sum_{i=1}^na_i+nx^2\\
\sum_{i=1}^n(a_i+x)&=\sum_{i=1}^na_i+nx
\end{aligned}
\]
更新即顺序进行：
\[\begin{aligned}
\textit{sum}_3&\leftarrow\textit{sum}_3+3x\cdot\textit{sum}_2+3x^2\cdot\textit{sum}_1+nx^3\\
\textit{sum}_2&\leftarrow\textit{sum}_2+2x\cdot\textit{sum}_1+nx^2\\
\textit{sum}_1&\leftarrow\textit{sum}_1+nx
\end{aligned}
\]
AC 代码
//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
using namespace std;
constexpr const int N=1e5,P=10007;
struct segTree{struct node{int l,r;int sum[4];int add,mul,set;int size(){return r-l+1;}}t[N<<2|1];void up(int p){t[p].sum[1]=(t[p<<1].sum[1]+t[p<<1|1].sum[1])%P;t[p].sum[2]=(t[p<<1].sum[2]+t[p<<1|1].sum[2])%P;t[p].sum[3]=(t[p<<1].sum[3]+t[p<<1|1].sum[3])%P;}void build(int p,int l,int r){t[p]={l,r};t[p].mul=1;if(l==r){return;}int mid=l+r>>1;build(p<<1,l,mid);build(p<<1|1,mid+1,r);up(p); }void down(int p){if(t[p].set){ t[p<<1].set=t[p].set;t[p<<1].add=0,t[p<<1].mul=1;t[p<<1].sum[1]=t[p<<1].size()*t[p].set%P;t[p<<1].sum[2]=t[p<<1].sum[1]*t[p].set%P;t[p<<1].sum[3]=t[p<<1].sum[2]*t[p].set%P;t[p<<1|1].set=t[p].set;t[p<<1|1].add=0,t[p<<1|1].mul=1;t[p<<1|1].sum[1]=t[p<<1|1].size()*t[p].set%P;t[p<<1|1].sum[2]=t[p<<1|1].sum[1]*t[p].set%P;t[p<<1|1].sum[3]=t[p<<1|1].sum[2]*t[p].set%P;t[p].set=0;}if(t[p].mul!=1){t[p<<1].mul=t[p<<1].mul*t[p].mul%P;t[p<<1].add=t[p<<1].add*t[p].mul%P;t[p<<1].sum[1]=t[p<<1].sum[1]*t[p].mul%P;t[p<<1].sum[2]=t[p<<1].sum[2]*t[p].mul%P*t[p].mul%P;t[p<<1].sum[3]=t[p<<1].sum[3]*t[p].mul%P*t[p].mul%P*t[p].mul%P;t[p<<1|1].mul=t[p<<1|1].mul*t[p].mul%P;t[p<<1|1].add=t[p<<1|1].add*t[p].mul%P;t[p<<1|1].sum[1]=t[p<<1|1].sum[1]*t[p].mul%P;t[p<<1|1].sum[2]=t[p<<1|1].sum[2]*t[p].mul%P*t[p].mul%P;t[p<<1|1].sum[3]=t[p<<1|1].sum[3]*t[p].mul%P*t[p].mul%P*t[p].mul%P;t[p].mul=1;}if(t[p].add){int &x=t[p].add;t[p<<1].add=(t[p<<1].add+x)%P;t[p<<1].sum[3]=(t[p<<1].sum[3]+3*t[p<<1].sum[2]*x%P+3*t[p<<1].sum[1]*x%P*x%P+t[p<<1].size()*x%P*x%P*x%P)%P;t[p<<1].sum[2]=(t[p<<1].sum[2]+2*t[p<<1].sum[1]*x%P+t[p<<1].size()*x%P*x%P)%P;t[p<<1].sum[1]=(t[p<<1].sum[1]+t[p<<1].size()*x)%P; t[p<<1|1].add=(t[p<<1|1].add+x)%P;t[p<<1|1].sum[3]=(t[p<<1|1].sum[3]+3*t[p<<1|1].sum[2]*x%P+3*t[p<<1|1].sum[1]*x%P*x%P+t[p<<1|1].size()*x%P*x%P*x%P)%P;t[p<<1|1].sum[2]=(t[p<<1|1].sum[2]+2*t[p<<1|1].sum[1]*x%P+t[p<<1|1].size()*x%P*x%P)%P;t[p<<1|1].sum[1]=(t[p<<1|1].sum[1]+t[p<<1|1].size()*x)%P;t[p].add=0;}}void add(int p,int l,int r,int x){if(l<=t[p].l&&t[p].r<=r){t[p].add=(t[p].add+x)%P;t[p].sum[3]=(t[p].sum[3]+3*t[p].sum[2]*x%P+3*t[p].sum[1]*x%P*x%P+t[p].size()*x%P*x%P*x%P)%P;t[p].sum[2]=(t[p].sum[2]+2*t[p].sum[1]*x%P+t[p].size()*x%P*x%P)%P;t[p].sum[1]=(t[p].sum[1]+t[p].size()*x)%P;return;}down(p);if(l<=t[p<<1].r){add(p<<1,l,r,x);}if(t[p<<1|1].l<=r){add(p<<1|1,l,r,x);}up(p);}void mul(int p,int l,int r,int x){if(l<=t[p].l&&t[p].r<=r){t[p].mul=t[p].mul*x%P;t[p].add=t[p].add*x%P;t[p].sum[1]=t[p].sum[1]*x%P;t[p].sum[2]=t[p].sum[2]*x%P*x%P;t[p].sum[3]=t[p].sum[3]*x%P*x%P*x%P;return;}down(p);if(l<=t[p<<1].r){mul(p<<1,l,r,x);}if(t[p<<1|1].l<=r){mul(p<<1|1,l,r,x);}up(p);}void set(int p,int l,int r,int x){if(l<=t[p].l&&t[p].r<=r){t[p].add=0,t[p].mul=1;t[p].set=x;t[p].sum[1]=t[p].size()*t[p].set%P;t[p].sum[2]=t[p].sum[1]*t[p].set%P;t[p].sum[3]=t[p].sum[2]*t[p].set%P;return;}down(p);if(l<=t[p<<1].r){set(p<<1,l,r,x);}if(t[p<<1|1].l<=r){set(p<<1|1,l,r,x);}up(p);}int query(int p,int l,int r,int x){if(l<=t[p].l&&t[p].r<=r){return t[p].sum[x];}down(p);int ans=0;if(l<=t[p<<1].r){ans+=query(p<<1,l,r,x);}if(t[p<<1|1].l<=r){ans+=query(p<<1|1,l,r,x);}return ans%P;}
}t;
main(){/*freopen("test.in","r",stdin);freopen("test.out","w",stdout);*/ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int n,m;while(true){cin>>n>>m;if(!n&&!m){break;}t.build(1,1,n);while(m--){int op,l,r,x;cin>>op>>l>>r>>x;switch(op){case 1:t.add(1,l,r,x);break;case 2:t.mul(1,l,r,x);break;case 3:t.set(1,l,r,x);break;case 4:cout<<t.query(1,l,r,x)<<'\n'; break;}}}cout.flush();/*fclose(stdin);fclose(stdout);*/return 0;
}
/*
5 3
3 3 5 7
1 2 4 4
4 1 5 2
0 0307
*/