传送门
题意：单点修改，区间求和
题解：
当然，线段树或者树状数组或者其他数据结构就是裸题了，其实还有CDQ搞法，空间上直接优化logn。
首先区间求和等同于前缀求和，转化为时间上a< b，序列上c< d的二维偏序带权求值。然后就是裸题了。（相当于求逆序对）。
#include<bits/stdc++.h> using namespace std; const int Maxn=3e5+50; streambuf *ib,*ob; inline int read() { char ch=ib->sbumpc();int i=0,f=1; while(!isdigit(ch)){if(ch=='-')f=-1;ch=ib->sbumpc();} while(isdigit(ch)){i=(i<<1)+(i<<3)+ch-'0';ch=ib->sbumpc();} return i*f; } int buf[50]; inline void W(int x) { if(!x){ob->sputc('0');return;} if(x<0){ob->sputc('-');x=-x;} while(x){buf[++buf[0]]=x%10,x/=10;} while(buf[0])ob->sputc(buf[buf[0]--]+'0'); return; } int n,cnt,cnt2,ans[Maxn]; char ch[10]; struct query { int pos,val,type; }q[Maxn],tmp[Maxn]; inline void solve(int l,int r) { if(l==r)return; int mid=(l+r)>>1; solve(l,mid); solve(mid+1,r); for(int i=l;i<=r;i++)tmp[i]=q[i]; int head1=l,head2=mid+1,sum=0,pos=l; while(head1<=mid&&head2<=r) { if(tmp[head1].pos<=tmp[head2].pos) { if(tmp[head1].type==1)sum+=tmp[head1].val; q[pos++]=tmp[head1++]; } else { if(tmp[head2].type!=1)ans[tmp[head2].val]+=((tmp[head2].type==2)?-1:1)*sum; q[pos++]=tmp[head2++]; } } while(head1<=mid){q[pos++]=tmp[head1++];} while(head2<=r) { if(tmp[head2].type!=1)ans[tmp[head2].val]+=((tmp[head2].type==2)?-1:1)*sum; q[pos++]=tmp[head2++]; } } int main() { ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);ib=cin.rdbuf(); ob = std::cout.rdbuf(); int T=read(); for(int tt=1;tt<=T;tt++) { cout<<"Case "<<tt<<":"<<'\n'; memset(q,0,sizeof(q));memset(ans,0,sizeof(ans)); n=read();cnt=cnt2=0; for(int i=1;i<=n;i++){q[++cnt].type=1;q[cnt].pos=i;q[cnt].val=read();} while(cin>>(ch+1),ch[1]!='E') { ++cnt; if(ch[1]=='A') { q[cnt].type=1;q[cnt].pos=read();q[cnt].val=read(); } else if(ch[1]=='S') { q[cnt].type=1;q[cnt].pos=read();q[cnt].val=-read(); } else { ++cnt2;q[cnt].type=2;q[cnt].pos=read()-1;q[cnt].val=cnt2; ++cnt;q[cnt].type=3;q[cnt].pos=read();q[cnt].val=cnt2; } } solve(1,cnt); for(int i=1;i<=cnt2;i++) {W(ans[i]),ob->sputc('\n');} } }