2015年3月18日 星期三

2015/03/18 TIOJ 1836 . 遊戲 Game

/*
    樹套樹 (二維線段樹)

    結點要動態開
    而且 如果該節點只有一個子結點
    則把該節點省略
*/
// http://tioj.ck.tp.edu.tw/problems/1836
#include <iostream>
#include <cstdio>

using namespace std;

typedef long long ll;

#define INF (int)(2e9)

struct Node
{
    Node *l, *r, *c;
    int h, t; ll gcd;

    Node(){ l = r = c = NULL; gcd = 0; }
    Node(int _h, int _t)
    {
        l = r = c = NULL;
        h = _h; t = _t; gcd = 0;
    }
};

Node *root;

ll GCD(ll a, ll b)
{
    while( a && b )
    {
        if( a < b ) swap(a, b);
        a %= b;
    }

    return a+b;
}

void pull(Node *O)
{
    if( !O->l || !O->r )
        O->gcd = O->l ? O->l->gcd : O->r->gcd;
    else
        O->gcd = GCD(O->l->gcd, O->r->gcd);
}

bool is_left(Node *O, Node *P)
{
    if( P->t <= (O->h+O->t)/2 && O->h <= P->h ) return true;
    else return false;
}

bool cover(Node *O, Node *P)
{
    if( !P ) return true;
    if( !O ) return false;

    if( O->h <= P->h && P->t <= O->t ) return true;
    else return false;
}

bool overlap(Node *O, Node *P)
{
    if( !O ) return false;

    if( P->t <= O->h || O->t <= P->h ) return false;
    else return true;
}

void modify(Node *O, int A, ll x)
{

    if( O->h+1 == O->t )
    {
        O->gcd = x;
        return;
    }

    Node tmp = Node(A, A+1);
    Node *P = is_left(O, &tmp) ? O->l : O->r;

    int l = O->h, r = O->t;

    while( l+1 != r )
    {
        int mid = (l+r)/2;

        Node lc = Node(l, mid);
        Node rc = Node(mid, r);

        if( cover(&lc, &tmp) && cover(&lc, P) ) r = mid;
        if( cover(&rc, &tmp) && cover(&rc, P) ) l = mid;

        if( l != mid && mid != r ) break;
    }

    if( P && P->h == l && P->t == r ) modify(P, A, x);
    else
    {
        P = new Node(l, r);

        if( is_left(O, &tmp) )
        {
            if( O->l )
            {
                if( is_left(P, O->l) ) P->l = O->l;
                else P->r = O->l;
            }

            O->l = P;
        }
        else
        {
            if( O->r )
            {
                if( is_left(P, O->r) ) P->l = O->r;
                else P->r = O->r;
            }

            O->r = P;
        }

        modify(P, A, x);
    }

    pull(O);
}

ll ask(Node *O, int A, int B)
{
    if( A <= O->h && O->t <= B ) return O->gcd;
    else
    {
        Node tmp = Node(A, B);

        ll re = 0;

        if( overlap(O->l, &tmp) ) re = GCD(re, ask(O->l, A, B));
        if( overlap(O->r, &tmp) ) re = GCD(re, ask(O->r, A, B));

        return re;
    }
}

ll ask(Node *O, int A, int B, int C, int D)
{
    if( A <= O->h && O->t <= B )
    {
        Node tmp = Node(C, D);

        ll re = 0;

        if( overlap(O->c, &tmp) ) re = GCD(re, ask(O->c, C, D));

        return re;
    }
    else
    {
        Node tmp = Node(A, B);

        ll re = 0;

        if( overlap(O->l, &tmp) ) re = GCD(re, ask(O->l, A, B, C, D));
        if( overlap(O->r, &tmp) ) re = GCD(re, ask(O->r, A, B, C, D));

        return re;
    }
}


void modify(Node *O, int A, int B, ll x)
{
    if( O->h+1 == O->t )
    {
        if( !O->c ) O->c = new Node(0, INF);
        modify(O->c, B, x);
    }
    else
    {
        Node tmp = Node(A, A+1);

        Node lc = Node(O->h, (O->h+O->t)/2);
        Node rc = Node((O->h+O->t)/2, O->t);

        if( overlap(&lc, &tmp) )
        {
            if( !O->l ) O->l = new Node(O->h, (O->h+O->t)/2);
            modify(O->l, A, B, x);
        }
        if( overlap(&rc, &tmp) )
        {
            if( !O->r ) O->r = new Node((O->h+O->t)/2, O->t);
            modify(O->r, A, B, x);
        }

        ll val = 0;
        val = GCD(val, ask(O, O->h, (O->h+O->t)/2, B, B+1) );
        val = GCD(val, ask(O, (O->h+O->t)/2, O->t, B, B+1));

        if( !O->c ) O->c = new Node(0, INF);
        modify(O->c, B, val);
    }

}


int N;

int main()
{
    root = new Node(0, INF);

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

    while( N-- )
    {
        int i;
        scanf("%d", &i);

        if( i == 1 )
        {
            ll P, Q, K;
            scanf("%lld %lld %lld", &P, &Q, &K);

            modify(root, P, Q, K);
        }
        if( i == 2 )
        {
            ll P, Q, U, V;
            scanf("%lld %lld %lld %lld", &P, &Q, &U, &V);

            if( P > U ) swap(P, U);
            if( Q > V ) swap(Q, V);

            U++; V++;

            printf("%lld\n", ask(root, P, U, Q, V));
        }

    }
}

沒有留言:

張貼留言