老坑了。
之前比较困然后没调出来，之前比较颓不想调毒瘤题。
做过类似的splay题，然后这题没啥好说的，开LL。
#include#include #include #include #include #include using namespace std;typedef long long LL;LL mod;struct node{ int l,r,lc,rc; LL sum; LL tipj,tipc;}tr[210000];int trlen;int a[110000];void bt(int l,int r){ int now=++trlen; tr[now].l=l;tr[now].r=r; if(l==r) { tr[now].lc=tr[now].rc=0; tr[now].sum=a[l]; tr[now].tipj=0;tr[now].tipc=1; } else { int mid=(l+r)/2; tr[now].lc=trlen+1;bt(l,mid); tr[now].rc=trlen+1;bt(mid+1,r); tr[now].sum=(tr[tr[now].lc].sum+tr[tr[now].rc].sum)%mod; tr[now].tipj=0;tr[now].tipc=1; }}void wh(int now){ int lc=tr[now].lc,rc=tr[now].rc; if(tr[now].tipc!=1) { tr[lc].sum=(tr[lc].sum*tr[now].tipc)%mod; tr[lc].tipj=(tr[lc].tipj*tr[now].tipc)%mod; tr[lc].tipc=(tr[lc].tipc*tr[now].tipc)%mod; tr[rc].sum=(tr[rc].sum*tr[now].tipc)%mod; tr[rc].tipj=(tr[rc].tipj*tr[now].tipc)%mod; tr[rc].tipc=(tr[rc].tipc*tr[now].tipc)%mod; tr[now].tipc=1; } if(tr[now].tipj!=0) { int L; L=tr[lc].r-tr[lc].l+1; tr[lc].sum=(tr[lc].sum+L*tr[now].tipj)%mod; tr[lc].tipj=(tr[lc].tipj+tr[now].tipj)%mod; L=tr[rc].r-tr[rc].l+1; tr[rc].sum=(tr[rc].sum+L*tr[now].tipj)%mod; tr[rc].tipj=(tr[rc].tipj+tr[now].tipj)%mod; tr[now].tipj=0; }}void mul(int now,int l,int r,LL k){ if(tr[now].l==l&&tr[now].r==r) { wh(now); tr[now].sum=(tr[now].sum*k)%mod; tr[now].tipj=(tr[now].tipj*k)%mod; tr[now].tipc=(tr[now].tipc*k)%mod; return ; } wh(now); int mid=(tr[now].l+tr[now].r)/2; int lc=tr[now].lc,rc=tr[now].rc; if(r<=mid) mul(lc,l,r,k); else if(mid+1<=l)mul(rc,l,r,k); else mul(lc,l,mid,k), mul(rc,mid+1,r,k); //jc tr[now].sum=(tr[lc].sum+tr[rc].sum)%mod;}void add(int now,int l,int r,LL k){ if(tr[now].l==l&&tr[now].r==r) { wh(now); int L=r-l+1; tr[now].sum=(tr[now].sum+L*k)%mod; tr[now].tipj=(tr[now].tipj+k)%mod; return ; } wh(now); int mid=(tr[now].l+tr[now].r)/2; int lc=tr[now].lc,rc=tr[now].rc; if(r<=mid) add(lc,l,r,k); else if(mid+1<=l)add(rc,l,r,k); else add(lc,l,mid,k), add(rc,mid+1,r,k); //jc tr[now].sum=(tr[lc].sum+tr[rc].sum)%mod;}LL getsum(int now,int l,int r){ if(tr[now].l==l&&tr[now].r==r)return tr[now].sum; wh(now); int mid=(tr[now].l+tr[now].r)/2; int lc=tr[now].lc,rc=tr[now].rc; if(r<=mid) return getsum(lc,l,r); else if(mid+1<=l)return getsum(rc,l,r); else return (getsum(lc,l,mid)+getsum(rc,mid+1,r))%mod;}int main(){ int n; scanf("%d%lld",&n,&mod); for(int i=1;i<=n;i++)scanf("%d",&a[i]); trlen=0;bt(1,n); int m,op,l,r;LL k; scanf("%d",&m); while(m--) { scanf("%d",&op); if(op==1) { scanf("%d%d%lld",&l,&r,&k); mul(1,l,r,k%mod); } else if(op==2) { scanf("%d%d%lld",&l,&r,&k); add(1,l,r,k%mod); } else { scanf("%d%d",&l,&r); printf("%lld\n",getsum(1,l,r)); } } return 0;}