题目
http://noi.ac/contest/356/problem/2028
思路
莫队
维护当前区间的答案和每一类的修改数、查询数
若干种情况
左侧加入修改，答案+=原有的同类查询数，同时维护修改数
左侧加入查询，答案不变，仅维护查询数
右侧加入修改，答案不变，仅维护修改数
右侧加入查询，答案+=原有的同类修改数，同时维护查询数
删除是加入的逆过程
代码
#include<bits/stdc++.h>
using namespace std;typedef long long LL;
/*struct Tr {int v,bz,id; }tr[N*4]; int T[N],n,ans,yjy; void update(int u) {int ls=u<<1,rs=u<<1|1;if(tr[ls].id) tr[u].id=1,tr[u].v=max(tr[ls].v,tr[u].v);if(tr[rs].id) tr[u].id=1,tr[u].v=max(tr[rs].v,tr[u].v);if(tr[u].id==0) tr[u].bz=0,tr[u].v=0; } void pushdown(int u,int st,int ed) {int ls=u<<1,rs=u<<1|1;if(tr[ls].id) tr[ls].bz+=tr[u].bz,tr[ls].v+=tr[u].bz;if(tr[rs].id) tr[rs].bz+=tr[u].bz,tr[rs].v+=tr[u].bz;tr[u].bz=0; } void add(int t) {for(int i=t; i<=n; i+=i&-i) T[i]+=1; } int total(int t) {int ret=0;for(int i=t; i; i-=i&-i) ret+=T[i];return ret; } void ins(int u,int st,int ed,int x) {if(st==ed){tr[u].bz=0; tr[u].v=0; tr[u].id=0; return;}pushdown(u,st,ed);int mid=st+ed>>1;if(mid>=x) ins(u<<1,st,mid,x);else ins(u<<1|1,mid+1,ed,x);update(x); } void modify(int u,int st,int ed,int l,int r,int v) {if(l<=st&&ed<=r){tr[u].bz+=v; tr[u].v+=v; return;}pushdown(u,st,ed);int mid=st+ed>>1;if(mid>=l) modify(u<<1,st,mid,l,r,v);if(mid<r) modify(u<<1|1,mid+1,ed,l,r,v);update(u); } int query(int u,int st,int ed,int l,int r) {if(l<=st&&ed<=r){return tr[u].v;}pushdown(u,st,ed);int mid=st+ed>>1,aii=0;if(mid>=l) aii=max(aii,query(u<<1,st,mid,l,r));if(mid<r) aii=max(aii,query(u<<1|1,mid+1,ed,l,r));return aii; }*/
const int N=50000,M=1000000,B=50;char Rc(){char c=getchar();for(;c<'A'||c>'Z';c=getchar());return c;
}int Ri(){int x=0;char c=getchar();for(;c<'0'||c>'9';c=getchar());for(;c<='9'&&c>='0';c=getchar()) x=x*10+c-'0';return x;
}int n,m,cq,opt[N+9],a[N+9];
struct question{int l,r,id;question(int L=0,int R=0,int Id=0){l=L;r=R;id=Id;}
}q[M+9];bool cmp(const question &a,const question &b){return a.l/B==b.l/B?a.r<b.r:a.l<b.l;}void into(){n=Ri();m=Ri();cq=Ri();for(int i=1;i<=n;++i){opt[i]=Rc()=='A';a[i]=Ri();}for(int i=1;i<=cq;++i){q[i].l=Ri();q[i].r=Ri();q[i].id=i;}
}int cnt[2][N+9];
LL now,ans[M+9];void Mo(){sort(q+1,q+cq+1,cmp);int l=1,r=0;for(int i=1;i<=cq;++i){for(;r<q[i].r;){++r;if (!opt[r]) now+=cnt[1][a[r]];++cnt[opt[r]][a[r]];}for(;l>q[i].l;){--l;if (opt[l]) now+=cnt[0][a[l]];++cnt[opt[l]][a[l]];}for(;r>q[i].r;){if (!opt[r]) now-=cnt[1][a[r]];--cnt[opt[r]][a[r]];--r;}for(;l<q[i].l;){if (opt[l]) now-=cnt[0][a[l]];--cnt[opt[l]][a[l]];++l;}ans[q[i].id]=now;}
}void work(){Mo();
}void outo(){for(int i=1; i<=cq; ++i)printf("%lld\n",ans[i]);
}int main(){into();work();outo();return 0;
}