传送门
前天看到这道题觉得线段树水过，准备敲一敲分块。然后就没有然后了wa了十发。今天看到就顺手水了水。。最近被拓展lucas和ahoi2017玩废，我恐怕就是一只咸鱼了。。
注意标记下传要加法标记要先乘再加，然后就没什么了。
代码：
#include<iostream> #include<stdio.h> #define ll long long using namespace std; const int Maxn=100005; struct node { ll l,r,sum,tag_1,tag_2; }tree[Maxn*4]; ll n,p; void build(ll l,ll r,ll rt) { tree[rt].l=l; tree[rt].r=r; tree[rt].tag_1=1; if(l==r) { scanf("%lld",&tree[rt].sum); return ; } ll mid=(l+r)>>1; build(l,mid,rt<<1); build(mid+1,r,rt<<1|1); tree[rt].sum=(tree[rt<<1].sum+tree[rt<<1|1].sum)%p; } void pushdown(ll rt) { if(tree[rt].tag_1==1&&tree[rt].tag_2==0) return ; ll l=tree[rt].l,r=tree[rt].r,mid=(tree[rt].l+tree[rt].r)>>1; tree[rt<<1].tag_1=(tree[rt<<1].tag_1*tree[rt].tag_1)%p; tree[rt<<1].tag_2=(tree[rt<<1].tag_2*tree[rt].tag_1%p+tree[rt].tag_2)%p; tree[rt<<1].sum=(tree[rt<<1].sum*tree[rt].tag_1%p+tree[rt].tag_2*(mid-l+1))%p; tree[rt<<1|1].tag_1=(tree[rt<<1|1].tag_1*tree[rt].tag_1)%p; tree[rt<<1|1].tag_2=(tree[rt<<1|1].tag_2*tree[rt].tag_1%p+tree[rt].tag_2)%p; tree[rt<<1|1].sum=(tree[rt<<1|1].sum*tree[rt].tag_1%p+tree[rt].tag_2*(r-mid))%p; tree[rt].tag_1=1; tree[rt].tag_2=0; } void Mulity(ll l,ll r,ll lf,ll rf,ll rt,ll c) { if(lf<=l&&rf>=r) { tree[rt].tag_2=tree[rt].tag_2*c%p; tree[rt].tag_1=tree[rt].tag_1*c%p; tree[rt].sum=tree[rt].sum*c%p; return ; } pushdown(rt); ll mid=(l+r)>>1; if(lf<=mid)Mulity(l,mid,lf,rf,rt<<1,c); if(rf>mid)Mulity(mid+1,r,lf,rf,rt<<1|1,c); tree[rt].sum=(tree[rt<<1].sum+tree[rt<<1|1].sum)%p; } void Add(ll l,ll r,ll lf,ll rf,ll rt,ll c) { if(lf<=l&&rf>=r) { tree[rt].tag_2=(tree[rt].tag_2+c)%p; tree[rt].sum=(tree[rt].sum+(r-l+1)*c)%p; return ; } pushdown(rt); ll mid=(l+r)>>1; if(lf<=mid)Add(l,mid,lf,rf,rt<<1,c); if(rf>mid)Add(mid+1,r,lf,rf,rt<<1|1,c); tree[rt].sum=(tree[rt<<1].sum+tree[rt<<1|1].sum)%p; } ll query(ll l,ll r,ll lf,ll rf,ll rt) { if(lf<=l&&rf>=r) return tree[rt].sum%p; pushdown(rt); ll mid=(l+r)>>1; ll ans=0; if(lf<=mid)ans=(ans+query(l,mid,lf,rf,rt<<1)%p)%p; if(rf>mid)ans=(ans+query(mid+1,r,lf,rf,rt<<1|1)%p)%p; tree[rt].sum=(tree[rt<<1].sum+tree[rt<<1|1].sum)%p; return ans%p; } int main() { scanf("%lld%lld",&n,&p); build(1,n,1); ll m,opt; scanf("%lld",&m); for(int i=1;i<=m;i++) { ll l,r,c; scanf("%lld",&opt); if(opt==1) { scanf("%lld%lld%lld",&l,&r,&c); Mulity(1,n,l,r,1,c); } if(opt==2) { scanf("%lld%lld%lld",&l,&r,&c); Add(1,n,l,r,1,c); } if(opt==3) { scanf("%lld%lld",&l,&r); printf("%lld\n",query(1,n,l,r,1)); } } return 0; }