传送门
题解： 随便分一下块就好了。。
#include <bits/stdc++.h> using namespace std; typedef unsigned long long LL; const int RLEN=1<<18|1; inline char nc() { static char ibuf[RLEN],*ib,*ob; (ib==ob) && (ob=(ib=ibuf)+fread(ibuf,1,RLEN,stdin)); return (ib==ob) ? -1 : *ib++; } inline int rd() { char ch=nc(); int i=0,f=1; while(!isdigit(ch)) {if(ch=='-')f=-1; ch=nc();} while(isdigit(ch)) {i=(i<<1)+(i<<3)+ch-'0'; ch=nc();} return i*f; } inline void W(LL x) { static int buf[50]; if(!x) {putchar('0'); return;} if(x<0) {putchar('-'); x=-x;} while(x) {buf[++buf[0]]=x%10; x/=10;} while(buf[0]) {putchar(buf[buf[0]--]+'0');} } const int N=1e5+50, S=334, H=N/S+5; int n,m,a[N],bl[N],bg[H],ed[H],h; struct BL { LL s[N],tag[H]; inline void add(int pos,LL val) { int t=bl[pos]; for(int i=t+1;i<=h;i++) tag[i]+=val; for(int i=pos;i<=ed[t];i++) s[i]+=val; } inline LL ask(int pos) {return s[pos]+tag[bl[pos]];} inline LL ask(int l,int r) {return ask(r)-ask(l-1);} } block; int li[N],ri[N]; LL num[H][N]; LL sum[H]; inline void init() { for(int i=1,j;i<=n;) { j=min(i+S-1,n); ++h; bg[h]=i; ed[h]=j; while(i<=j) bl[i++]=h; } } inline LL ask(int l,int r) { LL val=0; if(r-l+1<=2*S) { for(int i=l;i<=r;i++) val+=block.ask(li[i],ri[i]); } else { int L=bl[l]+1, R=bl[r]-1; for(int i=L;i<=R;i++) val+=sum[i]; for(int i=l;i<bg[L];i++) val+=block.ask(li[i],ri[i]); for(int i=r;i>ed[R];i--) val+=block.ask(li[i],ri[i]); } return val; } int main() { n=rd(); init(); for(int i=1;i<=n;i++) block.s[i]=(a[i]=rd())+block.s[i-1]; for(int i=1;i<=n;i++) li[i]=rd(), ri[i]=rd(); for(int i=1;i<=h;i++) { for(int j=bg[i];j<=ed[i];j++) sum[i]+=block.ask(li[j],ri[j]), num[i][li[j]]++, num[i][ri[j]+1]--; for(int j=1;j<=n;j++) num[i][j]+=num[i][j-1]; } m=rd(); for(int i=1;i<=m;i++) { int op=rd(), l=rd(), r=rd(); if(op==1) { LL det=r-a[l]; block.add(l,det); for(int j=1;j<=h;j++) sum[j]+=num[j][l]*det; a[l]+=det; } else { W(ask(l,r)); putchar('\n'); } } }