zoj 3765 Lights（Splay）

                  由于数组开小了，一直TLE。。。检查了一下午，都要哭了，题目没啥好说的，就是一个入门级别的Splay Tree。只有插入，删除，修改操作。

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#define LL long long
#define CLR(a, b) memset(a, b, memset(a))
using namespace std;
const int N = 300100;
const int INF = 0x7FFFFFFF;

int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;
}

struct SplayTree
{
    int size, root, top;
    int st[N], a[N];
    int ch[N][2], pre[N], key[N], num[N];
    int gcd1[N], gcd0[N];
    bool light[N], b[N];
    inline void PushUp(int x)
    {
        num[x] = num[ch[x][0]] + num[ch[x][1]] + 1;
        gcd0[x] = gcd(gcd0[ch[x][0]], gcd0[ch[x][1]]);
        gcd1[x] = gcd(gcd1[ch[x][0]], gcd1[ch[x][1]]);
        if(!light[x]) gcd0[x] = gcd(gcd0[x], key[x]);
        else gcd1[x] = gcd(gcd1[x], key[x]);
    }
    void NewNode(int &x, int father, int val, bool status)
    {
        if(top != -1)
            x = st[top --];
        else
            x = ++size;
        ch[x][0] = ch[x][1] = gcd0[x] = gcd1[x] = 0;
        if(status) gcd1[x] = val;
        else gcd0[x] = val;///这个初始化很必要。
        pre[x] = father;
        key[x] = val;
        light[x] = status;
        num[x] = 1;
    }
    void Build(int &x, int L, int R, int father)
    {
        if(L <= R)
        {
            int mid = (L + R) >> 1;
            NewNode(x, father, a[mid], b[mid]);
            Build(ch[x][0], L, mid - 1, x);
            Build(ch[x][1], mid + 1, R, x);
            PushUp(x);
        }
    }
    void Init(int n)
    {
        root = size = 0;
        top = -1;
        ch[0][0] = ch[0][1] = pre[0] = num[0] = 0;
        key[0] = gcd0[0] = gcd1[0] = 0;
        NewNode(root, 0, 0, 0);
        NewNode(ch[root][1], root, 0, 0);
        Build(ch[ch[root][1]][0], 1, n, ch[root][1]);
        PushUp(ch[root][1]);
        PushUp(root);
    }
    void Rotate(int x, int kind)
    {
        int y = pre[x];
        //PushDown(x);
        ch[y][!kind] = ch[x][kind];
        pre[ch[x][kind]] = y;
        if(pre[y])
            ch[pre[y]][ch[pre[y]][1] == y] = x;
        pre[x] = pre[y];
        ch[x][kind] = y;
        pre[y] = x;
        PushUp(y);
    }
    void Splay(int r, int goal)
    {
        while(pre[r] != goal)
        {
            if(pre[pre[r]] == goal) Rotate(r, ch[pre[r]][0] == r);
            else
            {
                int y = pre[r];
                int kind = ch[pre[y]][0] == y;
                if(ch[y][kind] == r)
                    Rotate(r, !kind), Rotate(r, kind);
                else
                    Rotate(y, kind), Rotate(r, kind);
            }
        }
        if(goal == 0) root = r;
    }
    int Select(int k)
    {
        int x;
        //PushDown(root);
        for(x = root; num[ch[x][0]] + 1 != k;)
        {
            if(num[ch[x][0]] + 1 > k)
                x = ch[x][0];
            else
                k -= num[ch[x][0]] + 1, x = ch[x][1];
            //PushDown(x);
        }
        return x;
    }
    void Insert(int x, int val, bool status)
    {//cout << x;
        //cout << " insert" << val <<" " << status << endl;
        int a, b;
        a = Select(x);
        b = Select(x + 1);
        Splay(a, 0);
        Splay(b, a);
        NewNode(ch[b][0], b, val, status);
        PushUp(b);
        PushUp(a);
    }
    void Delete(int x)
    {
        int a, b;
        a = Select(x - 1);
        b = Select(x + 1);
        Splay(a, 0);
        Splay(b, a);
        st[++ top] = ch[b][0];
        ch[b][0] = 0;
        PushUp(b);
        PushUp(a);
    }
    void Modify(int x, int val)
    {
        x = Select(x);
        Splay(x, 0);
        key[x] = val;
        PushUp(x);
    }
    void Reset(int x)
    {
        x = Select(x);
        Splay(x, 0);
        light[x] ^= true;
        PushUp(x);
    }
    int Query(int l, int r, bool status)
    {
        int a, b;
        a = Select(l - 1);
        b = Select(r + 1);
        Splay(a, 0);
        Splay(b, a);
        return status ? gcd1[ch[b][0]] : gcd0[ch[b][0]];
    }
} spt;

int main()
{
    int n, q, l, r, val;
    bool sta;
    char c[3];
    while(scanf("%d%d", &n, &q) != EOF)
    {
        for(int i = 1; i <= n; i ++)
            scanf("%d%d", &spt.a[i], &spt.b[i]);
        spt.Init(n);
        while(q --)
        {
            scanf("%s", c);
            if(c[0] == ‘Q‘)
                scanf("%d%d%d", &l, &r, &sta), val = spt.Query(l + 1, r + 1, sta), printf("%d\n", val ? val : -1);
            else if(c[0] == ‘I‘)
                scanf("%d%d%d", &l, &r, &sta), spt.Insert(l + 1, r, sta);
            else if(c[0] == ‘D‘)
                scanf("%d", &l), spt.Delete(l + 1);
            else if(c[0] == ‘R‘)
                scanf("%d", &l), spt.Reset(l + 1);
            else
                scanf("%d%d", &l, &val), spt.Modify(l + 1, val);
        }
    }
    return 0;
}

zoj 3765 Lights（Splay）,布布扣,bubuko.com

zoj 3765 Lights（Splay）

原文：http://blog.csdn.net/ok_again/article/details/20567195