复制炸格式了, 就不贴题面了
[NOI2003] 文本编辑器 https://www.luogu.org/problemnew/show/P4008
Solution
对于光标的移动, 我们只要记录一下现在在哪里就可以了
Insert 操作: 手动维护中序遍历结果, 即每次取中点像线段树一样一样递归建树, 实际操作: 把 splay 中的光标所在位置旋到根, 光标后一位旋到根的下面, 此时根的右节点的左子树是空的, 直接插入我们所建的树的根即可
Delete: 先找到我们要删除的是哪一段区间, 把光标之前的点旋到根, 终点之后的点旋到根的下面, 直接扔掉根节点的右儿子的左子树即可
Get: 也是找到区间递归中序输出就可以了
提示: 为了防止越界, 我在 splay 插入了两个换行符, 保证题目输入不会出现就行, 因此也要把光标初始值设为 1
- Code
- #include<bits/stdc++.h>
- #define il inline
- #define rg register
- #define lol long long
- #define Min(a,b) (a)<(b)?(a):(b)
- #define Max(a,b) (a)>(b)?(a):(b)
- using namespace std;
- const int N=1e6+10;
- const int inf=2e9;
- void in(int &ans)
- {
- ans=0; int f=1; char i=getchar();
- while(i<'0' || i>'9') {if(i=='-') f=-1; i=getchar();}
- while(i>='0' && i<='9') ans=(ans<<1)+(ans<<3)+i-'0', i=getchar();
- ans*=f;
- }
- int n,tot,m,now=1,root;
- char s[N<<1];
- struct Splay {
- int f,size,ch[2];
- Splay(){
- size = ch[0] = ch[1] = 0;
- }
- char val;
- }t[N<<1];
- il bool get(int x) {
- return t[t[x].f].ch[1]==x;
- }
- il void up(int x) {
- t[x].size=t[t[x].ch[0]].size+t[t[x].ch[1]].size+1;
- }
- void rotate(int x) {
- int f=t[x].f,gf=t[f].f;
- int k1=get(x),k2=get(f);
- t[gf].ch[k2]=x,t[x].f=gf;
- t[f].ch[k1]=t[x].ch[k1^1],t[t[x].ch[k1^1]].f=f;
- t[x].ch[k1^1]=f,t[f].f=x;
- up(f); up(x);
- }
- void splay(int x,int goal) {
- while(t[x].f!=goal) {
- int f=t[x].f,gf=t[f].f;
- if(gf!=goal) get(x)^get(f)?rotate(x):rotate(f);
- rotate(x);
- }
- if(!goal) root=x;
- }
- int kth(int k) {
- int u=root;
- while(1) {
- int y=t[u].ch[0];
- if(k>t[y].size+1)
- u=t[u].ch[1],k-=t[y].size+1;
- else if(k<=t[y].size) u=y;
- else return u;
- }
- }
- il void Move() {
- in(now); now++;
- }
- il int add(char c,int f) {
- t[++tot].val=c; t[tot].size=1;
- t[tot].f=f; return tot;
- }
- int build(int f,int l,int r,char *s) {
- int mid=l+r>>1;
- char ch=s[mid];
- int u=add(ch,f);// 按中序遍历建树
- if(l<mid) t[u].ch[0]=build(u,l,mid-1,s);
- if(mid<r) t[u].ch[1]=build(u,mid+1,r,s);
- up(u); return u;
- }
- void Insert() {
- int x; in(x); strcpy(s,"");
- for(rg int i=1;i<=x;i++) {
- char ch=getchar();
- while(ch==10 || ch==13 || ch<32 || ch>126) ch=getchar();
- s[i]=ch;
- }
- int l=kth(now);
- int r=kth(now+1);
- splay(l,0); splay(r,l);
- t[t[root].ch[1]].ch[0]=build(t[root].ch[1],1,x,s);
- up(t[root].ch[1]); up(root);
- }
- void Delete() {
- int x; in(x);
- int l=kth(now),r=kth(now+x+1);//r=kth((now+x-1)+1+1) 第一个 + 1 指光标指到起点, 因为实际上光标指的是起点 - 1 所以要加回来, 第二个 + 1 指区间终点的后一个端点
- splay(l,0); splay(r,l);
- int u=t[root].ch[1];
- t[u].ch[0]=0;
- up(u); up(root);
- }
- void out(int u) {
- if(t[u].ch[0]) out(t[u].ch[0]);
- if(t[u].val!='\n') putchar(t[u].val);
- if(t[u].ch[1]) out(t[u].ch[1]);
- }
- void Get() {
- int x; in(x);
- int l=kth(now),r=kth(now+x+1);
- splay(l,0); splay(r,l);
- out(t[t[root].ch[1]].ch[0]);
- putchar('\n');
- }
- int main()
- {
- //freopen("data.in", "r", stdin);
- root=add('\n',0),t[root].ch[1]=add('\n',root);up(root);
- in(n); char s[10];
- while(n--) {
- scanf("%s",s);
- if(s[0]=='M') Move();
- if(s[0]=='I') Insert();
- if(s[0]=='D') Delete();
- if(s[0]=='G') Get();
- if(s[0]=='P') now--;
- if(s[0]=='N') now++;
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2763222.html