毒瘤题。找了一下午+晚上的BUG，才发现原来query_tree写的是a%p;
真的是一个教训
UPD：2019.6.18
#include<iostream> #include<cmath> #include<cstdio> #include<cstring> #include<queue> #define lson i*2,l,mid //这个是宏定义，用前面的lson替代后面的i*2,l,mid #define rson i*2+1,mid+1,r using namespace std; struct tree{ long long mul; //mul是乘的缩写，add是加，sum是求和 long long add; long long sum; int l,r; }t[400860]; int n,m,a[100860],p; void build_tree(int i,int l,int r) { t[i].l=l; //相乘的话必须是1，有大佬说l,r可以不定义，但是我码力不够 t[i].r=r; t[i].mul=1; t[i].sum=0; t[i].add=0; if(l==r) { t[i].sum=a[l]; return ; } int mid=(l+r)/2; build_tree(lson); build_tree(rson); t[i].sum=(t[i*2].sum+t[i*2+1].sum)%p; } void pushdown2(int i) //回溯也有坑，大佬说两个push_down可以合并，特别注意mul最后赋值为1，向下传递的时候不要忘了下面的add和mul { t[i*2].mul=t[i].mul*t[i*2].mul%p; t[i*2+1].mul=t[i].mul*t[i*2+1].mul%p; t[i*2].add=(t[i*2].add*t[i].mul+t[i].add)%p; t[i*2+1].add=(t[i*2+1].add*t[i].mul+t[i].add)%p; t[i*2].sum=(t[i].mul*t[i*2].sum+t[i].add*(t[i*2].r-t[i*2].l+1))%p; t[i*2+1].sum=(t[i].mul*t[i*2+1].sum+t[i].add*(t[i*2+1].r-t[i*2+1].l+1))%p; t[i].add=0; t[i].mul=1; } void pushdown(int i) { t[i*2].mul=t[i].mul*t[i*2].mul%p; t[i*2+1].mul=t[i*2+1].mul*t[i].mul%p; t[i*2].add=(t[i*2].add*t[i].mul+t[i].add)%p; t[i*2+1].add=(t[i*2+1].add*t[i].mul+t[i].add)%p; t[i*2].sum=(t[i].mul*t[i*2].sum+t[i].add*(t[i*2].r-t[i*2].l+1))%p; t[i*2+1].sum=(t[i].mul*t[i*2+1].sum+t[i].add*(t[i*2+1].r-t[i*2+1].l+1))%p; t[i].add=0; t[i].mul=1; } void mul_tree(int i,int l,int r,int x,int y,int a) { if(l>=x&&r<=y) { t[i].sum*=a%p; t[i].mul*=a%p; t[i].add*=a%p; return ; } pushdown(i); int mid=(l+r)/2; if(x<=mid) mul_tree(lson,x,y,a); if(y>mid) mul_tree(rson,x,y,a); t[i].sum=(t[i*2].sum+t[i*2+1].sum)%p; } void add_tree(int i,int l,int r,int x,int y,int a) { if(l>=x&&r<=y) { //t[i].mul*=a%p; t[i].add+=a%p; t[i].sum+=(t[i].r-t[i].l+1)*a%p; return ; } pushdown(i); int mid=(l+r)/2; if(x<=mid) add_tree(lson,x,y,a); if(y>mid) add_tree(rson,x,y,a); t[i].sum=(t[i*2].sum+t[i*2+1].sum)%p; } int query_tree(int i,int l,int r,int a,int b) { if(l>=a&&r<=b) //l,r包含在ab区间则这一段直接返回 { return t[i].sum%p; } int mid=(l+r)/2; long long ans=0; pushdown(i); if(a<=mid) ans+=query_tree(lson,a,b)%p; if(b>mid) ans+=query_tree(rson,a,b)%p; return ans%p; } int main() { scanf("%d %d %d",&n,&m,&p); int i,j; for(i=1;i<=n;i++) scanf("%d",&a[i]); build_tree(1,1,n); for(i=1;i<=m;i++) { int k; int t1,t2,t3; scanf("%d",&k); if(k==1) { scanf("%d %d %d",&t1,&t2,&t3); mul_tree(1,1,n,t1,t2,t3); //printf("%d \n",query_tree(1,1,n,t1,t2)%p); //听说过复制粘贴吧 } if(k==2) { scanf("%d %d %d",&t1,&t2,&t3); add_tree(1,1,n,t1,t2,t3); //printf("%d \n",query_tree(1,1,n,t1,t2)%p); } if(k==3) { scanf("%d %d",&t1,&t2); printf("%d \n",query_tree(1,1,n,t1,t2)%p); } } return 0; }