Bzoj3595：[SCOI2014]方伯伯的OJ

题面

　　Bzoj

解析

　　wys讲到用Splay，但我又一次写成了Spaly

　　考虑到n的范围巨大而m的范围是正常的1e5，显然要动态开点，一个点代表一个区间。但这道题只用一棵平衡树可能不太好做，于是有dalao就写了两棵平衡树，显然我这种一棵平衡树都要写挂的人是不可能去完成两棵平衡树的，于是可以用map代替其中一棵树。其中map第一关键字为区间的右端点，第二关键字为节点编号，要分裂点的时候先查询分裂的节点，用lower_bound可以在log的时间内查到，再分裂节点就行，显然操作1、2、3需要分裂节点。

　　对于操作2，当然先是找到节点，然后旋转到根，查询前驱和后继，分情况讨论删除根，再把序列rk1转到根节点，把删除的节点挂在左二子上就行。操作3类似，删除根及其之前的操作都和操作2一样，只不过操作3要把rk last转到根节点，把删除的节点挂在右儿子上就行

　细节

　　分裂节点时分成了[l, val - 1], [val, val] [val + 1, r]三个区间，要注意判断[l, val - 1], [val + 1, r]两个区间是否存在

　　0号节点的右儿子要赋成root，删除节点时要更新（这个我调了2个小时）

　　代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn = 500005;

template<class T> void read(T &re)
{
    re=0;
    T sign=1;
    char tmp;
    while((tmp=getchar())&&(tmp<'0'||tmp>'9')) if(tmp=='-') sign=-1;
    re=tmp-'0';
    while((tmp=getchar())&&(tmp>='0'&&tmp<='9')) re=(re<<3)+(re<<1)+(tmp-'0');
    re*=sign;
}

int n, m, res, root, tot;
map<int,int> mp;

struct splay_tree{
    int l, r, s[2], fa, siz;
}tr[maxn];

int Newnode(int l, int r, int f)
{
    int ret = ++tot;
    tr[ret].l = l;
    tr[ret].r = r;
    tr[ret].fa = f;
    tr[ret].siz = r - l + 1;
    return ret;
}

void update(int x)
{
    int ls = tr[x].s[0], rs = tr[x].s[1];
    tr[x].siz = tr[ls].siz + tr[rs].siz + tr[x].r - tr[x].l + 1;
}

void Rotate(int x)
{
    int y = tr[x].fa, z = tr[y].fa, k = (tr[y].s[1] == x), w = (tr[z].s[1] == y), son = tr[x].s[k^1];
    tr[y].s[k] = son;tr[son].fa = y;
    tr[x].s[k^1] = y;tr[y].fa = x;
    tr[z].s[w] = x;tr[x].fa = z;
    update(y);update(x);
}

void Splay(int x, int to)
{
    while(tr[x].fa != to)
    {
        int y = tr[x].fa, z = tr[y].fa;
        if(z == to)
        {
            Rotate(x);
            break;
        }
        Rotate((tr[y].s[0] == x) ^ (tr[z].s[0] == y)? x: y); 
        Rotate(x);
    }
    if(!to)
        root = x;
}

int Find(int x)
{
    int now = root;
    while(1)
    {
        int ls = tr[now].s[0], rs = tr[now].s[1], sum = tr[ls].siz + tr[now].r - tr[now].l + 1;
        if(x > tr[ls].siz && x <= sum)
        {
            x -= tr[ls].siz;
            break;
        }
        if(x <= tr[ls].siz)     now = ls;
        else     x -= sum, now = rs;
    }
    return tr[now].l + x - 1;
}

void Split(int x, int val)
{
    int ls, rs, L = tr[x].l, R = tr[x].r;
    if(L == R)
        return ;
    if(L == val)
    {
        rs = ++tot;
        mp[R] = rs;
        mp[val] = x;
        tr[rs].s[1] = tr[x].s[1];
        tr[tr[rs].s[1]].fa = rs;
        tr[x].s[1] = rs;
        tr[rs].fa = x;
        tr[rs].l = L + 1;
        tr[rs].r = R;
        tr[x].r = L;
        update(rs);update(x);
    }
    else if(R == val)
    {
        ls = ++tot;
        mp[R - 1] = ls;
        mp[val] = x;
        tr[ls].s[0] = tr[x].s[0];
        tr[tr[x].s[0]].fa = ls;
        tr[x].s[0] = ls;
        tr[ls].fa = x;
        tr[ls].l = L;
        tr[ls].r = R - 1;
        tr[x].l = R;
        update(ls);update(x);
    }
    else
    {
        ls = ++tot; rs = ++tot;    
        mp[val] = x;
        mp[val-1] = ls;
        mp[R] = rs;
        tr[ls].s[0] = tr[x].s[0];
        tr[rs].s[1] = tr[x].s[1];
        tr[tr[x].s[0]].fa = ls;
        tr[tr[x].s[1]].fa = rs;
        tr[x].s[0] = ls;
        tr[x].s[1] = rs;
        tr[x].l = tr[x].r = val;
        tr[ls].fa = tr[rs].fa = x;
        tr[ls].l = L;
        tr[ls].r = val - 1;
        tr[rs].l = val + 1;
        tr[rs].r = R;
        update(ls);update(rs);update(x);
    }
    Splay(x, 0);
}

int Query(int x)
{
    Splay(x, 0);
    return tr[x].siz - tr[tr[x].s[1]].siz;
}
int timer;
void Del(int x)
{
    int pre = tr[x].s[0], las = tr[x].s[1];
    while(tr[pre].s[1])    pre = tr[pre].s[1];
    while(tr[las].s[0])    las = tr[las].s[0];
    if(!pre && !las)    root = 0;
    else if(!pre)
    {
        Splay(las, root);
        root = las;
        tr[root].fa = 0;
        tr[0].s[1] = root;
        tr[x].s[0] = tr[x].s[1] = 0;
        tr[x].siz = 1;
    }
    else if(!las)
    {
        Splay(pre, root);
        root = pre;
        tr[root].fa = 0;
        tr[0].s[1] = root;
        tr[x].s[0] = tr[x].s[1] = 0;
        tr[x].siz = 1;
    }
    else 
    {
        Splay(pre, 0);
        Splay(las, root);
        tr[las].s[0] = tr[x].fa = 0;
        tr[x].siz = 1;
        update(las);update(pre);
    }
}

void Insert_front(int x)
{
    if(!root)
    {
        root = x;
        return ;
    }
    int lef = root;
    while(tr[lef].s[0])    lef = tr[lef].s[0];
    Splay(lef, 0);
    tr[root].s[0] = x;
    tr[x].fa = root;
    update(root);
}

void Insert_back(int x)
{
    if(!root)
    {
        root = x;
        return ;
    }
    int rig = root;
    while(tr[rig].s[1])
        rig = tr[rig].s[1];
    Splay(rig, 0);
    tr[root].s[1] = x;
    tr[x].fa = root;
    update(x);
    update(root);
}

int main()
{
    read(n);read(m);
    mp[n] = root = Newnode(1, n, 0);
    tr[0].s[1] = root;
    for(int i = 1; i <= m; ++i)
    {
        
        timer ++;
        int opt, x, y;
        read(opt);read(x);
        if(opt == 1)
        {
            read(y);
            x -= res;
            y -= res;
            int z = mp.lower_bound(x) -> second;
            Split(z, x);
            res = Query(z);
            tr[z].l = tr[z].r = y;
            mp[y] = z;
        }
        else if(opt == 2)
        {
            x -= res;
            int y = mp.lower_bound(x) -> second;
            Split(y, x);
            res = Query(y);
            Del(y);
            Insert_front(y);
        }
        else if(opt == 3)
        {
            x -= res;
            int y = mp.lower_bound(x) -> second;
            Split(y, x);
            res = Query(y);
            Del(y);
            Insert_back(y);
        }
        else
        {
            x -= res;
            res = Find(x);
        }
        printf("%d\n", res);
    }
    return 0;
}

View Code

秒客网

Bzoj3595：[SCOI2014]方伯伯的OJ

相关文章