存个树状数组的板子省的每次都抄别人
struct sgt{ ll c1[N],c2[N]; inline void update(ll x,ll k) { ll i=x; while(x<=n) { c1[x]+=k; c2[x]+=i*k; x+=x&-x; } return; } inline ll sum(ll x) { ll ans=0; ll i=x; while(x>0) { ans+=c1[x]*(i+1); ans-=c2[x]; x-=x&-x; } return ans; } inline void change(int x,int y,ll z) { // cerr<<x<<" "<<y<<endl; update(x,z); update(y+1,-z); } ll query(int x) { return sum(x)-sum(x-1); } }S;