2015年2月5日 星期四

2015/02/05 POJ 3580 SuperMemo

/*
    note: 
    1.push 以後放函數開頭比較好
    2.確保對於有flag的點 調用small等 依舊是正確的答案
    3.我終於發現為啥用g++會RE了 不應該把time回傳值丟到srand裡的
*/
// http://poj.org/problem?id=3580
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <ctime>

using namespace std;

#define INF (int)(2e9)

struct Node
{
    Node *l, *r;
    int pri, num, small, size;
    bool reverse;
    int add;

    Node(int _num = 0)
    {
        l = r = NULL;
        pri = rand();
        num = _num;
        small = num;
        size = 1;
        reverse = false;
        add = 0;
    }
};

Node *root;

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

int small(Node *O)
{
    return O ? O->small+O->add : INF ;
}

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

    if( O->reverse )
    {
        swap(O->l, O->r);

        if( O->l ) O->l->reverse ^= 1;
        if( O->r ) O->r->reverse ^= 1;

        O->reverse = false;
    }

    if( O->add )
    {
        O->num += O->add;

        if( O->l ) O->l->add += O->add;
        if( O->r ) O->r->add += O->add;

        O->add = 0;
    }
}

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

    O->size = size(O->l)+size(O->r)+1;
    O->small = min(min(small(O->l), small(O->r)), O->num);
    return;
}

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

void split(Node *O, Node *&a, Node *&b, int k)
{
    push(O);

    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 add(int x, int y, int d)
{
    Node *m1, *m2, *m3;
    split(root, m2, m3, y);
    split(m2, m1, m2, x-1);
    m2->add += d;
    root = merge(merge(m1, m2), m3);
}

void reverse(int x, int y)
{
    Node *m1, *m2, *m3;
    split(root, m2, m3, y);
    split(m2, m1, m2, x-1);
    m2->reverse ^= 1;
    root = merge(merge(m1, m2), m3);
}

void rotate(int x, int y, int t)
{
    int n = y-x+1;
    t = (t%n+n)%n;
    Node *m1, *m2, *m3, *m4, *m5;
    split(root, m2, m3, y);
    split(m2, m1, m2, x-1);

    split(m2, m4, m5, size(m2)-t);
    root = merge(merge(m1, m5), merge(m4, m3));
}

void insert(int x, int p)
{
    Node *m1, *m2;
    split(root, m1, m2, x);
    root = merge(merge(m1, new Node(p)), m2);
}

void erase(int x)
{
    Node *m1, *m2, *m3;
    split(root, m2, m3, x);
    split(m2, m1, m2, x-1);
    root = merge(m1, m3);
}

int small(int x, int y)
{
    Node *m1, *m2, *m3;
    split(root, m2, m3, y);
    split(m2, m1, m2, x-1);
    int Ans = m2->small;
    root = merge(merge(m1, m2), m3);
    return Ans;
}

int N, M;

int main()
{
    srand(10513 );
    root = NULL;

    scanf("%d", &N);

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

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

    scanf("%d", &M);

    for(int Mi = 0; Mi < M; Mi++)
    {
        char cmd[10];
        scanf("%s", cmd);

        if( !strcmp(cmd, "ADD") )
        {
            int x, y, d;
            scanf("%d %d %d", &x, &y, &d);
            add(x, y, d);

        }

        if( !strcmp(cmd, "REVERSE") )
        {
            int x, y;
            scanf("%d %d", &x, &y);
            reverse(x, y);
        }

        if( !strcmp(cmd, "REVOLVE") )
        {
            int x, y, t;
            scanf("%d %d %d", &x, &y, &t);
            rotate(x, y, t);
        }

        if( !strcmp(cmd, "INSERT") )
        {
            int x, y;
            scanf("%d %d", &x, &y);
            insert(x, y);
        }

        if( !strcmp(cmd, "DELETE") )
        {
            int x;
            scanf("%d", &x);
            erase(x);
        }

        if( !strcmp(cmd, "MIN") )
        {
            int x, y;
            scanf("%d %d", &x, &y);
            printf("%d\n", small(x, y));
        }


    }
}

沒有留言:

張貼留言