题目
如图，我们写出第一个表达式就是答案，然后推一下，变成第二个。
所以线段树保存一下区间和，区间平方和。就可以做出这题了。
另外要说的是，这题的牛客网的测试数据有毒，区间查询的区间不正确。经过实锤，区间的l会小于1！很气人
所以(r-l+1)*(C2+C)不能在区间里一起计算。
线段树只能用来查询到区间和-区间平方和。剩余的另外算。琢磨着标程可能就这样写的。
#include <iostream> #include <stdio.h> using namespace std; #define LL long long const LL maxn = 1e5+55; const LL mod = 1e9+7; #define lt x<<1 #define rt x<<1|1 LL sum[maxn<<2],sum2[maxn<<2]; LL len[maxn<<2]; LL add[maxn<<2]; LL a[maxn]; void up(LL x) { sum[x]=(sum[rt]+sum[lt])%mod; sum2[x]=(sum2[rt]+sum2[lt])%mod; } void pushdown(LL x) { if(add[x]){ LL q=add[x]; (add[lt]+=q)%=mod; (add[rt]+=q)%=mod; sum2[lt]=(sum2[lt]+2*q%mod*sum[lt]%mod+len[lt]*q%mod*q%mod)%mod; sum[lt]=(sum[lt]+len[lt]*q%mod)%mod; sum2[rt]=(sum2[rt]+2*q%mod*sum[rt]%mod+len[rt]*q%mod*q%mod)%mod; sum[rt]=(sum[rt]+len[rt]*q%mod)%mod; add[x]=0; } } void build(LL x,LL l,LL r) { if(l==r){ sum[x]=a[l]%mod; sum2[x]=a[l]*a[l]%mod; len[x]=1; add[x]=0; return; }else{ LL mid = (l+r)>>1; build(lt,l,mid); build(rt,mid+1,r); len[x]=(len[lt]+len[rt])%mod; add[x]=0; up(x); } } LL n,c,Q; LL cc_c; //LL an=0; LL query(LL x,LL l,LL r,LL ll,LL rr) { LL ans = 0; if(ll<=l&&rr>=r){ ans=((sum[x]+mod-sum2[x])%mod)%mod; // (an+=len[x]%mod)%=mod; return ans; } pushdown(x); LL mid = (l+r)>>1; if(ll<=mid){ (ans+=query(lt,l,mid,ll,rr))%=mod; } if(mid+1<=rr){ (ans+=query(rt,mid+1,r,ll,rr))%=mod; } up(x); return ans%mod; } void change(LL x,LL l,LL r,LL ll,LL rr,LL q) { if(ll<=l&&rr>=r){ add[x]=(add[x]+q)%mod; sum2[x]=(sum2[x]+2*q%mod*sum[x]%mod+len[x]*q%mod*q%mod)%mod; sum[x]=(sum[x]+len[x]*q%mod)%mod; return; }else{ pushdown(x); LL mid=(l+r)>>1; if(ll<=mid){ change(lt,l,mid,ll,rr,q); } if(mid+1<=rr){ change(rt, mid+1, r, ll, rr, q); } up(x); } } LL qkm(LL base,LL mi) { LL ans = 1; base%=mod; while(mi){ if(mi&1) ans=ans*base%mod; base=base*base%mod; mi>>=1; } return ans; } int main() { scanf("%lld %lld %lld",&n,&c,&Q); cc_c=(c*c%mod+c)%mod; for(LL i=1;i<=n;i++) scanf("%lld",&a[i]); build(1,1,n); LL nc=qkm(2*c,mod-2); while(Q--){ // an=0; LL l,r,q; scanf("%lld%lld%lld",&l,&r,&q); // if(l<1) while(1); //加上这一句话，运行超时，事实证明，数据有不合格的 //所以 标程肯定是 (r-l+1)*(c*c+c)这样写的 //不能把c*c+c 放在线段树查询里面一起算，wa到怀疑人生 printf("%lld\n", (query(1,1,n,l,r)+(r-l+1)*cc_c%mod)%mod*nc%mod); change(1,1,n,l,r,q); } }