hdu 4288 Coder (离散化, 线段树,单点更新,区间合并)

题目链接

题意:n(1E5)个操作,分为三种,add x表示将x加到集合中(保证集合中之前没有x),del x表示从集合中删掉x(保证集合中一定右x),sum表示求集合中所有元素按从小到大排列后,所有的下标中满足i%5=3的a[i]的和。1=<x<=1E9

思路:很容易想到的是,由于插入和删除元素造成的位置改变是剧烈的,因此要分别维护i%5==k,k属于0..4的元素的和。

这道题的核心点在于,由于只有1E5个操作,我们可以将元素离散化,这样做的目的是,将每个数和位置一一对应,每个位置用1或者0,表示该位置对应的元素是否在集合中。

考虑线段树,维护6个域,1个是区间中,在集合中的元素个数,剩下5个域,分别表示以该区间的端点为位置1,位置x%i=k的元素的和(k属于0..4)。因此每个叶子节点都是位置1.

考虑PushUp, 区间元素和之间累加,难点在于其他5个域的维护。

假设当前区间为rt,那么对于sum[0..4] (sum代表的就是上面说的要维护的5个域),显然区间rt<<1的答案可以直接贡献给rt.

对于rt<<1|1的答案,考虑rt<<1|1中位置为%5==x的元素和,rt<<1中的元素个数为len个,那么rt<<1|1中sum[x]对 rt中的sum[(x+len)%5]有贡献。

反推出对rt 中 sum[i]有贡献的是rt<<1|1中的sum[(i-len+5)%5)]

/* ***********************************************
Author :111qqz
Created Time :2017年09月26日 星期二 12时42分10秒
File Name :4288.cpp
************************************************ */
 1#include <cstdio>
 2#include <cstring>
 3#include <iostream>
 4#include <algorithm>
 5#include <vector>
 6#include <queue>
 7#include <set>
 8#include <map>
 9#include <string>
10#include <cmath>
11#include <cstdlib>
12#include <ctime>
13#define PB push_back
14#define fst first
15#define sec second
16#define lson l,m,rt<<1
17#define rson m+1,r,rt<<1|1
18#define ms(a,x) memset(a,x,sizeof(a))
19typedef long long LL;
20#define pi pair < int ,int >
21#define MP make_pair
 1using namespace std;
 2const double eps = 1E-8;
 3const int dx4[4]={1,0,0,-1};
 4const int dy4[4]={0,-1,1,0};
 5const int inf = 0x3f3f3f3f;
 6const int N=1E5+7;
 7int n;
 8struct Node
 9{
10    int cnt; //区间中,在集合中存在的元素的个数。
11    LL sum[5]; //sum[i]表示该区间中,以区间起点为下标1开始计算时,位置为x%5==i时的元素的和。
12}tree[N<<2];
13struct Opt
14{
15    int opt;
16    LL val;
17}qu[N];
18LL H[N],A[N];
19int cnt;
20int Hash( int x)
21{
22    return lower_bound(H,H+cnt,x)-H;
23}
24void PushUp( int rt)
25{
26    tree[rt].cnt = tree[rt<<1].cnt + tree[rt<<1|1].cnt;
27    for ( int i = 0 ; i < 5 ; i++)
28    {
29    int left_len = tree[rt<<1].cnt;
30    tree[rt].sum[i] = tree[rt<<1].sum[i] + tree[rt<<1|1].sum[((i-left_len)%5+5)%5];
31    }
32}
33void update( int p,int opt,int l,int r,int rt)
34{
35    if (l==r)
36    {
37    if (opt==1)
38    {
39        tree[rt].cnt=1;
40        tree[rt].sum[1]=H[p-1];
41    }
42    else
43    {
44        tree[rt].cnt=0;
45        tree[rt].sum[1]=0;
46    }
47    return ;
48    }
 1    int m = (l+r)>>1;
 2    if (p<=m) update(p,opt,lson);
 3    else update(p,opt,rson);
 4    PushUp(rt);
 5}
 6int main()
 7{
 8    #ifndef  ONLINE_JUDGE 
 9    freopen("./in.txt","r",stdin);
10  #endif
11    while (~scanf("%d",&n))
12    {
13        ms(tree,0);
14        cnt=0;
15        for ( int i = 1 ; i <= n ; i++)
16        {
17        char tmp[5];
18        scanf("%s",tmp);
19        if (tmp[0]=='a')
20        {
21            qu[i].opt=1;
22            int x;
23            scanf("%d",&x);
24            qu[i].val=x;
25            H[cnt++]=x;
26        }else if (tmp[0]=='d')
27        {
28            qu[i].opt=2;
29            int x;
30            scanf("%d",&x);
31            qu[i].val = x;
32        }else
33        {
34            qu[i].opt=3;
35        }
36        }
37        sort(H,H+cnt);
38        cnt = unique(H,H+cnt)-H;
39        //cout<<"cnt:"<<cnt<<endl;    
40        for ( int i = 1 ; i <= n ; i++)
41        {
42            LL ans = tree[1].sum[3];
43            if (qu[i].opt==3) printf("%lld\n",ans);
44            else
45            {
46            int x = Hash(qu[i].val)+1;
47            //cout<<"val:"<<qu[i].val<<"x:"<<x<<" H[p-1]:"<<H[x-1]<<endl;
48            update(x,qu[i].opt,1,cnt+1,1);
49            }
50        }
51     }
52  #ifndef ONLINE_JUDGE  
53  fclose(stdin);
54  #endif
55    return 0;
56}