题目描述
给出一个长为 nnn 的数列，以及 nnn 个操作，操作涉及区间乘法，区间加法，单点询问。
输入格式
第一行输入一个数字 nnn。
第二行输入 nnn 个数字，第 i 个数字为 aia_iai，以空格隔开。
接下来输入 nnn 行询问，每行输入四个数字 opt\mathrm{opt}opt、lll、rrr、ccc，以空格隔开。
若 opt=0\mathrm{opt} = 0opt=0，表示将位于 [l,r][l, r][l,r] 的之间的数字都加 ccc。
若 opt=1\mathrm{opt} = 1opt=1，表示将位于 [l,r][l, r][l,r] 的之间的数字都乘 ccc。
若 opt=2\mathrm{opt} = 2opt=2，表示询问 ara_rar 的值 mod 10007mod \ 10007mod 10007（lll 和 ccc 忽略）。
输出格式
对于每次询问，输出一行一个数字表示答案。
样例
样例输入
71 2 2 3 9 3 20 1 3 12 1 3 11 1 4 40 1 7 21 2 6 41 1 6 52 2 6 4
样例输出
3100
数据范围与提示
对于 100% 100\%100% 的数据，1≤n≤100000,−231≤others 1 \leq n \leq 100000, -2^{31} \leq \mathrm{others}1≤n≤100000,−231≤others、ans≤231−1 \mathrm{ans} \leq 2^{31}-1ans≤231−1。
思路： 把加法和乘法都看成 x*a+b，乘法的时候b是0，加法的时候a是1
1 #include2 using namespace std; 3 4 #define F(i,a,b) for(int i=a;i<=b;i++) 5 #define D(i,a,b) for(int i=a;i>=b;i--) 6 #define ms(i,a) memset(a,i,sizeof(a)) 7 #define LL long long 8 #define st(x) ((x-1)*B+1) 9 #define ed(x) min(x*B,n)10 #define bl(x) ((x-1)/B+1) 11 12 int inline read(){13 int x=0,w=0; char c=getchar(); 14 while (c<'0' || c>'9') w+=c=='-',c=getchar(); 15 while (c>='0' && c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar(); 16 return w? -x: x; 17 }18 19 int const maxn=100003; 20 int const mod=10007; 21 22 int n,B;23 LL add[350],mul[350],a[maxn]; 24 25 void update(int l,int r,int M,int A){26 int x=bl(l); 27 int y=bl(r); 28 if(x==y){29 F(i,st(x),ed(x)) a[i]=(a[i]*mul[x]+add[x]) % mod; 30 F(i,l,r) a[i]=(a[i]*M+A) % mod; 31 mul[x]=1; add[x]=0; 32 }else {33 F(i,st(x),ed(x)) a[i]=(a[i]*mul[x]+add[x]) % mod; 34 F(i,st(y),ed(y)) a[i]=(a[i]*mul[y]+add[y]) % mod; 35 F(i,l,ed(x)) a[i]=(a[i]*M+A) % mod; 36 F(i,st(y),r) a[i]=(a[i]*M+A) % mod; 37 mul[x]=mul[y]=1; add[x]=add[y]=0; 38 F(i,x+1,y-1) mul[i]=(mul[i]*M)% mod,add[i]=(add[i]*M+A) % mod; 39 }40 }41 42 int query(int k){43 int x=bl(k); 44 F(i,st(x),ed(x)) a[i]=(a[i]*mul[x]+add[x]) % mod;45 mul[x]=1; add[x]=0; 46 return a[k]; 47 }48 49 int main(){50 n=read(); 51 B=(int) sqrt(n); 52 F(i,1,n) a[i]=read()% mod; 53 F(i,1,bl(n)) mul[i]=1; 54 F(i,1,n){55 int x=read(); 56 int l=read(); 57 int r=read(); 58 int c=read(); 59 if(x==0) update(l,r,1,c); 60 else if(x==1) update(l,r,c,0); 61 else printf("%d\n",query(r)); 62 }63 return 0; 64 }