题目链接：codeforces 85D. Sum of Medians
题意：
addx表示向集合中添加x（添加x的时候保证x是第一次被添加入集合）
delx表示从集合中删除x（删除x的时候保证x存在于集合中）
sum将集合排序后，询问集合里面所有下标i%5=3的元素的和（如果集合为空输出0） 题解： 线段树的每一个节点维护5个值，表示这个区间%5的和，然后开一个mov数组表示这个区间向后移了多少位。 注意的是每次插入一个数，要先将[i+1,r]向后移一个区间后，在把数插进去，这样答案才不会错。
1 #include<bits/stdc++.h> 2 #define ls l,m,rt<<1 3 #define rs m+1,r,rt<<1|1 4 #define mst(a,b) memset(a,b,sizeof(a)) 5 #define F(i,a,b) for(int i=a;i<=b;++i) 6 using namespace std; 7 typedef long long ll; 8 typedef pair<int,int>P; 9 10 const int N=1e5+7;11 int n,mov[N<<2],hsh[N],h_ed,x,ed;12 ll sum[N<<2][5];13 P q[N];14 char op[10];15 16 int getid(int x){return lower_bound(hsh+1,hsh+1+h_ed,x)-hsh;}17 18 void up(int rt){F(i,0,4)sum[rt][(mov[rt]+i)%5]=sum[rt<<1][i]+sum[rt<<1|1][i];}19 20 void add(int op,int x,int l=1,int r=h_ed,int rt=1)21 {22if(l==r)23{24 mst(sum[rt],0);25 if(op==1)sum[rt][mov[rt]%5]=hsh[x];26 return;27}28int m=l+r>>1;29if(x<=m)add(op,x,ls);30else add(op,x,rs);31up(rt);32 }33 34 void update(int op,int L,int R,int l=1,int r=h_ed,int rt=1)35 {36if(L<=l&&r<=R)37{38 mov[rt]+=op;39 if(l!=r)up(rt);40 else 41 {42 ll tmp=0;43 F(i,0,4)if(sum[rt][i])tmp=sum[rt][i];44 mst(sum[rt],0),sum[rt][mov[rt]%5]=tmp;45 }46 return;47}48int m=l+r>>1;49if(L<=m)update(op,L,R,ls);50if(R>m)update(op,L,R,rs);51up(rt);52 }53 54 int main(){55scanf("%d",&n);56F(i,1,n)57{58 scanf("%s",op);59if(op[0]=='s')q[i]=P(0,0);60else61{62 scanf("%d",&x);63 q[i]=P(op[0]=='a'?1:-1,x);64 hsh[++ed]=x;65}66}67sort(hsh+1,hsh+1+ed),h_ed=unique(hsh+1,hsh+1+ed)-hsh-1;68F(i,1,n)69{70 if(!q[i].first)printf("%lld\n",sum[1][2]);71 else72 {73 update(q[i].first,getid(q[i].second)+1,h_ed);74 add(q[i].first,getid(q[i].second));75 }76}77return 0;78 }
View Code
以下是分块解法：
将所有数hash后分成sqrt(h_ed)块，每一块用一个set维护。
每次插入就找到对应的块，然后暴力维护这个块的信息，每个块也开一个sum[5]，来保存%5=j(j=0,1,2,3,4)的和。
ask就将所有块的和加一加。
1 #include<bits/stdc++.h> 2 #define ls l,m,rt<<1 3 #define rs m+1,r,rt<<1|1 4 #define mst(a,b) memset(a,b,sizeof(a)) 5 #define F(i,a,b) for(int i=a;i<=b;++i) 6 using namespace std; 7 typedef long long ll; 8 typedef pair<int,int>P; 9 10 const int N=1e5+7;11 int n,hsh[N],h_ed,x,ed,cnt,sqr;//sqr为每个块的大小12 P q[N];13 char op[10];14 15 int getid(int x){return lower_bound(hsh+1,hsh+1+h_ed,x)-hsh;}16 17 struct kuai18 {19int l,r;20set<int>dt;21ll sum[5];22kuai()23{24 l=r=0;25 dt.clear(),mst(sum,0);26}27 }s[501];28 29 ll ask()30 {31ll ans=0;32int mov=0;33F(i,1,cnt)34{35 ans+=s[i].sum[(5-mov+3)%5];36 mov=(mov+s[i].dt.size())%5;37}38return ans;39 }40 41 void add(int op,int x)42 {43int now=x/sqr+(x%sqr!=0),ct=0;44if(op==1)s[now].dt.insert(hsh[x]);45else s[now].dt.erase(hsh[x]);46set<int>::iterator it;47mst(s[now].sum,0);48for(it=s[now].dt.begin();it!=s[now].dt.end();it++)49 ct++,s[now].sum[ct%5]+=*it;50 }51 52 int main(){53scanf("%d",&n);54F(i,1,n)55{56 scanf("%s",op);57if(op[0]=='s')q[i]=P(0,0);58else59{60 scanf("%d",&x);61 q[i]=P(op[0]=='a'?1:-1,x);62 hsh[++ed]=x;63}64}65sort(hsh+1,hsh+1+ed),h_ed=unique(hsh+1,hsh+1+ed)-hsh-1;66sqr=sqrt(h_ed+0.5);67if(sqr)cnt=h_ed/sqr+(h_ed%sqr!=0);//注意只有sum的情况68F(i,1,n)if(!q[i].first)printf("%lld\n",ask());69 else add(q[i].first,getid(q[i].second));70return 0;71 }
View Code
