HYSBZ 1269テキストエディタsplay
11454 ワード
基本的な操作を比較します.
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define INF 99999999
#define ll __int64
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define key_value ch[ch[root][1]][0]
using namespace std;
const int MAXN = 2200010;
int pre[MAXN],rev[MAXN],siz[MAXN],ch[MAXN][2],s[MAXN],tot1,tot2,root;
int n;
char a[MAXN],key[MAXN];
void Treavel(int x)
{
if(x)
{
Treavel(ch[x][0]);
printf(" %2d: %2d %2d %2d size=%2d key=%2c rev=%2d pre=%2d
",x,ch[x][0],ch[x][1],pre[x],siz[x],key[x],rev[x],pre[x]);
Treavel(ch[x][1]);
}
}
void debug()
{
printf("root:%d
",root);
Treavel(root);
}
void Newnode(int &rt,int pa,int k)
{
if(tot2){
rt = s[tot2--];
}
else {
rt = ++tot1;
}
pre[rt] = pa;
siz[rt] = 1;
key[rt] = k;
rev[rt] = 0;
ch[rt][0] = ch[rt][1] = 0;
}
void pushup(int rt)
{
siz[rt] = siz[ch[rt][0]] + siz[ch[rt][1]] + 1;
}
void updata_rev(int rt)
{
if(!rt)
return;
rev[rt] ^= 1;
swap(ch[rt][0],ch[rt][1]);
}
void pushdown(int rt)
{
if(rev[rt]){
updata_rev(ch[rt][0]);
updata_rev(ch[rt][1]);
rev[rt] = 0;
}
}
void build(int &rt,int l,int r,int pa)
{
if(l > r)
return ;
int m = (l+r)/2;
Newnode(rt,pa,a[m]);
build(ch[rt][0],l,m-1,rt);
build(ch[rt][1],m+1,r,rt);
pushup(rt);
}
void Init()
{
root = tot1 = tot2 = 0;
key[root] = pre[root] = rev[root] = siz[root] = 0;
ch[root][0] = ch[root][1] = 0;
Newnode(root,0,0);
Newnode(ch[root][1],root,0);
pushup(ch[root][1]);
pushup(root);
}
void Rotate(int rt,int kind)
{
int y = pre[rt];
pushdown(y);
pushdown(rt);
ch[y][!kind] = ch[rt][kind];
pre[ch[rt][kind]] = y;
if(pre[y]){
ch[pre[y]][ch[pre[y]][1]==y] = rt;
}
pre[rt] = pre[y];
ch[rt][kind] = y;
pre[y] = rt;
pushup(y);
}
void splay(int rt,int goal)
{
pushdown(rt);
while(pre[rt] != goal)
{
if(pre[pre[rt]] == goal){
pushdown(pre[rt]);
pushdown(rt);
Rotate(rt,ch[pre[rt]][0]==rt);
}
else {
pushdown(pre[pre[rt]]);
pushdown(pre[rt]);
pushdown(rt);
int y = pre[rt];
int kind = ch[pre[y]][0]==y;
if(ch[y][kind] == rt){
Rotate(rt,!kind);
Rotate(rt,kind);
}
else {
Rotate(y,kind);
Rotate(rt,kind);
}
}
}
if(goal == 0)
root = rt;
pushup(rt);
}
int Get_kth(int rt,int k)
{
pushdown(rt);
int t = siz[ch[rt][0]] + 1;
if(t == k){
return rt;
}
else if(t > k){
return Get_kth(ch[rt][0],k);
}
else {
return Get_kth(ch[rt][1],k-t);
}
}
int Get_next(int rt)
{
pushdown(rt);
int tmp = ch[rt][1];
while(ch[tmp][0]){
tmp = ch[tmp][0];
pushdown(tmp);
}
return tmp;
}
int Get_pre(int rt)
{
pushdown(rt);
int tmp = ch[rt][0];
while(ch[tmp][1]){
tmp = ch[tmp][1];
pushdown(tmp);
}
return tmp;
}
void erase(int rt)
{
if(!rt)
return;
s[++tot2] = rt;
erase(ch[rt][0]);
erase(ch[rt][1]);
}
int main()
{
int i,j;
while(~scanf("%d",&n))
{
Init();
char c[20];
//debug();
while(n--)
{
scanf("%s",c);
if(c[0] == 'I'){
int len;
scanf("%d",&len);
getchar();
gets(a);
splay(Get_next(root),root);
build(key_value,0,len-1,ch[root][1]);
pushup(ch[root][1]);
pushup(root);
//debug();
}
else if(c[0] == 'D'){
int x;
scanf("%d",&x);
int ret = siz[ch[root][0]] + 1;
splay(Get_kth(root,ret+x+1),root);
erase(key_value);
pre[key_value] = 0;
key_value = 0;
pushup(ch[root][1]);
pushup(root);
//debug();
}
else if(c[0] == 'R'){
int x;
scanf("%d",&x);
int ret = siz[ch[root][0]] + 1;
splay(Get_kth(root,ret+x+1),root);
updata_rev(key_value);
pushup(ch[root][1]);
pushup(root);
//debug();
}
else if(c[0] == 'G'){
printf("%c
",key[Get_next(root)]);
}
else if(c[0] == 'M'){
int x;
scanf("%d",&x);
splay(Get_kth(root,x+1),0);
//debug();
}
else if(c[0] == 'P'){
splay(Get_pre(root),0);
//debug();
}
else {
splay(Get_next(root),0);
//debug();
}
}
}
}