2015年2月10日 星期二

2015/02/10 某Treap題

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <ctime>

using namespace std;

struct Node
{
    Node *l, *r;
    int size, sum, num, pri;

    Node(int _num = 0)
    {
        l = r = NULL;
        size = 1;
        sum = num = _num;
        pri = rand()<<10 | rand();
    }
};

Node *root;

int size(Node *O){ return O ? O->size : 0 ; }
int sum(Node *O){ return O ? O->sum : 0 ; }

void pull(Node *O)
{
    if( !O ) return;

    O->size = size(O->l)+size(O->r)+1;
    O->sum = sum(O->l)+sum(O->r)+O->num;
}

Node* merge(Node *a, Node *b)
{
    if( !a || !b ) return a ? a : b;
    else if( a->pri >= b->pri )
    {
        a->r = merge(a->r, b);
        pull(a);
        return a;
    }
    else
    {
        b->l = merge(a, b->l);
        pull(b);
        return b;
    }
}

void split(Node *O, Node *&a, Node *&b, int k)
{
    if( !O ) a = b = NULL;
    else if( size(O->l)+1 <= k )
    {
        a = O;
        split(O->r, a->r, b, k-size(O->l)-1);
        pull(a);
    }
    else
    {
        b = O;
        split(O->l, a, b->l, k);
        pull(b);
    }
}

void cut(int l, int r)
{
    Node *s1, *s2, *s3;
    split(root, s2, s3, r);
    split(s2, s1, s2, l-1);
    root = merge(s2, merge(s1, s3));
}

int ask(int l, int r)
{
    Node *s1, *s2, *s3;
    split(root, s2, s3, r);
    split(s2, s1, s2, l-1);
    int Ans = s2->sum;
    root = merge(merge(s1, s2), s3);
    return Ans;
}

int T;
int N, M;

int main()
{
    srand(time(NULL) );

    scanf("%d", &T);

    while( T-- )
    {
        root = NULL;

        scanf("%d %d", &N, &M);

        for(int Ni = 0; Ni < N; Ni++)
        {
            int x;
            scanf("%d", &x);

            root = merge(root, new Node(x));
        }

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

            if( sp == 1 ) cut(l, r);
            else printf("%d\n", ask(l, r));
        }
    }
}

沒有留言:

張貼留言