| 20605移动盒子 |
| 难度级别：B； 运行时间限制：1000ms； 运行空间限制：51200KB； 代码长度限制：2000000B |
|
试题描述
|
|
你有一行盒子，从左到右依次编号为1,2,3，……，n。可以执行一下四种指令： |
|
输入
|
|
第一行包括两个正整数n和m，分别表示盒子个数和指令条数，接下来的m行，每行一条指令，如果是指令1、2或者3时，三部分间有一个空格分隔，如指令1 2 4表示将盒子2移动到盒子4的左边。
|
|
输出
|
|
一个正整数，表示所有奇数位置上盒子编号的数字之和。
|
|
输入示例
|
|
6 4
1 1 4 2 3 5 3 1 6 4 |
|
输出示例
|
|
12
|
|
其他说明
|
|
样例说明：当n=6时，在初始状态下执行1 1 4后，盒子序列为2 3 1 4 5 6，接下来执行2 3 5后，盒子序列变成2 1 4 5 3 6，再执行3 1 6，得到2 6 4 5 3 1，最终执行4，得到1 3 5 4 6 2。
0 < n, m < 100001 |
题解：赤裸裸的链表，可惜我没有写。我写的是splay tree你们怕不怕！！！
写完真的是太爽了。。。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
#include<cstring>
#define PAU putchar(' ')
#define ENT putchar('\n')
#define CH for(int d=0;d<=1;d++) if(ch[d])
using namespace std;
const int maxn=+;
struct node{
node*fa,*ch[];
int c;bool rev;int siz;
node(){c=-;rev=false;siz=;}
void revt(){swap(ch[],ch[]);rev^=;return;}
void update(){siz=;CH{siz+=ch[d]->siz;}return;}
void down(){if(rev){CH{ch[d]->revt();}rev=false;}return;}
}Splay[maxn],*root;int cnt=;
int parent(node*x,node*&y){return (y=x->fa)?y->ch[]==x?:y->ch[]==x?:-:-;}
void rotate(node*x){
node*y,*z;int d1=parent(x,y),d2=parent(y,z);
if(y->ch[d1]=x->ch[d1^]) y->ch[d1]->fa=y;
y->fa=x;x->fa=z;x->ch[d1^]=y;
if(d2!=-) z->ch[d2]=x;
y->update();return;
}
void pushdown(node*x){
static node*s[maxn];int top=;
for(node*y;;x=y){
s[top++]=x;y=x->fa;
if(!y||(y->ch[]!=x&&y->ch[]!=x)) break;
} while(top--) s[top]->down();return;
}
node*splay(node*x){
pushdown(x);node*y,*z;int d1,d2;
while(true){
if((d1=parent(x,y))<) break;
if((d2=parent(y,z))<){rotate(x);break;}
if(d1==d2) rotate(y),rotate(x);
else rotate(x),rotate(x);
} x->update();return x;
}
node*find(node*x,int rank){
x->down();int kth=;if(x->ch[]) kth=x->ch[]->siz+;
if(rank==kth) return x;
if(rank<kth) return find(x->ch[],rank);
else return find(x->ch[],rank-kth);
}
void split(node*&x,node*&y,int a){
if(!a){y=x;x=NULL;return;}
x=splay(find(x,a));y=x->ch[];
x->ch[]=NULL;if(y)y->fa=NULL;x->update();return;
}
void split(node*&x,node*&y,node*&z,int a,int b){
split(x,z,b);split(x,y,a-);return;
}
void join(node*&x,node*y){
if(!x){x=y;return;}if(!y)return;
x=splay(find(x,x->siz));x->ch[]=y;
if(y)y->fa=x;x->update();return;
}
void join(node*&x,node*y,node*z){
join(y,z);join(x,y);return;
}
int A[maxn],n,Q;
void build(node*&x,int L,int R){
if(L>R)return;int M=L+R>>;
x=&Splay[cnt++];x->c=A[M];
build(x->ch[],L,M-);
build(x->ch[],M+,R);
if(x->ch[]) x->ch[]->fa=x;
if(x->ch[]) x->ch[]->fa=x;
x->update();return;
}
void reverse(int L,int R){
node*x,*y;split(root,x,y,L,R);x->revt();join(root,x,y);return;
}
node*findll(node*x,int a){
if(!x) return NULL;x->down();
if(x->c==a) return x;
node*t;
if((t=findll(x->ch[],a))||(t=findll(x->ch[],a))) return t;
return NULL;
}
void printer(node*x){
if(!x){printf("NULL ");return;}
x->down();
if(x->ch[])printer(x->ch[]);
printf("%d ",x->c);
if(x->ch[])printer(x->ch[]);
return;
}
int cz=;long long sum=;
void counter(node*x){
if(!x){return;}
x->down();
if(x->ch[])counter(x->ch[]);
if((cz++)&) sum+=x->c;
if(x->ch[])counter(x->ch[]);
return;
}
node*findfa(node*x){
while(x->fa) x=x->fa;return x;
}
int findpos(int a){
for(int i=;i<=n;i++) if(A[i]==a) return i;
return -;
}
void split(node*&t1,node*&x,node*&t2,node*&y,node*&t3,int a,int b){
splay(t1);
x=findll(t1,a),y=findll(t1,b);
splay(x);int kth1=;if(x->ch[]) kth1=x->ch[]->siz+;
splay(y);int kth2=;if(y->ch[]) kth2=y->ch[]->siz+;
if(kth1>kth2) swap(kth1,kth2);
splay(t1);split(t1,x,t2,kth1,kth1);
kth2-=kth1;split(t2,y,t3,kth2,kth2);return;
}
void join(node*&t1,node*x,node*t2,node*y,node*t3){
join(t2,y,t3);join(t1,x,t2);return;
}
void swapnode(int a,int b){
node*t1,*t2,*x,*y;
split(root,x,t1,y,t2,a,b);
join(root,y,t1,x,t2);return;
}
void shift(int a,int b,int tp){//1 right 0 left
node*t1,*t2,*x,*y;
split(root,x,t1,y,t2,a,b);
y->ch[tp]=x;x->fa=y;y->update();
join(root,NULL,t1,y,t2);return;
}
inline int read(){
int x=,sig=;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')sig=-;ch=getchar();}
while(isdigit(ch))x=*x+ch-'',ch=getchar();
return x*=sig;
}
inline void write(int x){
if(x==){putchar('');return;}if(x<)putchar('-'),x=-x;
int len=,buf[];while(x)buf[len++]=x%,x/=;
for(int i=len-;i>=;i--)putchar(buf[i]+'');return;
}
inline void write(long long x){
if(x==){putchar('');return;}if(x<)putchar('-'),x=-x;
int len=;long long buf[];while(x)buf[len++]=x%,x/=;
for(int i=len-;i>=;i--)putchar(buf[i]+'');return;
}
void init(){
n=read();Q=read();
for(int i=;i<=n;i++) A[i]=i;
build(root,,n);int tp,a,b;
while(Q--){
tp=read();
if(tp==) root->revt();
else{
a=read();b=read();
if(tp==) swapnode(a,b);
else shift(a,b,tp-);
}
}
counter(root);
write(sum);
return;
}
void work(){
return;
}
void print(){
return;
}
int main(){init();work();print();return ;}