hdu4288 Coder（线段树单点更新）

题意：支持增删，查操作，最后的序列式递增的。

做法:主要是如何维护mod5的sum值，这里左儿子可以不用管，关键是右儿子的处理，可以假设右儿子有t个节点，左儿子有cnt个节点，

则令（t+cnt）MOD 5= i 则tmod5=(i-cnt MOD 5)MOD 5 ,所以剩下的就是维护每个节点的节点总数以及相应的和就好了。

  1 #include<cstring>

 2 #include<algorithm>
 3 #include<cstdio>
 4 typedef long long ll;
 5 using namespace std;
 6 #define lz u<<1,l,mid
 7 #define rz u<<1|1,mid+1,r
 8 const int MAX = 100000+10;
 9 struct node
10 {
11     ll sum[6],cnt;
12 }tree[MAX<<2];
13 int num[MAX],rnum[MAX],check[MAX];
14 void build(int u,int l,int r)
15 {
16     for(int i=0;i<5;i++) tree[u].sum[i]=0;
17     tree[u].cnt=0;
18     if(l!=r)
19     {
20         int mid=(l+r)>>1;
21         build(lz); build(rz);
22     }
23 }
24 void add(int u,int l,int r,int x,int d,int cur)
25 {
26     if(l==r)
27     {
28         tree[u].sum[1]+=d;
29         tree[u].cnt+=cur;
30         return;
31     }
32     int mid=(l+r)>>1;
33     if(x<=mid) add(lz,x,d,cur);
34     else add(rz,x,d,cur);
35     tree[u].cnt=tree[u<<1].cnt+tree[u<<1|1].cnt;
36     for(int i=0;i<5;i++)
37     {
38         tree[u].sum[i]=tree[u<<1].sum[i]+tree[u<<1|1].sum[((i-tree[u<<1].cnt)%5+5)%5];
39     }
40 }
41 int main()
42 {
43     int n,a; char str[10];
44     while(scanf("%d",&n)==1)
45     {
46         int cur=0;
47         for(int i=0;i<n;i++)
48         {
49             scanf("%s",str);
50             if(str[0]=='a')
51             {
52                 check[i]=1;
53                 scanf("%d",&a);
54                 num[i]=rnum[cur++]=a;
55             }
56             else if(str[0]=='d')
57             {
58                 check[i]=2;
59                 scanf("%d",&num[i]);
60             }
61             else  check[i]=3;
62         }
63         sort(rnum,rnum+cur);
64         int tot=unique(rnum,rnum+cur)-rnum;
65         if(tot!=0) build(1,1,tot);
66         for(int i=0;i<n;i++)
67         {
68             if(check[i]==1)
69             {
70                 int pos=lower_bound(rnum,rnum+tot,num[i])-rnum+1;
71                 add(1,1,tot,pos,num[i],1);
72             }
73             else if(check[i]==2)
74             {
75                 int pos=lower_bound(rnum,rnum+tot,num[i])-rnum +1;
76                 add(1,1,tot,pos,-num[i],-1);
77             }
78             else
79             {
80                 if(tot==0) printf("0
");
81                 else
82                 {
83                     printf("%I64d
",tree[1].sum[3]);
84                 }
85             }
86         }
87     }
88     return 0;
89 }