直接搞棵splay就行了，不要把光標弄到樹中而是把光標當成詢問或操作區間的端點標志這樣會簡單很多。

7點40分寫到9點20分，包括調試總共花了一個小時40分鐘，這次是自己獨立調出來的，總算對splay有一定的了解。

設計操作：區間翻轉，區間刪除和插入，取第k個數。

這里的區間插入不是一個一個插，那樣會很容易使樹退化成鏈狀，這里應該直接在key_val中build。

#include<bits/stdc++.h> #define REP(i,a,b) for(int i=a;i<=b;i++) #define MS0(a) memset(a,0,sizeof(a)) #define key_val ch[ch[rt][1]][0]using namespace std;typedef long long ll; const int INF=1e9+10; const int maxn=2000100;int N; char op[20];int k; char str[maxn]; int pos;int pre[maxn],sz[maxn],ch[maxn][2],rt,tot1; int s[maxn],tot2; char val[maxn]; int rev[maxn];void debug(int r) {if(r==0) return;debug(ch[r][0]);printf("%c",val[r]);//printf("lch=%2d rch=%2d pre=%2d r=%2d val=%c sz=%2d rt=%2d\n",ch[r][0],ch[r][1],pre[r],r,val[r],sz[r],rt);debug(ch[r][1]); }void up(int r) {sz[r]=sz[ch[r][0]]+sz[ch[r][1]]+1; }void update_rev(int r) {if(!r) return;swap(ch[r][0],ch[r][1]);rev[r]^=1; }void down(int r) {if(rev[r]){update_rev(ch[r][0]);update_rev(ch[r][1]);rev[r]=0;} }void newnode(int &r,int fa,char k) {if(tot2) r=s[tot2--];else r=++tot1;pre[r]=fa;val[r]=k;sz[r]=1;rev[r]=0;MS0(ch[r]); }void rot(int x,int kind) {int y=pre[x];down(y);down(x);ch[y][kind^1]=ch[x][kind];pre[ch[x][kind]]=y;if(pre[y]) ch[pre[y]][ch[pre[y]][1]==y]=x;pre[x]=pre[y];ch[x][kind]=y;pre[y]=x;up(y); }void splay(int x,int goal) {down(x);while(pre[x]!=goal){if(pre[pre[x]]==goal) rot(x,ch[pre[x]][0]==x);else{int y=pre[x],z=pre[y];int kind=ch[y][0]==x,one=0;if(ch[y][0]==x&&ch[z][0]==y) one=1;if(ch[y][1]==x&&ch[z][1]==y) one=1;if(one) rot(y,kind),rot(x,kind);else rot(x,kind),rot(x,kind^1);}}if(goal==0) rt=x;up(x); }void rto(int k,int goal) {int r=rt;k++;while(k!=sz[ch[r][0]]+1){down(r);if(k<sz[ch[r][0]]+1) r=ch[r][0];else k-=sz[ch[r][0]]+1,r=ch[r][1];}splay(r,goal); }void Rev(int l,int r) {rto(l-1,0);rto(r+1,rt);down(rt);down(ch[rt][1]);update_rev(key_val);up(ch[rt][1]);up(rt); }void Del(int l,int r) {rto(l-1,0);rto(r+1,rt);down(rt);down(ch[rt][1]);key_val=0;up(ch[rt][1]);up(rt); }void build(int &x,int l,int r,int fa) {if(l>r) return;int m=(l+r)>>1;//cout<<"l="<<l<<" r="<<r<<" m="<<m<<" str="<<str<<endl; newnode(x,fa,str[m]);build(ch[x][0],l,m-1,x);build(ch[x][1],m+1,r,x);up(x); }void Insert() {rto(pos,0);rto(pos+1,rt);down(rt);down(ch[rt][1]);int n=strlen(str);build(key_val,0,n-1,ch[rt][1]);pre[key_val]=ch[rt][1];up(ch[rt][1]);up(rt); }char Get(int k) {int r=rt;k++;while(k!=sz[ch[r][0]]+1){down(r);if(k<sz[ch[r][0]]+1) r=ch[r][0];else k-=sz[ch[r][0]]+1,r=ch[r][1];}return val[r]; }void Init() {pre[0]=sz[0]=ch[0][0]=ch[0][1]=rev[0]=0;rt=tot1=tot2=0;newnode(rt,0,'-');newnode(ch[rt][1],rt,'+');sz[rt]=2; }int main() {freopen("in.txt","r",stdin);while(cin>>N){Init();pos=0;REP(i,1,N){scanf("%s",op);if(op[0]=='I'){scanf("%d",&k);gets(str);gets(str);Insert();}else if(op[0]=='M'){scanf("%d",&k);pos=k;}else if(op[0]=='D'){scanf("%d",&k);Del(pos+1,pos+k);}else if(op[0]=='R'){scanf("%d",&k);Rev(pos+1,pos+k);}else if(op[0]=='G') printf("%c\n",Get(pos+1));else if(op[0]=='P') pos--;else pos++;}}return 0; } View Code

?

轉載于:https://www.cnblogs.com/--560/p/5202694.html

總結

以上是生活随笔為你收集整理的bzoj1269 文本编辑器 splay的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。