https://acm.uestc.edu.cn/problem/fang-chai/description
聪明的做法
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int MAXN = 100005; const ll mod = 1e9+7; int n, m; struct Tree{ ll sum, fsum, add, mul, st; }T[MAXN<<2]; inline void add(ll &a, const ll &b){ a += b; if(a >= mod) a -= mod; } inline ll addto(const ll &a, const ll &b){ return a+b>=mod?a+b-mod:a+b; } #define mid ((l+r)>>1) inline void pushup(int u,int l,int r){ T[u].sum = addto(T[u<<1].sum, T[u<<1|1].sum); T[u].fsum = addto(T[u<<1].fsum, T[u<<1|1].fsum); } void build(int u,int l,int r){ T[u].add = 0, T[u].mul = 1, T[u].st = -1; if(l == r){ scanf("%lld", &T[u].sum); T[u].fsum = T[u].sum*T[u].sum%mod; return; } build(u<<1, l, mid); build(u<<1|1, mid+1, r); pushup(u,l,r); } inline void setupdate(int u,int l,int r,ll st){ T[u].st = st, T[u].add = 0ll, T[u].mul = 1ll; T[u].sum = T[u].st*(r-l+1)%mod; T[u].fsum = T[u].st*T[u].st%mod*(r-l+1)%mod; } inline void update(int u,int l,int r,ll k,ll b){ T[u].fsum = (k*k%mod*T[u].fsum%mod + 2ll*k*b%mod*T[u].sum%mod + b*b%mod*(r-l+1)%mod)%mod; T[u].sum = (T[u].sum*k + b*(r-l+1))%mod; T[u].add = (T[u].add*k + b)%mod; T[u].mul = (T[u].mul*k)%mod; } inline void pushdown(int u,int l,int r){ if(T[u].st != -1){ setupdate(u<<1,l,mid,T[u].st); setupdate(u<<1|1,mid+1,r,T[u].st); T[u].st = -1; } if(T[u].mul != 1ll || T[u].add != 0ll){ update(u<<1,l,mid,T[u].mul,T[u].add); update(u<<1|1,mid+1,r,T[u].mul,T[u].add); T[u].mul = 1ll, T[u].add = 0ll; } } void changeadd(int u,int l,int r,int L,int R,int x){ if(L<=l&&r<=R){ add(T[u].add, x); T[u].fsum = (T[u].fsum + 2ll*x*T[u].sum%mod + 1ll*x*x%mod*(r-l+1)%mod)%mod; T[u].sum = (T[u].sum + 1ll*x*(r-l+1))%mod; return; } pushdown(u,l,r); if(L<=mid)changeadd(u<<1,l,mid,L,R,x); if(R>mid)changeadd(u<<1|1,mid+1,r,L,R,x); pushup(u,l,r); } void changemul(int u,int l,int r,int L,int R,int x){ if(L<=l&&r<=R){ T[u].add = T[u].add*x%mod; T[u].mul = T[u].mul*x%mod; T[u].fsum = T[u].fsum*x%mod*x%mod; T[u].sum = T[u].sum*x%mod; return; } pushdown(u,l,r); if(L<=mid)changemul(u<<1,l,mid,L,R,x); if(R>mid)changemul(u<<1|1,mid+1,r,L,R,x); pushup(u,l,r); } void changeset(int u,int l,int r,int L,int R,int x){ if(L<=l&&r<=R){ T[u].st = x, T[u].add = 0ll, T[u].mul = 1ll; T[u].sum = T[u].st*(r-l+1)%mod; T[u].fsum = T[u].st*T[u].st%mod*(r-l+1)%mod; return; } pushdown(u,l,r); if(L<=mid)changeset(u<<1,l,mid,L,R,x); if(R>mid)changeset(u<<1|1,mid+1,r,L,R,x); pushup(u,l,r); } ll fsum, sum; void init(){ fsum = sum = 0ll; } void query(int u,int l,int r,int L,int R){ if(L<=l&&r<=R){ add(sum, T[u].sum); add(fsum, T[u].fsum); return; } pushdown(u,l,r); if(L<=mid)query(u<<1,l,mid,L,R); if(R>mid)query(u<<1|1,mid+1,r,L,R); pushup(u,l,r); } int main(){ int o,L,R,x; while(~scanf("%d%d",&n,&m)){ build(1,1,n); while(m--){ scanf("%d%d%d",&o,&L,&R); if(L > R) swap(L,R); if(o == 4){ init(); query(1,1,n,L,R); ll res = (fsum*(R-L+1)-sum*sum)%mod; if(res < 0) res += mod; printf("%lld\n", res); }else{ scanf("%d",&x); if(o == 1){ changeadd(1,1,n,L,R,x); }else if(o == 2){ changemul(1,1,n,L,R,x); }else if(o == 3){ changeset(1,1,n,L,R,x); } } } } return 0; } /***********************/愚蠢的做法，但没被卡，哈哈哈
#include <bits/stdc++.h> using namespace std; typedef long long ll; const ll mod = 1e9+7; const int maxn = 1e5+9; struct rt{ ll sq,sum; ll add,mul,val; }dat[maxn*4]; int a[maxn]; void pushUp(int k){ dat[k].sum=(dat[k<<1].sum+dat[k<<1|1].sum)%mod; dat[k].sq=(dat[k<<1].sq+dat[k<<1|1].sq)%mod; } void build(int l,int r,int k){ dat[k].add=dat[k].mul=dat[k].val=-1; if(l==r){ dat[k].sum=(ll)a[l]; dat[k].sq=(ll)a[l]*a[l]%mod; return; } int mid=(l+r)>>1; build(l,mid,k<<1); build(mid+1,r,k<<1|1); pushUp(k); } void PushDown(int k,int l,int r){ if(l==r)return; int mid=(l+r)>>1; if(dat[k].val!=-1){ ll x=dat[k].val; dat[k<<1].val=dat[k<<1|1].val=dat[k].val; dat[k<<1].sum=x*(mid-l+1)%mod; dat[k<<1|1].sum=x*(r-mid)%mod; dat[k<<1].sq=x*x%mod*(mid-l+1)%mod; dat[k<<1|1].sq=x*x%mod*(r-mid)%mod; dat[k<<1].mul=dat[k<<1].add=dat[k<<1|1].mul=dat[k<<1|1].add=-1; dat[k].val=-1; } else if(dat[k].add!=-1){ if(dat[k<<1].val!=-1||dat[k<<1].mul!=-1)PushDown(k<<1,l,mid); if(dat[k<<1|1].val!=-1||dat[k<<1|1].mul!=-1)PushDown(k<<1|1,mid+1,r); ll x=dat[k].add; dat[k<<1].sq=((dat[k<<1].sq+(dat[k<<1].sum*2%mod*x%mod))%mod+x*x%mod*(mid-l+1)%mod)%mod; dat[k<<1].sum=(dat[k<<1].sum+x*(mid-l+1))%mod; dat[k<<1].add=((dat[k<<1].add==-1?0:dat[k<<1].add)+x)%mod; dat[k<<1|1].sq=((dat[k<<1|1].sq+(dat[k<<1|1].sum*2%mod*x%mod))%mod+x*x%mod*(r-mid)%mod)%mod; dat[k<<1|1].sum=(dat[k<<1|1].sum+x*(r-mid))%mod; dat[k<<1|1].add=((dat[k<<1|1].add==-1?0:dat[k<<1|1].add)+x)%mod; dat[k].add=-1; } else if(dat[k].mul!=-1){ if(dat[k<<1].val!=-1||dat[k<<1].add!=-1)PushDown(k<<1,l,mid); if(dat[k<<1|1].val!=-1||dat[k<<1|1].add!=-1)PushDown(k<<1|1,mid+1,r); ll x=dat[k].mul; dat[k<<1].sum=dat[k<<1].sum*x%mod; dat[k<<1|1].sum=dat[k<<1|1].sum*x%mod; dat[k<<1].sq=dat[k<<1].sq*x%mod*x%mod; dat[k<<1|1].sq=dat[k<<1|1].sq*x%mod*x%mod; dat[k<<1].mul=(dat[k<<1].mul==-1?1ll:dat[k<<1].mul)*x%mod; dat[k<<1|1].mul=(dat[k<<1|1].mul==-1?1ll:dat[k<<1|1].mul)*x%mod; dat[k].mul=-1; } } void add(int a,int b,int l,int r,int k,ll x){ if(a<=l&&r<=b){ if(dat[k].val!=-1||dat[k].mul!=-1)PushDown(k,l,r); dat[k].sq=((dat[k].sq+(dat[k].sum*2%mod*x%mod))%mod+x*x%mod*(r-l+1)%mod)%mod; dat[k].sum=(dat[k].sum+x*(r-l+1)%mod)%mod; dat[k].add=((dat[k].add==-1?0:dat[k].add)+x)%mod; return; } int mid=(l+r)>>1; PushDown(k,l,r); if(a<=mid)add(a,b,l,mid,k<<1,x); if(b>mid)add(a,b,mid+1,r,k<<1|1,x); pushUp(k); } void mul(int a,int b,int l,int r,int k,ll x){ if(a<=l&&r<=b){ if(dat[k].add!=-1||dat[k].val!=-1)PushDown(k,l,r); dat[k].sq=dat[k].sq*x%mod*x%mod; dat[k].sum=dat[k].sum*x%mod; dat[k].mul=(dat[k].mul==-1?1ll:dat[k].mul)*x%mod; return; } PushDown(k,l,r); int mid=(l+r)>>1; if(a<=mid)mul(a,b,l,mid,k<<1,x); if(b>mid)mul(a,b,mid+1,r,k<<1|1,x); pushUp(k); } void val(int a,int b,int l,int r,int k,ll x){ if(a<=l&&r<=b){ dat[k].val=x; dat[k].sum=(r-l+1)*x%mod; dat[k].sq=(r-l+1)*x%mod*x%mod; dat[k].mul=dat[k].add=-1; return; } PushDown(k,l,r); int mid=(l+r)>>1; if(a<=mid)val(a,b,l,mid,k<<1,x); if(b>mid)val(a,b,mid+1,r,k<<1|1,x); pushUp(k); } ll query1(int a,int b,int l,int r,int k){ if(a<=l&&r<=b)return dat[k].sq; PushDown(k,l,r); int mid=(l+r)>>1; ll ans=0; if(a<=mid)ans=(ans+query1(a,b,l,mid,k<<1))%mod; if(b>mid)ans=(ans+query1(a,b,mid+1,r,k<<1|1))%mod; return ans; } ll query2(int a,int b,int l,int r,int k){ if(a<=l&&r<=b)return dat[k].sum; PushDown(k,l,r); int mid=(l+r)>>1; ll ans=0; if(a<=mid)ans=(ans+query2(a,b,l,mid,k<<1))%mod; if(b>mid)ans=(ans+query2(a,b,mid+1,r,k<<1|1))%mod; return ans; } int main(){ int n,m; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++)scanf("%d",&a[i]); build(1,n,1); int o,l,r; ll k; for(int i=0;i<m;i++){ scanf("%d%d%d",&o,&l,&r); if(o==4){ ll x=query1(l,r,1,n,1); ll y=query2(l,r,1,n,1); // cout<<x<<" "<<y<<endl; cout<<((r-l+1)*x%mod-y*y%mod+mod)%mod<<endl; } else{ scanf("%lld",&k); if(o==1){ add(l,r,1,n,1,k); } else if(o==2){ mul(l,r,1,n,1,k); } else{ val(l,r,1,n,1,k); } } } return 0; }
