首页 > 代码库 > Hdu 4699 Editor(Splay)
Hdu 4699 Editor(Splay)
题目大意:
给出一个文本编辑器,按照图示的操作进行删减和添加。
思路分析:
对于如何维护左边最大,就要记录每个区间的左边最大,还有这个节点的值,还有子区间的和。
注意看题目,题目的要求输出左边最大是不能为空集的,意味着如果全部都是负数,那么就输出最左边的负数就好。
那么就要解决初始化的问题。
再有一点问题就是会有很多个连续的L ,R操作。所以要判断边界。
#include <cstdio> #include <iostream> #include <vector> #include <cstdio> #include <stdlib.h> #define inf 0x3f3f3f3f #define maxn 2000005 #define keyTree (ch[ch[root][1]][0]) using namespace std; typedef long long LL; int S[maxn],que[maxn],ch[maxn][2],pre[maxn],siz[maxn]; int root,top1,top2; /*以上变量为Splay固有的*/ int val[maxn],a[maxn]; int lef[maxn],sum[maxn]; inline void scanf_(int &num){ char in; bool neg=false; while(((in=getchar()) > '9' || in<'0') && in!='-') ; if(in=='-'){ neg=true; while((in=getchar()) >'9' || in<'0'); } num=in-'0'; while(in=getchar(),in>='0'&&in<='9') num*=10,num+=in-'0'; if(neg) num=0-num; } inline void printf_(int num){ bool flag=false; if(num<0){ putchar('-'); num=-num; } int ans[10],top=0; while(num!=0){ ans[top++]=num%10; num/=10; } if(top==0) putchar('0'); for(int i=top-1;i>=0;i--){ char ch=ans[i]+'0'; putchar(ch); } } void Treaval(int x) { if(x) { Treaval(ch[x][0]); printf("%d ",val[x]); //printf("now %2d:lson %2d rson %2d father %2d size = %2d ,val = %2d \n",x,ch[x][0],ch[x][1],pre[x],siz[x],val[x]); Treaval(ch[x][1]); } } void debug() { printf("root=%d\n",root); Treaval(root); puts(""); } void New(int &x,int PRE,int v) { if(top2)x=S[--top2]; else x=++top1; ch[x][0]=ch[x][1]=0; siz[x]=1; pre[x]=PRE; val[x]=v; lef[x]=v; // rig[x]=max(0,v); sum[x]=v; } void pushup(int x) { siz[x]=siz[ch[x][0]]+siz[ch[x][1]]+1; sum[x]=sum[ch[x][0]]+sum[ch[x][1]]+val[x]; lef[x]=max(lef[ch[x][0]],max(sum[ch[x][0]]+val[x],sum[ch[x][0]]+val[x]+lef[ch[x][1]])); } void pushdown(int x) { } void build(int &x,int s,int e,int f) { if(s>e)return; int mid=(s+e)>>1; New(x,f,a[mid]); if(s<mid)build(ch[x][0],s,mid-1,x); if(e>mid)build(ch[x][1],mid+1,e,x); pushup(x); } void Rotate(int x,int kind) { int y=pre[x]; pushdown(x); pushdown(y); ch[y][!kind]=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; pushup(y); } void Splay(int x,int goal) { pushdown(x); while(pre[x]!=goal) { if(pre[pre[x]]==goal) Rotate(x,ch[pre[x]][0]==x); else { int y=pre[x]; int kind=ch[pre[y]][0]==y; if(ch[y][kind]==x){ Rotate(x,!kind); Rotate(x,kind); } else { Rotate(y,kind); Rotate(x,kind); } } } pushup(x); if(goal==0)root=x; } void RotateTo(int k,int goal) { int r=root; pushdown(r); while(siz[ch[r][0]]!=k) { if(k<siz[ch[r][0]]) { r=ch[r][0]; } else { k-=siz[ch[r][0]]+1; r=ch[r][1]; } pushdown(r); } Splay(r,goal); } void erase(int x) { int y=pre[x]; int head=0,tail=0; for(que[tail++]=x;head<tail;head++) { S[top2++]=que[head]; if(ch[que[head]][0])que[tail++]=ch[que[head]][0]; if(ch[que[head]][1])que[tail++]=ch[que[head]][1]; } ch[y][ch[y][1]==x]=0; pushup(y); } void init(int n)/*special*/ { root=top1=top2=0; ch[0][0]=ch[0][1]=siz[0]=pre[0]=sum[0]=0; val[0]=0; lef[0]=-0x3f3f3f3f; New(root,0,0); New(ch[root][1],root,0); siz[root]=2; pushup(ch[root][1]); pushup(root); } int main() { int Q; while(scanf("%d",&Q)!=EOF) { init(1); int pos=0; int cnt=0; while(Q--) { char cmd[5]; scanf("%s",cmd); if(cmd[0]=='I') { int x; scanf("%d",&x); RotateTo(pos,0); RotateTo(pos+1,root); New(keyTree,ch[root][1],x); pushup(ch[root][1]); pushup(root); cnt++; pos++; } else if(cmd[0]=='Q') { int x; scanf("%d",&x); x=min(x,cnt); RotateTo(0,0); RotateTo(x+1,root); printf_(lef[keyTree]); puts(""); } else if(cmd[0]=='D') { if(pos==0)continue; RotateTo(pos-1,0); RotateTo(pos+1,root); keyTree=0; pushup(ch[root][1]); pushup(root); if(pos) pos--; if(cnt>0) cnt--; } else if(cmd[0]=='L') { pos--; if(pos<0)pos=0; } else if(cmd[0]=='R') { pos++; if(pos>cnt)pos=cnt; } } } return 0; }
Hdu 4699 Editor(Splay)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。