程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> ZOJ 3765 Lights Splay Tree的幾種基本操作

ZOJ 3765 Lights Splay Tree的幾種基本操作

編輯：C++入門知識

區間的查詢，點修改，插入和刪除。先姑且當作模板吧，略挫，慢慢補充，慢慢優化。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

#pragma comment(linker, "/STACK:1024000000");
#define EPS (1e-8)
#define LL long long
#define ULL unsigned long long
#define _LL __int64
#define _INF 0x3f3f3f3f
#define Mod 9999991

using namespace std;

const int MAXN = 700100;

struct N
{
    //info
    int son[2],pre;

    //data
    int sta,ls,rs,s;
    int w,g[2];
    bool mark[2];

}st[MAXN];

struct W
{
    int sta,w;
}num[200100];

void Output(int root)
{
    if(root == -1)
        return ;
    Output(st[root].son[0]);
    printf("root = %d pre = %d data = %2d lg = %2d rg = %2d sta = %2d ls = %d rs = %d s = %d\n",root,st[root].pre,st[root].w,st[root].g[0],st[root].g[1],st[root].sta,st[root].ls,st[root].rs,st[root].s);
    Output(st[root].son[1]);
}

int Top;

int Gcd(int a,int b)
{
    int t;

    while(b)
    {
        t = a;
        a = b;
        b = t%b;
    }
    return a;
}

//更新st[root]的數據域
void Updata(int root)
{
    st[root].ls = 0,st[root].rs = 0;

    st[root].g[st[root].sta] = st[root].w;
    st[root].g[1^st[root].sta] = 1;
    st[root].mark[st[root].sta] = true;
    st[root].mark[1^st[root].sta] = false;

    if(st[root].son[0] != -1)
    {
        if(st[root].mark[0] == true)
            st[root].g[0] = (st[st[root].son[0]].mark[0] ?  Gcd(st[root].g[0],st[st[root].son[0]].g[0]) : st[root].g[0]);
        else
            st[root].g[0] = st[st[root].son[0]].g[0];
        if(st[root].mark[1] == true)
            st[root].g[1] = (st[st[root].son[0]].mark[1] ?  Gcd(st[root].g[1],st[st[root].son[0]].g[1]) : st[root].g[1]);
        else
            st[root].g[1] = st[st[root].son[0]].g[1];

        st[root].mark[0] = (st[root].mark[0] || st[st[root].son[0]].mark[0]);
        st[root].mark[1] = (st[root].mark[1] || st[st[root].son[0]].mark[1]);
        st[root].ls = st[st[root].son[0]].s;
    }

    if(st[root].son[1] != -1)
    {
        if(st[root].mark[0] == true)
            st[root].g[0] = (st[st[root].son[1]].mark[0] ?  Gcd(st[root].g[0],st[st[root].son[1]].g[0]) : st[root].g[0]);
        else
            st[root].g[0] = st[st[root].son[1]].g[0];
        if(st[root].mark[1] == true)
            st[root].g[1] = (st[st[root].son[1]].mark[1] ?  Gcd(st[root].g[1],st[st[root].son[1]].g[1]) : st[root].g[1]);
        else
            st[root].g[1] = st[st[root].son[1]].g[1];

        st[root].mark[0] = (st[root].mark[0] || st[st[root].son[1]].mark[0]);
        st[root].mark[1] = (st[root].mark[1] || st[st[root].son[1]].mark[1]);
        st[root].rs = st[st[root].son[1]].s;
    }

    st[root].s = st[root].ls + st[root].rs + 1;
}

void Init(int &root,int s,int e,int pre)
{
    if(s > e)
        return ;

    int mid = (s+e)>>1;

    root = Top++;
    st[root].w = num[mid].w;
    st[root].sta = num[mid].sta;

    st[root].pre = pre;
    st[root].son[0] = st[root].son[1] = -1;

    Init(st[root].son[0],s,mid-1,root);
    Init(st[root].son[1],mid+1,e,root);

    Updata(root);
}

//dir == 0,root為pre的左兒子，dir == 1時為右兒子。
void Rotate(int root,int dir)
{
    //旋轉操作
    st[st[root].pre].son[dir] = st[root].son[1^dir];
    st[root].son[1^dir] = st[root].pre;

    if(st[st[st[root].pre].pre].son[0] == st[root].pre)
        st[st[st[root].pre].pre].son[0] = root;
    else
        st[st[st[root].pre].pre].son[1] = root;
    int temp = st[root].pre;
    st[root].pre = st[st[root].pre].pre;
    st[temp].pre = root;

    if(st[temp].son[dir] != -1)
        st[st[temp].son[dir]].pre = temp;

    //更新數據域
    Updata(temp);
    Updata(root);
}

//將root旋轉到goal下面,goal == 0時即表示將root旋轉至根節點位置。
int Splay(int root,int goal)
{
    while(st[root].pre != goal)
    {
        Rotate(root,(st[st[root].pre].son[0] == root ? 0 : 1));
    }

    return root;
}

int Search_Site(int root,int site)
{
    while(st[root].ls + 1 != site)
    {
        if(st[root].ls + 1 < site)
        {
            site = site - st[root].ls - 1;
            root = st[root].son[1];
        }
        else
        {
            root = st[root].son[0];
        }
    }

    return root;
}

void Increase(int root,int site,int w,int sta,int &R)
{
    root = Search_Site(root,site);

    R = Splay(root,0);

    //在根節點的右子樹的最左邊插入一個點

    int tr = st[R].son[1];
    st[R].son[1] = -1;

    int New = Top++;

    st[New].w = w;
    st[New].sta = sta;

    st[New].pre = 0;
    st[0].son[0] = New;
    st[R].pre = New;
    st[New].son[0] = R;
    st[tr].pre = New;
    st[New].son[1] = tr;

    Updata(R);
    Updata(New);
    R = New;
}

void Link(int &root,int tr,int pre)
{
    if(root == -1)
    {
        root = tr;
        st[root].pre = pre;
    }
    else
    {
        Link(st[root].son[1],tr,root);
    }
    Updata(root);
}

//不存在刪除所有節點的情況
void Decrease(int root,int site,int &R)
{
    root = Search_Site(root,site);
    //Output(R);
   // printf("D site = %d root = %d R = %d\n",site,root,R);

    R = Splay(root,0);
    //刪除根節點

    R = st[root].son[0];
    st[R].pre = st[root].pre;
    st[0].son[0] = R;
    int tr = st[root].son[1];

    //將tr接到R的最右邊。

    Link(R,tr,root);
    Updata(R);
}

void Reinit(int root,int site,int &R)
{
    root = Search_Site(root,site);

    R = Splay(root,0);

    st[R].sta ^= 1;
    Updata(R);
}

void Modify(int root,int site,int w,int &R)
{
    root = Search_Site(root,site);

    R = Splay(root,0);

    st[R].w = w;
    Updata(R);
}

int Query(int root,int l,int r,int sta,int &R)
{
    int lsite = Search_Site(root,l);
    int rsite = Search_Site(root,r);

    R = Splay(rsite,0);

    R = Splay(lsite,0);

    if(st[st[R].son[1]].son[0] == -1 || st[st[st[R].son[1]].son[0]].mark[sta] == false)
        return -1;
    return st[st[st[R].son[1]].son[0]].g[sta];
}

int main()
{
    //freopen("data.txt","r",stdin);
    //freopen("dataout.txt","w",stdout);
    int n,m;

    int i;

    int root;

    while(scanf("%d %d",&n,&m) != EOF)
    {
        for(i = 2;i <= n+1; ++i)
        {
            scanf("%d %d",&num[i].w,&num[i].sta);
        }

       // cout<