F.A.QsWeb BoardHomeProblemSetStatusRanklistContestModifyUser???yejinru(0)Logout捐贈(zèng)本站 Notice:祝大家新年快樂(lè)！

1269: [AHOI2006]文本編輯器editor

Time Limit:?10 Sec??Memory Limit:?162 MB
Submit:?921??Solved:?320
[Submit][Status][Discuss]

Description

這些日子，可可不和卡卡一起玩了，原來(lái)可可正廢寢忘食的想做一個(gè)簡(jiǎn)單而高效的文本編輯器。你能幫助他嗎？為了明確任務(wù)目標(biāo)，可可對(duì)“文本編輯器”做了一個(gè)抽象的定義：???文本：由0個(gè)或多個(gè)字符構(gòu)成的序列。這些字符的ASCII碼在閉區(qū)間[32, 126]內(nèi)，也就是說(shuō)，這些字符均為可見(jiàn)字符或空格。光標(biāo)：在一段文本中用于指示位置的標(biāo)記，可以位于文本的第一個(gè)字符之前，文本的最后一個(gè)字符之后或文本的某兩個(gè)相鄰字符之間。文本編輯器：為一個(gè)可以對(duì)一段文本和該文本中的一個(gè)光標(biāo)進(jìn)行如下七條操作的程序。如果這段文本為空，我們就說(shuō)這個(gè)文本編輯器是空的。 編寫一個(gè)程序：? 建立一個(gè)空的文本編輯器。? 從輸入文件中讀入一些操作指令并執(zhí)行。? 對(duì)所有執(zhí)行過(guò)的GET操作，將指定的內(nèi)容寫入輸出文件。

Input

輸入文件中第一行是指令條數(shù)N，以下是需要執(zhí)行的N個(gè)操作。除了回車符之外，輸入文件的所有字符的ASCII碼都在閉區(qū)間[32, 126]內(nèi)。且行尾沒(méi)有空格。

Output

依次對(duì)應(yīng)輸入文件中每條GET指令的輸出，不得有任何多余的字符。

Sample Input

10
Insert 13
Balanced eert
Move 2
Delete 5
Next
Insert 7
editor
Move 0
Get
Move 11
Rotate 4
Get

Sample Output

B
t

HINT

?

對(duì)輸入數(shù)據(jù)我們有如下假定：? MOVE操作不超過(guò)50 000個(gè)，INSERT、DELETE和ROTATE操作作的總個(gè)數(shù)不超過(guò)6 000，GET操作不超過(guò)20 000個(gè)，PREV和NEXT操作的總個(gè)數(shù)不超過(guò)20 000。? 所有INSERT插入的字符數(shù)之和不超過(guò)2M（1M=1 024*1 024）。? DELETE操作、ROTATE操作和GET操作執(zhí)行時(shí)光標(biāo)后必然有足夠的字符。MOVE、PREV、NEXT操作不會(huì)把光標(biāo)移動(dòng)到非法位置。? 輸入文件沒(méi)有錯(cuò)誤。

?

Source

鳴謝seter重新制作數(shù)據(jù)

[Submit][Status][Discuss]

HOME?Back

---

?????中文?????????English??????
版權(quán)所有 ?2008-2012 大視野在線測(cè)評(píng) |?站長(zhǎng)統(tǒng)計(jì) Based on opensource project?hustoj.

?

分析：splay的基本操作。
1.插入，我們需要把插入的位置伸展到根，然后再把伸展之后的后一個(gè)位置伸展到根的右兒子，插入就直接把所有的數(shù)插入到根的右兒子的左子樹(shù)中。
2.刪除，我們把需要?jiǎng)h除的整個(gè)區(qū)間[a,b]直接伸展到根的右兒子的左子樹(shù)，即把a(bǔ)-1伸展到根，把b+1伸展到根的右兒子，然后把根的右兒子的左子樹(shù)整個(gè)刪除掉即可
3.旋轉(zhuǎn)，lazy標(biāo)記，每當(dāng)我們往下遍歷的時(shí)候，需要把lazy標(biāo)記下沉。而旋轉(zhuǎn)過(guò)程中，比如我們需要對(duì)區(qū)間[a,b]旋轉(zhuǎn)，我們可以把a(bǔ)-1旋轉(zhuǎn)到根，把b+1旋轉(zhuǎn)到根的右兒子，然后把根的右兒子的左子樹(shù)的標(biāo)記翻轉(zhuǎn)一下就行了。
4.輸出，我們需要輸出光標(biāo)后的第一個(gè)字符，我們可以直接把光標(biāo)的位置伸展到根，然后再求根的右兒子的最小值輸出
5.移動(dòng)到第k個(gè)字符后面，我們直接把光標(biāo)改變，無(wú)需把該位置伸展到根，只需要用的時(shí)候再進(jìn)行伸展操作
6.前移（后移），直接把光標(biāo)減一（加一），無(wú)需進(jìn)行伸展操作

對(duì)于這題來(lái)說(shuō)，插入的時(shí)候需要把插入的字符串遞歸構(gòu)造一個(gè)成一個(gè)perfect tree來(lái)插入。

?

#include <set> #include <map> #include <cmath> #include <queue> #include <stack> #include <string> #include <vector> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm>using namespace std;typedef long long ll; typedef unsigned long long ull;#define debug puts("here") #define rep(i,n) for(int i=0;i<n;i++) #define foreach(i,vec) for(unsigned i=0;i<vec.size();i++) #define pb push_backint tot,root,pos;namespace Splay{#define lx ch[x][0] #define rx ch[x][1] #define px pre[x]#define ly ch[y][0] #define ry ch[y][1] #define py pre[y]#define lz ch[z][0] #define rz ch[z][1] #define pz pre[z]#define rt ch[root][1] #define lrt ch[rt][0]const int X = (1<<21)+5;int ch[X][2],pre[X],sz[X],rev[X];char str[X];char qq[X];inline void dfs(int x){if(x){dfs(lx);cout<<lx<<" "<<rx<<" "<<x<<endl;dfs(rx);}}inline void update(int x){//cout<<lx<<" "<<rx<<" "<<sz[lx]<<" "<<sz[rx]<<" "<<sz[lx]+sz[rx]+1<<endl;sz[x] = sz[lx]+sz[rx]+1;}inline void push_down(int x){if(x&&rev[x]){swap(lx,rx);rev[lx] ^= 1;rev[rx] ^= 1;rev[x] = 0;}}inline void new_node(int &x,int y,char c){x = ++tot;pre[x] = y;rev[x] = ch[x][0] = ch[x][1] = 0;str[x] = c;}inline void build(int &x,int l,int r,int y,char *s){if(l>r) return;int mid = (l+r)>>1;new_node(x,y,s[mid]);build(lx,l,mid-1,x,s);build(rx,mid+1,r,x,s);update(x);}inline void setc(int y,int d,int x){ch[y][d] = x;pre[x] = y;}inline int sgn(int x){return ch[px][1]==x;}inline void _rot(int x,int d){int y = px;int z = py;push_down(y);push_down(x);setc(y,!d,ch[x][d]);if(z) setc(z,sgn(y),x);pre[x] = z;setc(x,d,y);update(y);}inline void rot(int x){_rot(x,!sgn(x));}inline void zag(int x){_rot(x,0);}inline void zig(int x){_rot(x,1);}inline int splay(int x,int goal=0){push_down(x);while(px!=goal){int y = px;int z = py;if(z==goal){rot(x);break;}if(lz==y){if(ly==x)zig(y),zig(x);elsezag(x),zig(x);}else{if(ry==x)zag(y),zag(x);elsezig(x),zag(x);}}update(x);if(goal==0)root = x;return x;}inline int get_Kth(int x,int k){push_down(x);int tmp = sz[lx]+1;if(tmp==k)return x;if(k<tmp)return get_Kth(lx,k);elsereturn get_Kth(rx,k-tmp);}inline int get_min(int x){push_down(x);while(lx){x = lx;push_down(x);}return x;}inline void Move(){int k;scanf("%d",&k);pos = k+1;}inline void Insert(){int k;scanf("%d",&k);getchar();gets(qq);int x = get_Kth(root,pos);splay(x);x = get_min(rt);splay(x,root);build(lrt,0,k-1,rt,qq);}inline void Delete(){int k;scanf("%d",&k);int x = get_Kth(root,pos);splay(x);int y = get_Kth(root,pos+k+1);splay(y,root);pre[lrt] = 0;lrt = 0;update(rt);update(root);}inline void Rotate(){int k;scanf("%d",&k);int x = get_Kth(root,pos);splay(x);int y = get_Kth(root,pos+k+1);splay(y,root);rev[lrt] ^= 1;}inline void Get(){int x = get_Kth(root,pos);splay(x);x = get_min(rt);printf("%c\n",str[x]);}inline void Prev(){pos --;}inline void Next(){pos ++;}inline void init(){memset(pre,0,sizeof(pre));memset(ch,0,sizeof(ch));memset(sz,0,sizeof(sz));memset(rev,0,sizeof(rev));root = tot = 0;char s[] = "@@@@@@";build(root,0,5,0,s);pos = 1;}}using namespace Splay;int main(){#ifndef ONLINE_JUDGEfreopen("sum.in","r",stdin);//freopen("sum.out","w",stdout); #endifint ncase;char op[20];cin>>ncase;init();while(ncase--){scanf("%s",op);switch(op[0]){case 'M':Move();break;case 'I':Insert();break;case 'D':Delete();break;case 'R':Rotate();break;case 'G':Get();break;case 'P':Prev();break;default:Next();}}return 0; }

　　

轉(zhuǎn)載于:https://www.cnblogs.com/yejinru/archive/2013/02/10/2909797.html

總結(jié)

以上是生活随笔為你收集整理的BZOJ 1269: [AHOI2006]文本编辑器editor Splay的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。