手机网站怎么做优化,广州建设网站 公司,网站建设策划书事物选题,商品网站建设设计思路直接搞棵splay就行了#xff0c;不要把光标弄到树中而是把光标当成询问或操作区间的端点标志这样会简单很多。 7点40分写到9点20分#xff0c;包括调试总共花了一个小时40分钟#xff0c;这次是自己独立调出来的#xff0c;总算对splay有一定的了解。 设计操作#xff1a;…直接搞棵splay就行了不要把光标弄到树中而是把光标当成询问或操作区间的端点标志这样会简单很多。 7点40分写到9点20分包括调试总共花了一个小时40分钟这次是自己独立调出来的总算对splay有一定的了解。 设计操作区间翻转区间删除和插入取第k个数。 这里的区间插入不是一个一个插那样会很容易使树退化成链状这里应该直接在key_val中build。 #includebits/stdc.h
#define REP(i,a,b) for(int ia;ib;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 INF1e910;
const int maxn2000100;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(r0) 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) rs[tot2--];else rtot1;pre[r]fa;val[r]k;sz[r]1;rev[r]0;MS0(ch[r]);
}void rot(int x,int kind)
{int ypre[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 ypre[x],zpre[y];int kindch[y][0]x,one0;if(ch[y][0]xch[z][0]y) one1;if(ch[y][1]xch[z][1]y) one1;if(one) rot(y,kind),rot(x,kind);else rot(x,kind),rot(x,kind^1);}}if(goal0) rtx;up(x);
}void rto(int k,int goal)
{int rrt;k;while(k!sz[ch[r][0]]1){down(r);if(ksz[ch[r][0]]1) rch[r][0];else k-sz[ch[r][0]]1,rch[r][1];}splay(r,goal);
}void Rev(int l,int r)
{rto(l-1,0);rto(r1,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(r1,rt);down(rt);down(ch[rt][1]);key_val0;up(ch[rt][1]);up(rt);
}void build(int x,int l,int r,int fa)
{if(lr) return;int m(lr)1;//coutll rr mm strstrendl;newnode(x,fa,str[m]);build(ch[x][0],l,m-1,x);build(ch[x][1],m1,r,x);up(x);
}void Insert()
{rto(pos,0);rto(pos1,rt);down(rt);down(ch[rt][1]);int nstrlen(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 rrt;k;while(k!sz[ch[r][0]]1){down(r);if(ksz[ch[r][0]]1) rch[r][0];else k-sz[ch[r][0]]1,rch[r][1];}return val[r];
}void Init()
{pre[0]sz[0]ch[0][0]ch[0][1]rev[0]0;rttot1tot20;newnode(rt,0,-);newnode(ch[rt][1],rt,);sz[rt]2;
}int main()
{freopen(in.txt,r,stdin);while(cinN){Init();pos0;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);posk;}else if(op[0]D){scanf(%d,k);Del(pos1,posk);}else if(op[0]R){scanf(%d,k);Rev(pos1,posk);}else if(op[0]G) printf(%c\n,Get(pos1));else if(op[0]P) pos--;else pos;}}return 0;
} View Code 转载于:https://www.cnblogs.com/--560/p/5202694.html
