题意：维护一个圈，实现六个功能，给某位置起的一些数增加某值，反转某一段数，添加删除某些数，移动当前所指的位置，
简单的splay，把圈拆成链，对于每种操作，处理一下。
#define inf 0x3f3f3f3f
#define keyTree (ch[ ch[root][1] ][0]) const int maxn = ; struct SplayTree {
int sz[maxn];
int ch[maxn][];
int pre[maxn];
int root , top1 , top2;
int ss[maxn] , que[maxn]; void Rotate(int x,int f) {
int y = pre[x];
push_down(y);
push_down(x);
ch[y][!f] = ch[x][f];
pre[ ch[x][f] ] = y;
pre[x] = pre[y];
if(pre[x]) ch[ pre[y] ][ ch[pre[y]][] == y ] = x;
ch[x][f] = y;
pre[y] = x;
push_up(y);
}
void Splay(int x,int goal) {
push_down(x);
//puts("zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz");
while(pre[x] != goal) {
int y = pre[x], z = pre[y];
push_down(z);
push_down(y);
push_down(x);
if(pre[pre[x]] == goal) {
Rotate(x , ch[pre[x]][] == x);
} else {
int y = pre[x] , z = pre[y];
int f = (ch[z][] == y);
if(ch[y][f] == x) {
Rotate(x , !f) , Rotate(x , f);
} else {
Rotate(y , f) , Rotate(x , f);
}
}
}
push_up(x);
if(goal == ) root = x;
}
void RotateTo(int k,int goal) {//把第k位的数转到goal下边
int x = root;
push_down(x);
while(sz[ ch[x][] ] != k) {
// printf("x = %d k = %d sz[x] = %d\n",x,k,sz[x]);
if(k < sz[ ch[x][] ]) {
x = ch[x][];
} else {
k -= (sz[ ch[x][] ] + );
x = ch[x][];
}
push_down(x);
}
Splay(x,goal);
} //以上一般不修改//////////////////////////////////////////////////////////////////////////////
void debug() {
printf("%d\n",root);
Treaval(root);
}
void Treaval(int x) {
push_down(x);
if(x) {
Treaval(ch[x][]);
printf("结点%2d:左儿子 %2d 右儿子 %2d 父结点 %2d size = %2d ,val = %2d\n",x,ch[x][],ch[x][],pre[x],sz[x],val[x]);
Treaval(ch[x][]);
}
}
//以上Debug
//以下是题目的特定函数:
void NewNode(int &x,int c) {
x = ++top1;
ch[x][] = ch[x][] = pre[x] = ;
sz[x] = ;
val[x] = c;
lazy[x] = add[x] = ;
}
//把延迟标记推到孩子
void push_down(int x) {
if(lazy[x] != )
{
rev(ch[x][]);
rev(ch[x][]);
//swap(add[ch[x][0]],add[ch[x][1]]);
lazy[x] = ;
}
if(add[x] != )
{
val[ch[x][]] += add[x];
val[ch[x][]] += add[x];
add[ch[x][]] += add[x];
add[ch[x][]] += add[x];
add[x] = ;
}
return ;
}
//把孩子状态更新上来
void push_up(int x) {
sz[x] = + sz[ ch[x][] ] + sz[ ch[x][] ];
}
/*初始化*/
void makeTree(int &x,int l,int r,int f) {
if(l > r) return ;
int m = (l + r)>>;
NewNode(x , num[m]); /*num[m]权值改成题目所需的*/
makeTree(ch[x][] , l , m - , x);
makeTree(ch[x][] , m + , r , x);
pre[x] = f;
push_up(x);
}
void clear() {
cnt = ;
ch[][] = ch[][] = pre[] = sz[] = ;
add[] = lazy[] = ;
root = top1 = ;
//为了方便处理边界,加两个边界顶点
NewNode(root , -inf);
NewNode(ch[root][] , inf);
pre[top1] = root;
sz[root] = ;
}
void init(int pos,int n) {
clear();
cnt = n;
RotateTo(pos , );
RotateTo(pos + , root);
makeTree(keyTree , , n , ch[root][]);
push_up(ch[root][]);
push_up(root);
}
void update(int u,int v,int _add )
{
RotateTo(u - , );
RotateTo(v + , root );
add[keyTree] += _add;
val[keyTree] += _add;
push_up(root);
//Splay(keyTree,root);
}
void rev(int x)
{
if(x == ) return;
swap(ch[x][] ,ch[x][]);
lazy[x] ^= ;
}
void lz(int u,int v )
{
RotateTo(u - , );
RotateTo(v + , root );
rev(keyTree);
//Splay(keyTree,root);
}
int split(int u,int v )
{
RotateTo(u - , );
RotateTo(v + , root );
int res = keyTree;
keyTree = ;
push_up(ch[root][]);
push_up(root);
return res ;
}
void hb(int k,int ts)
{
RotateTo(k - , );
RotateTo(k , root);
keyTree = ts ;
pre[ts] = ch[root][];
push_up(ch[root][]);
push_up(root);
}
void insert(int k,int val)
{
cnt ++ ;
RotateTo(k - , );
RotateTo(k , root ) ;
NewNode(keyTree,val);
pre[keyTree] = ch[root][];
push_up(ch[root][]);
push_up(root);
}
int getkth(int k )
{
int x = root ;
push_down(x);
while(sz[ ch[x][] ] != k) {
// printf("x = %d k = %d sz[x] = %d\n",x,k,sz[x]);
if(k < sz[ ch[x][] ]) {
x = ch[x][];
} else {
k -= (sz[ ch[x][] ] + );
x = ch[x][];
}
push_down(x);
}
return val[x];
}
void del(int k) {
RotateTo(k - , );
RotateTo(k + , root);
//printf("val = %d\n",val[keyTree]);
//printf("sz = %d\n",sz[keyTree]);
cnt -- ;
keyTree = ;
push_up(ch[root][]);
push_up(root);
// erase(keyTree);
}
int cnt ;
/*这是题目特定变量*/
int num[maxn];
int val[maxn];
int add[maxn];
int lazy[maxn]; } spt; int n,m,k1,k2;
int wh;
int main()
{
int cas;
cas = ;
char str[];
while(
scanf("%d%d%d%d",&n,&m,&k1,&k2)!=EOF && !(n == && m == && k1 == && k2 == ) )
{
for(int i = ; i<= n ; i ++ ) scanf("%d",&spt.num[i]);
spt.init(,n);
wh = ;
printf("Case #%d:\n",++cas);
int x;
while(m -- )
{
scanf("%s",str);
if( str[] == 'q' )
{
int ans = spt.getkth(wh);
printf("%d\n",ans);
}
else if( str[] == 'r' )
{
if(wh + k1 - <= spt.cnt)
{
spt.lz(wh , wh + k1 - );
}
else
{
int p1,p2,p3,p4;
p4 = spt.cnt;
p1 = wh + k1 - - spt.cnt;
p2 = spt.split(,p1);
wh = wh - p1;
p4 = p4 - p1;
spt.hb(p4 + ,p2);
p1 = wh + k1 - ;
spt.lz(wh,p1);
}
}
else if(str[] == 'i')
{
scanf("%d",&x);
spt.insert(wh + ,x);
}
else if(str[] == 'm')
{
scanf("%d",&x);
if(x == )
{
wh -- ;
if(wh == ) wh = spt.cnt;
}
else
{
wh ++ ;
if(wh >spt.cnt) wh = ;
}
}
else if(str[] == 'd')
{
if(wh == spt.cnt)
{
spt.del(wh);
wh = ;
}
else
{
spt.del(wh);
}
}
else if(str[] == 'a')
{
scanf("%d",&x);
int p1,p2,p3,lef;
if(wh + k2 - <= spt.cnt)
{
spt.update(wh,wh + k2 - ,x);
}
else
{
lef = wh + k2 - - spt.cnt;
// printf("%d %d \n",k2,lef);
spt.update(,lef,x);
spt.update(wh,spt.cnt,x);
}
}
// spt.debug();
}
}
return ;
}
7k+的代码，居然调出来了，好开心。