2015年2月1日 星期日

2015/02/01 ZJ b278: 说话不算话的区间求和

/*
    持久化線段樹
*/
// http://zerojudge.tw/ShowProblem?problemid=b278
#include <iostream>
#include <cstdio>

using namespace std;

typedef long long ll;

struct Node
{
    Node *l, *r;
    ll num;

    Node(ll _num = 0){ l = r = NULL; num = _num; }
};

int N, T;
Node *root[600000];

void push(Node *O)
{
    O->num = O->l->num + O->r->num;
    return;
}

Node *build(int L, int R)
{
    Node *re = new Node();

    if( L+1 == R ) return re;

    re->l = build(L, (L+R)/2);
    re->r = build((L+R)/2, R);

    return re;
}

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

Node *change(Node *O, int L, int R, int A, int x)
{
    int B = A+1;

    if( B <= L || R <= A ) return O;
    else if( A <= L && R <= B )
    {
        Node *re = new Node(x);
        return re;
    }
    else
    {
        Node *re = new Node();
        re->l = change(O->l, L, (L+R)/2, A, x);
        re->r = change(O->r, (L+R)/2, R, A, x);

        push(re);
        return re;
    }
}

int main()
{
    scanf("%d %d", &N, &T);

    root[0] = build(1, N+1);

    for(int Ti = 1; Ti <= T; Ti++)
    {
        int kd;
        scanf("%d", &kd);

        if( kd == 0 )
        {
            int k;
            scanf("%d", &k);

            root[Ti] = root[Ti-k-1];
        }
        if( kd == 1 )
        {
            int x, v;
            scanf("%d %d", &x, &v);

            root[Ti] = change(root[Ti-1], 1, N+1, x, v);
        }
        if( kd == 2 )
        {
            int x, y;
            scanf("%d %d", &x, &y);

            root[Ti] = root[Ti-1];
            printf("%lld\n", ask(root[Ti], 1, N+1, x, y+1));
        }
    }
}

沒有留言:

張貼留言