首页 > 代码库 > hdu 4288 Coder

hdu 4288 Coder

2024-07-17 17:20:35   229人阅读

http://acm.hdu.edu.cn/showproblem.php?pid=4288

题意：add 就是在集合里面加上一个数x； del 就是从集合里删去一个数x； sum是求位置i%5==3的数的和。

tree[i].sum[5] 里面数组存的是不同位置%5之后分别对应的和。

  1 #include <cstdio>  2 #include <cstring>  3 #include <algorithm>  4 #define maxn 100010  5 using namespace std;  6   7 char str[maxn][4];  8 int x[maxn],xx[maxn];  9 struct node 10 { 11     int r,l; 12     __int64 sum[6]; 13     int cnt; 14 }tree[maxn*4]; 15  16 void build(int i,int l,int r) 17 { 18     tree[i].l=l;tree[i].r=r; 19     for(int j=0; j<5; j++) tree[i].sum[j]=0; 20     tree[i].cnt=0; 21     if(l==r) return ; 22     int mid=(l+r)>>1; 23     build(i<<1,l,mid); 24     build(i<<1|1,mid+1,r); 25 } 26  27 void update(int i,int l,int r,int c,int num) 28 { 29     tree[i].cnt+=num; 30     if(tree[i].l==l&&tree[i].r==r) 31     { 32         tree[i].sum[0]+=c; 33         return ; 34     } 35     int mid=(tree[i].l+tree[i].r)>>1; 36     if(r<=mid) 37     { 38         update(i<<1,l,r,c,num); 39     } 40     else if(l>mid) 41     { 42         update(i<<1|1,l,r,c,num); 43     } 44     else 45     { 46         update(i<<1,l,mid,c,num); 47         update(i<<1|1,mid+1,r,c,num); 48     } 49     for(int j=0; j<5; j++) 50     { 51         tree[i].sum[j]=tree[i<<1].sum[j]+tree[i<<1|1].sum[((j-tree[i<<1].cnt)%5+5)%5]; 52     } 53 } 54 int bs(int l,int r,int data) 55 { 56     while(l<=r) 57     { 58         int mid=(l+r)>>1; 59         if(xx[mid]==data) 60         { 61             return mid; 62         } 63         else if(xx[mid]>data) 64         { 65             r=mid-1; 66         } 67         else 68             l=mid+1; 69     } 70 } 71 int main() 72 { 73     int n; 74     while(scanf("%d",&n)!=EOF) 75     { 76         int t1=0; 77         for(int i=0; i<n; i++) 78         { 79             scanf("%s",str[i]); 80             if(strcmp(str[i],"sum")) 81             { 82                 scanf("%d",&x[i]); 83                 xx[t1++]=x[i]; 84             } 85         } 86         sort(xx,xx+t1); 87         t1=unique(xx,xx+t1)-xx; 88         build(1,1,t1); 89         for(int i=0; i<n; i++) 90         { 91             int l1=bs(0,t1-1,x[i]); 92             if(!strcmp(str[i],"add")) 93             { 94                 update(1,l1+1,l1+1,x[i],1); 95             } 96             else if(!strcmp(str[i],"del")) 97             { 98                 update(1,l1+1,l1+1,-x[i],-1); 99             }100             else if(!strcmp(str[i],"sum"))101             {102                 printf("%I64d\n",tree[1].sum[2]);103             }104         }105     }106     return 0;107 }
View Code

 


联系
我们