正确率刷到了46%
真是蛋疼
这不是一道线段树的模板题吗
把(x+add)*val化开，变成x*val+add*val
然后直接处理就可以了
下面是代码，cin/out RE，改成printf,scanf就AC了
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define maxn 100010 #define lc id<<1 #define rc id<<1|1 using namespace std; typedef long long ll; int n,opt,a[maxn]; ll m; struct Node{ int l,r; ll s,m,a; }t[maxn<<3]; void pushdown(int id){ int l=t[id].l,r=t[id].r,mid=l+r>>1; t[lc].s=(t[lc].s*t[id].m+t[id].a*(mid-l+1))%m; t[rc].s=(t[rc].s*t[id].m+t[id].a*(r-mid))%m; t[lc].m=t[lc].m*t[id].m%m; t[rc].m=t[rc].m*t[id].m%m; t[lc].a=(t[lc].a*t[id].m+t[id].a)%m; t[rc].a=(t[rc].a*t[id].m+t[id].a)%m; t[id].m=1,t[id].a=0; } void pushup(int id){ t[id].s=(t[lc].s+t[rc].s)%m; } void build(int id,int l,int r){ t[id].l=l,t[id].r=r; t[id].m=1,t[id].a=0; if(l==r){ t[id].s=a[l]%m; return; } int mid=l+r>>1; build(lc,l,mid);build(rc,mid+1,r); pushup(id); } ll ask(int id,int l,int r){ pushdown(id); if(t[id].l==l&&t[id].r==r){ return t[id].s; } int mid=t[id].l+t[id].r>>1; if(r<=mid){ return ask(lc,l,r); } if(l>mid){ return ask(rc,l,r); } return(ask(lc,l,mid)+ask(rc,mid+1,r))%m; } void Mul(int id,int l,int r,int c){ pushdown(id); if(t[id].l==l&&t[id].r==r){ t[id].m=t[id].m*c%m; t[id].s=t[id].s*c%m; return; } int mid=t[id].l+t[id].r>>1; if(r<=mid){ Mul(lc,l,r,c); } else if(l>mid){ Mul(rc,l,r,c); }else{ Mul(lc,l,mid,c);Mul(rc,mid+1,r,c); } pushup(id); } void Plus(int id,int l,int r,int c){ pushdown(id); if(t[id].l==l&&t[id].r==r){ t[id].a+=c; t[id].a%=m; t[id].s+=1ll*(r-l+1)*c; t[id].s%=m; return; } int mid=t[id].l+t[id].r>>1; if(r<=mid){ Plus(lc,l,r,c); }else if(l>mid){ Plus(rc,l,r,c); }else{ Plus(lc,l,mid,c); Plus(rc,mid+1,r,c); } pushup(id); } int main(){ scanf("%d%lld",&n,&m); for(int i=1;i<=n;i++){ cin>>a[i]; } build(1,1,n); scanf("%d",&opt); int type,l,r,c; for(int i=1;i<=opt;i++){ scanf("%d",&type); if(type==3){ scanf("%d%d",&l,&r); printf("%lld\n",ask(1,l,r)%m); continue; } scanf("%d%d%d",&l,&r,&c); if(type==1){ Mul(1,l,r,c); }else{ Plus(1,l,r,c); } } return 0; } /* in: 7 43 1 2 3 4 5 6 7 5 1 2 5 5 3 2 4 2 3 7 9 3 1 3 3 4 7 Sample Output 2 35 8 */