1269: [AHOI2006]文本編輯器editor
Time Limit: 10 Sec Memory Limit: 162 MBSubmit: 2678 Solved: 996
[Submit][Status][Discuss]
Description
這些日子，可可不和卡卡一起玩了，原來可可正廢寢忘食的想做一個簡單而高效的文本編輯器，
bzoj1269[AHOI2006]文本編輯器editor
。你能幫助他嗎？為了明確任務目標，可可對“文本編輯器”做了一個抽象的定義：文本：由0個或多個字符構成的序列。這些字符的ASCII碼在閉區間[32, 126]內，也就是說，這些字符均為可見字符或空格。光標：在一段文本中用于指示位置的標記，可以位于文本的第一個字符之前，文本的最后一個字符之后或文本的某兩個相鄰字符之間。文本編輯器：為一個可以對一段文本和該文本中的一個光標進行如下七條操作的程序。如果這段文本為空，我們就說這個文本編輯器是空的。 編寫一個程序： 建立一個空的文本編輯器。 從輸入文件中讀入一些操作指令并執行。 對所有執行過的GET操作，將指定的內容寫入輸出文件。Input
輸入文件中第一行是指令條數N，以下是需要執行的N個操作。除了回車符之外，輸入文件的所有字符的ASCII碼都在閉區間[32, 126]內。且行尾沒有空格。
Output
依次對應輸入文件中每條GET指令的輸出，不得有任何多余的字符。
Sample Input
10Insert 13
Balanced eert
Move 2
Delete 5
Next
Insert 7
editor
Move 0
Get
Move 11
Rotate 4
Get
Sample Output
Bt
HINT
對輸入數據我們有如下假定： MOVE操作不超過50 000個，INSERT、DELETE和ROTATE操作作的總個數不超過6 000，GET操作不超過20 000個，PREV和NEXT操作的總個數不超過20 000。 所有INSERT插入的字符數之和不超過2M（1M=1 024*1 024）。 DELETE操作、ROTATE操作和GET操作執行時光標后必然有足夠的字符。MOVE、PREV、NEXT操作不會把光標移動到非法位置。 輸入文件沒有錯誤。
Source
鳴謝seter重新制作數據
這道題很顯然是一道Splay維護區間題，只不過這里的值是字符而不是整數，其實道理是一樣的。
我最初提交時輸入寫scanf(“%d\n”,&n)結果是TLE，后來改成scanf(“%d%*c”,&n)結果就對了，
電腦資料
《bzoj1269[AHOI2006]文本編輯器editor》(http://www.gydabaoji.com)。注：在scanf中如果%后加*表示讀入后不賦給相應的變量，即跳過該輸入值。
#include<iostream>#include<cstdio>#include<cstdlib>#include<cmath>#include<cstring>#include#define F(i,j,n) for(int i=j;i<=n;i++)#define D(i,j,n) for(int i=j;i>=n;i--)#define LL long long#define pa pair<int,int>#define MAXN 2100000#define INF 1000000000#define key c[c[rt][1]][0]using namespace std;int pos=1,rt=0,tot=0,n,x,c[MAXN][2],s[MAXN],fa[MAXN];char v[MAXN],op[10],ch[MAXN];bool rev[MAXN];inline void pushup(int k){ if (!k) return; s[k]=s[c[k][0]]+s[c[k][1]]+1;}inline void update(int k){ if (!k) return; rev[k]^=1; swap(c[k][0],c[k][1]);}inline void pushdown(int k){ if (!k) return; if (rev[k]) { update(c[k][0]);update(c[k][1]); rev[k]=0; }}inline void rotate(int x,int &k){ int y=fa[x],z=fa[y],l=(c[y][1]==x),r=l^1; if (y==k) k=x; else c[z][c[z][1]==y]=x; fa[x]=z;fa[y]=x;fa[c[x][r]]=y; c[y][l]=c[x][r];c[x][r]=y; pushup(y);pushup(x);}inline void splay(int x,int &k){ while (x!=k) { int y=fa[x],z=fa[y]; if (y!=k) { if ((c[y][0]==x)^(c[z][0]==y)) rotate(x,k); else rotate(y,k); } rotate(x,k); }}inline int find(int k,int rank){ pushdown(k); int l=c[k][0],r=c[k][1]; if (s[l]+1==rank) return k; else if (s[l]>=rank) return find(l,rank); else return find(r,rank-s[l]-1);}inline void split(int l,int r){ int x=find(rt,l-1),y=find(rt,r+1); splay(x,rt);splay(y,c[rt][1]);}inline void newnode(int &k,char ch,int last){ k=++tot; fa[k]=last; v[k]=ch; c[k][0]=c[k][1]=rev[k]=0; s[k]=1;}inline void ins(int &k,int l,int r,int last){ int mid=(l+r)>>1; newnode(k,ch[mid],last); if (l<mid) else="" if="" inline="" int="" key="0;"" pos="x+1;}" pre="" void=""></p></mid)></int,int></cstring></cmath></cstdlib></cstdio></iostream>