[SCOI2014]方伯伯的OJ——Splay

[SCOI2014]方伯伯的OJ——Splay

题面

　　Bzoj3595

解析

　　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("%dn", res);}return 0;
}

转载于:.html