2015年1月5日 星期一

Codechef January Challenge 2015 Xor Queries

/*
    另ㄧ種形式的線段樹
    權值樹。。。。
 
    是說要寫 持久化線段樹啊。。。
    ㄧ開始要寫 線段樹 套 Treap
    只是複雜度不給過。。。

    所有的操作都要是 lgN
    再次挑戰自己的極限啊
    真是好樣的。。。
*/
#include <iostream>
#include <cstdio>

using namespace std;

#define up_bound 524288

struct Node
{
    Node *l, *r;
    int num;
    Node(int _num = 0){ l = r = NULL; num = _num; }
};

Node www[10000000]; int clk = 0;
Node *root[600000];

int num(Node *t)
{
    return t ? t->num : 0 ;
}

void pull(Node *t)
{
    t->num = num(t->l)+num(t->r);
}

void build(Node *&t, int L, int R)
{
    t = &www[++clk];
    *t = Node();

    if( L+1 == R ) return;

    build(t->l, L, (L+R)/2);
    build(t->r, (L+R)/2, R);
}

Node* add(Node *t, int L, int R, int A, int B, int x = 1)
{
    if( B <= L || R <= A ) return t;
    else if( A <= L && R <= B )
    {
        Node *re = &www[++clk];
        *re = Node(t->num+x);
        return re;
    }
    else
    {
        Node *re = &www[++clk];
        *re = Node();

        re->l = add(t->l, L, (L+R)/2, A, B, x);
        re->r = add(t->r, (L+R)/2, R, A, B, x);
        pull(re);
        return re;
    }
}

int kth(Node *t, Node *p, int L, int R, int k)
{
    if( L+1 == R ) return L;

    if( num(p->l) - num(t->l) >= k ) return kth(t->l, p->l, L, (L+R)/2, k);
    else return kth(t->r, p->r, (L+R)/2, R, k - num(p->l) + num(t->l) );
}

int ask(Node *t, Node *p, int L, int R, int A, int B)
{
    if( B <= L || R <= A ) return 0;
    else if( A <= L && R <= B ) return p->num - t->num;
    else
    {
        int v0 = ask(t->l, p->l, L, (L+R)/2, A, B);
        int v1 = ask(t->r, p->r, (L+R)/2, R, A, B);
        return v0+v1;
    }
}

int XOR(Node *t, Node *p, int L, int R, int x, int val)
{
    if( L+1 == R ) return L;

    if( x&val )
    {
        if( num(p->l) - num(t->l) ) return XOR(t->l, p->l, L, (L+R)/2, x, val/2);
        else return XOR(t->r, p->r, (L+R)/2, R, x, val/2);
    }
    else
    {
        if( num(p->r) - num(t->r) ) return XOR(t->r, p->r, (L+R)/2, R, x, val/2);
        else return XOR(t->l, p->l, L, (L+R)/2, x, val/2);
    }
}

int now = 0;

int M;

int main()
{
    build(root[0], 0, up_bound);

    scanf("%d", &M);

    for(int Mi = 0; Mi < M; Mi++)
    {
        int sp;
        scanf("%d", &sp);

        if( sp == 0 )
        {
            int x;
            scanf("%d", &x);

            now++;
            root[now] = add(root[now-1], 0, up_bound, x, x+1);
        }
        if( sp == 1 )
        {
            int L, R, x;
            scanf("%d %d %d", &L, &R, &x);

            printf("%d", XOR(root[L-1], root[R], 0, up_bound, x, up_bound/2));
            puts("");
        }
        if( sp == 2 )
        {
            int k;
            scanf("%d", &k);
            now -= k;
        }
        if( sp == 3 )
        {
            int L, R, x;
            scanf("%d %d %d", &L, &R, &x);

            printf("%d", ask(root[L-1], root[R], 0, up_bound, 1, x+1));
            puts("");
        }
        if( sp == 4 )
        {
            int L, R, k;
            scanf("%d %d %d", &L, &R, &k);

            printf("%d", kth(root[L-1], root[R], 0, up_bound, k));
            puts("");
        }
    }
}

沒有留言:

張貼留言