codeforces 85D. Sum of Medians(线段树or分块)

题意：

add x 表示向集合中添加x（添加x的时候保证x是第一次被添加入集合）
del x 表示从集合中删除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 {
22     if(l==r)
23     {
24         mst(sum[rt],0);
25         if(op==1)sum[rt][mov[rt]%5]=hsh[x];
26         return;
27     }
28     int m=l+r>>1;
29     if(x<=m)add(op,x,ls);
30     else add(op,x,rs);
31     up(rt);
32 }
33 
34 void update(int op,int L,int R,int l=1,int r=h_ed,int rt=1)
35 {
36     if(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     }
48     int m=l+r>>1;
49     if(L<=m)update(op,L,R,ls);
50     if(R>m)update(op,L,R,rs);
51     up(rt);
52 }
53 
54 int main(){
55     scanf("%d",&n);
56     F(i,1,n)
57     {
58         scanf("%s",op);
59          if(op[0]=='s')q[i]=P(0,0);
60          else
61          {
62              scanf("%d",&x);
63              q[i]=P(op[0]=='a'?1:-1,x);
64              hsh[++ed]=x;
65          }
66     }
67     sort(hsh+1,hsh+1+ed),h_ed=unique(hsh+1,hsh+1+ed)-hsh-1;
68     F(i,1,n)
69     {
70         if(!q[i].first)printf("%lld
",sum[1][2]);
71         else
72         {
73             update(q[i].first,getid(q[i].second)+1,h_ed);
74             add(q[i].first,getid(q[i].second));
75         }
76     }
77     return 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 kuai
18 {
19     int l,r;
20     set<int>dt;
21     ll sum[5];
22     kuai()
23     {
24         l=r=0;
25         dt.clear(),mst(sum,0);
26     }
27 }s[501];
28 
29 ll ask()
30 {
31     ll ans=0;
32     int mov=0;
33     F(i,1,cnt)
34     {
35         ans+=s[i].sum[(5-mov+3)%5];
36         mov=(mov+s[i].dt.size())%5;
37     }
38     return ans;
39 }
40 
41 void add(int op,int x)
42 {
43     int now=x/sqr+(x%sqr!=0),ct=0;
44     if(op==1)s[now].dt.insert(hsh[x]);
45     else s[now].dt.erase(hsh[x]);
46     set<int>::iterator it;
47     mst(s[now].sum,0);
48     for(it=s[now].dt.begin();it!=s[now].dt.end();it++)
49         ct++,s[now].sum[ct%5]+=*it;
50 }
51 
52 int main(){
53     scanf("%d",&n);
54     F(i,1,n)
55     {
56         scanf("%s",op);
57          if(op[0]=='s')q[i]=P(0,0);
58          else
59          {
60              scanf("%d",&x);
61              q[i]=P(op[0]=='a'?1:-1,x);
62              hsh[++ed]=x;
63          }
64     }
65     sort(hsh+1,hsh+1+ed),h_ed=unique(hsh+1,hsh+1+ed)-hsh-1;
66     sqr=sqrt(h_ed+0.5);
67     if(sqr)cnt=h_ed/sqr+(h_ed%sqr!=0);//注意只有sum的情况
68     F(i,1,n)if(!q[i].first)printf("%lld
",ask());
69         else add(q[i].first,getid(q[i].second));
70     return 0;
71 }

View Code