程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> hdu4288 Coder（線段樹+離散化）

hdu4288 Coder（線段樹+離散化）

編輯：C++入門知識

hdu4288 Coder（線段樹+離散化）

題目鏈接：

huangjing

題意：

題目中給了三個操作 1：add x 就是把x插進去 2：delete x 就是把x刪除 3：sum 就是求下標%5=3的元素的和。還有一個條件是插入和刪除最後都要保證數列有序。。。首先告訴一種暴力的寫法。。因為時間非常充足，需要對stl裡面的函數有所了解。。就是直接申明一個vector的容器，然後直接用vector裡面的操作比如 insert，erase等等操作。。不過這個效率很低。。最後跑出來6000多ms。。（強哥的代碼）代碼：

#include
#include
#include
#include
#include
#include
#include
#include
#include
#define eps 1e-9
#define ll long long
#define INF 0x3f3f3f3f
using namespace std;

char s[5];
int n;

vectora;

int main()
{
    int len,val;
    vector::iterator iter;
    while(cin>>n)
    {
        len=0;
        a.clear();
        while(n--)
        {
            scanf("%s",s);
            if(s[0]=='s')
            {
                long long ans = 0;
                for(int i=2; i < len ; i+=5)
                    ans += a[i];
                cout<




第二種方法是線段樹做法，這個要維護5顆線段樹，結構體裡面保存每個節點的個數，首先因為線段樹不支持插入，刪除，要維護一個個數cnt，當插入一個數的時候，你看原來%3的數，現在取余肯定等於2，那麼怎麼辦呢？？那麼這個cnt就起到了神奇的作用，每當插入刪除的時候就把相應的節點數變化，來維護那5棵線段樹。。最後因為沒有告訴數據范圍，所以要采取離散化，然後離線處理，最後得出所有要操作的總個數，然後依此建樹，第一次用離散化，覺得好高大上。。。
代碼：（參考自cxlove）
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define eps 1e-9
#define ll long long
#define INF 0x3f3f3f3f
using namespace std;
const int maxn=100000+10;
int n,a[maxn],b[maxn];
char op[maxn][5];

struct Tree
{
    int cnt;
    ll sum[5];
}tree[maxn<<2];

void buildtree(int l,int r,int dex)
{
    tree[dex].cnt=0;
    memset(tree[dex].sum,0,sizeof(tree[dex].sum));
    if(l==r)  return;
    int mid=(l+r)>>1;
    buildtree(l,mid,dex<<1);
    buildtree(mid+1,r,dex<<1|1);
}

void push_up(int dex)
{
    for(int i=0;i<5;i++)
        tree[dex].sum[i]=tree[dex<<1].sum[i]+tree[dex<<1|1].sum[((i-tree[dex<<1].cnt)%5+5)%5];
}

void update(int l,int r,int dex,int pos,int flag,int val)
{
    tree[dex].cnt+=flag;
    if(l==r)
    {
        if(flag==1)
           tree[dex].sum[1]=val;
        else
           tree[dex].sum[1]=0;
        return;
    }
    int mid=(l+r)>>1;
    if(pos<=mid)  update(l,mid,dex<<1,pos,flag,val);
    else update(mid+1,r,dex<<1|1,pos,flag,val);
    push_up(dex);
}

int main()
{
    int tot,pos,flag;
    while(~scanf("%d",&n))
    {
        tot=0;
        for(int i=1;i<=n;i++)
        {
            scanf("%s",op[i]);
            if(op[i][0]!='s')
            {
                scanf("%d",&b[i]);
                a[tot++]=b[i];
            }
        }
        sort(a,a+tot);
        tot=unique(a,a+tot)-a;
        if(tot==0)  memset(tree[1].sum,0,sizeof(tree[1].sum));
        else buildtree(1,tot,1);
        for(int i=1;i<=n;i++)
        {
            pos=lower_bound(a,a+tot,b[i])-a;
            pos++;
            if(op[i][0]=='a')
            {
                flag=1;
                update(1,tot,1,pos,flag,b[i]);
            }
            else if(op[i][0]=='d')
            {
                flag=-1;
                update(1,tot,1,pos,flag,b[i]);
            }
            else
                printf("%I64d\n",tree[1].sum[3]);
        }
    }
    return 0;
}