牛客练习赛28 B-数据结构

线段数模版问题，拿走不谢 ```cpp #include<bits/stdc++.h> #define LL long long #define L(x) x<<1 //左儿子 x*2 #define R(x) x<<1|1 //右儿子 x*2+1 const int maxn =1e5+5; using namespace std; LL n,m,num[maxn]; LL mod; //膜数 inline LL read() { LL x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') f=(ch=='-')?-1:1,ch=getchar(); while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar(); return x*f; } struct T { LL l,r; LL sum,add,mul; } tree[maxn<<2];//注意开long long 和四倍空间 inline void update(LL p) { tree[p].sum=(tree[L(p)].sum+tree[R(p)].sum)%mod; return; } inline void spread(LL p) { LL mid=(tree[p].l+tree[p].r)>>1; if(tree[p].mul!=1) { tree[L(p)].mul=(tree[L(p)].mul*tree[p].mul)%mod; tree[R(p)].mul=(tree[R(p)].mul*tree[p].mul)%mod; tree[L(p)].add=(tree[L(p)].add*tree[p].mul)%mod; tree[R(p)].add=(tree[R(p)].add*tree[p].mul)%mod; tree[L(p)].sum=(tree[L(p)].sum*tree[p].mul)%mod; tree[R(p)].sum=(tree[R(p)].sum*tree[p].mul)%mod; tree[p].mul=1; } if(tree[p].add) { tree[L(p)].add=(tree[L(p)].add+tree[p].add)%mod; tree[R(p)].add=(tree[R(p)].add+tree[p].add)%mod; tree[L(p)].sum=(tree[L(p)].sum+tree[p].add*(mid-tree[p].l+1))%mod; tree[R(p)].sum=(tree[R(p)].sum+tree[p].add*(tree[p].r-mid))%mod;//tree[p].r-mid不加1 tree[p].add=0; } return; } inline void build(LL l,LL r,LL p) {//建树 tree[p].l=l,tree[p].r=r,tree[p].mul=1; if(l==r) { tree[p].sum=num[l]; tree[p].mul=1; return; } LL mid=(tree[p].l+tree[p].r)>>1; build(l,mid,L(p)); build(mid+1,r,R(p)); update(p); return; } inline void change1(LL l,LL r,LL p,LL v) {//区间增值 if(tree[p].l==l&&tree[p].r==r) { tree[p].add=(tree[p].add+v)%mod; tree[p].sum=(tree[p].sum+v*(r-l+1))%mod; return; } spread(p); LL mid=(tree[p].l+tree[p].r)>>1; if(r<=mid) change1(l,r,L(p),v); else if(l>mid) change1(l,r,R(p),v); else change1(l,mid,L(p),v),change1(mid+1,r,R(p),v); update(p); return; } inline void change2(LL l,LL r,LL p,LL v) {//区间乘法 if(tree[p].l==l&&tree[p].r==r) { tree[p].mul=(tree[p].mul*v)%mod; tree[p].sum=(tree[p].sum*v)%mod; tree[p].add=(tree[p].add*v)%mod; return; } spread(p); LL mid=(tree[p].l+tree[p].r)>>1; if(r<=mid) change2(l,r,L(p),v); else if(l>mid) change2(l,r,R(p),v); else change2(l,mid,L(p),v),change2(mid+1,r,R(p),v); update(p); return; } inline LL ask_sum1(LL l,LL r,LL p) {//区间和 if(tree[p].l==l&&tree[p].r==r) { return tree[p].sum%mod; } spread(p); LL mid=(tree[p].l+tree[p].r)>>1; if(r<=mid) return ask_sum1(l,r,L(p))%mod; else if(l>mid) return ask_sum1(l,r,R(p))%mod; else return (ask_sum1(l,mid,L(p))%mod+ask_sum1(mid+1,r,R(p))%mod)%mod; } inline LL ask_sum2(LL l,LL r,LL p) {//区间平方和 if(tree[p].l==tree[p].r) { return tree[p].sum*tree[p].sum; } spread(p); LL mid=(tree[p].l+tree[p].r)>>1; if(r<=mid) return ask_sum2(l,r,L(p)); else if(l>mid) return ask_sum2(l,r,R(p)); else return ask_sum2(l,mid,L(p))+ask_sum2(mid+1,r,R(p)); } LL opt,l,r,v; int main() { n=read(),m=read(); mod=read(); for(int i=1; i<=n; i++) num[i]=read(); build(1,n,1); while(m--) { opt=read(); if(opt==3) { l=read(),r=read(); printf("%lld\n",ask_sum1(l,r,1)%mod);//询问区间和 } if(opt==4) { l=read(),r=read(); printf("%lld\n",ask_sum2(l,r,1)%mod);//询问区间平方和 } if(opt==1) { l=read(),r=read(),v=read(); change2(l,r,1,v);//区间乘 } if(opt==2) { l=read(),r=read(),v=read(); change1(l,r,1,v);//区间加 } } return 0; } ```