程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> hdu 4288 Coder

hdu 4288 Coder

編輯：C++入門知識

hdu 4288 Coder

初始有一個空集合，有N個操作，1 add x向集合中加一個元素x，2 del x在集合中刪除一個元素x，sum詢問下標mod 5為3的元素的和。

建立一棵線段樹，能夠實現數組中元素的刪除和添加，維護區間的和。

重點是怎麼在元素隨時變動的條件下求下標mod 5 為3的數的和。首先節點有一個信息cnt表示區間內元素的個數，sum[5]

代表了在這個區間中下表分別對5取余的元素的和，注意是在當前區間內，若當前有一個元素那麼存入sum[1]中。然後就是push_up時，sum【】的維護，這個挺難想的，看了題解然後和同學討論了好久才明白。

#include 
#include 
#include
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
//#define LL long long
#define LL __int64
#define eps 1e-12
#define PI acos(-1.0)
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = 100010;

struct Info
{
    char str[5];
    LL num;
}info[maxn];
LL x[maxn];

struct node
{
    int l,r;
    int cnt;
    LL sum[6];
}tree[maxn*4];


void build(int v, int l, int r)
{
    tree[v].l = l;
    tree[v].r = r;
    tree[v].cnt = 0;
    tree[v].sum[0] = tree[v].sum[1] = tree[v].sum[2] = tree[v].sum[3] = tree[v].sum[4] = 0;
    if(l == r)
        return;
    int mid = (l+r)>>1;
    build(v*2,l,mid);
    build(v*2+1,mid+1,r);
}

int Binsearch(int l, int r, int key)
{
    int mid,low = l,high = r;
    while(high >= low)
    {
        mid = (low + high) >> 1;
        if(x[mid] == key)
            return mid;
        if(x[mid] > key)
            high = mid-1;
        else low = mid+1;
    }
    return -1;
}

void update(int v, int pos, LL num, int f)
{
    tree[v].cnt += f;
    if(tree[v].l == tree[v].r)
    {
        tree[v].sum[1] += num;
        return;
    }
   int mid = (tree[v].l + tree[v].r) >> 1;
   if(pos <= mid)
        update(v*2,pos,num,f);
   else update(v*2+1,pos,num,f);
    //重點，維護區間的和。
   for(int i = 0; i < 5; i++)
        tree[v].sum[i] = tree[v*2].sum[i] + tree[v*2+1].sum[((i-tree[v*2].cnt)%5+5)%5];
}


int main()
{
    int n;
    int cnt;
    while(~scanf(%d,&n))
    {
        cnt = 0;
        for(int i = 1; i <= n; i++)
        {
            scanf(%s,info[i].str);
            if(strcmp(info[i].str,sum) != 0)
            {
                scanf(%I64d,&info[i].num);
                x[++cnt] = info[i].num;
            }
        }
        //離散化
        sort(x+1,x+1+cnt);
        cnt = unique(x+1,x+1+cnt)-(x+1);

        build(1,1,cnt);
        int pos;
        for(int i = 1; i <= n; i++)
        {
            if(info[i].str[0] != 's')
                 pos = Binsearch(1,cnt,info[i].num);//二分尋找下標
            if(info[i].str[0] == 'a')
            {
                update(1,pos,info[i].num,1);
            }
            else if(info[i].str[0] == 'd')
            {
                update(1,pos,-info[i].num,-1);
            }
            else
                printf(%I64d
,tree[1].sum[3]);
        }
    }
    return 0;
}