可以作为模板
#include <map>
#include <set>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <string>
#include <cstdio>
#include <math.h>
#include <iomanip>
#include <cstdlib>
#include <limits.h>
#include <string.h>
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
#define LL long long
#define pii pair<int ,int>
#define bug cout<<"here!!"<<endl
#define PI acos(-1.0)
#define FRE freopen("input.txt","r",stdin)
#define FF freopen("output.txt","w",stdout)
#define eps 1e-8
#define MIN INT_MIN
#define inf 1<<30
#define N 3*100100
//#define DEBUG_ENABLE 1
struct SplayTree{
int sz[N]; //sz[x]-以x为根结点子树的结点数量
int ch[N][2]; //ch[x][0]-x的左子节点;ch[x][1]-x的右子节点
int pre[N]; //pre[x]-x的父结点
int root,top1,top2; //root-根结点;top1-未用结点队列头指针;top2-结点回收栈的栈顶指针
int ss[N],que[N];
/***********************************以下代码基本不变*********************************************/
/* Rotate(x,f):f=0-将x点左旋;f=1-将x点右旋 */
inline 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[y])
if(ch[pre[y]][0]==y) ch[pre[y]][0]=x;
else ch[pre[y]][1]=x;
ch[x][f]=y;
pre[y]=x;
push_up(y);
}
/* splay(x,goal):将x结点伸展为goal结点的子节点 */
inline void splay(int x,int goal){
for(push_down(x);pre[x]!=goal;){
if(pre[pre[x]]==goal){ /* x节点的父结点的父结点为goal,进行单旋转 */
if(ch[pre[x]][0]==x) rotate(x,1);
else rotate(x,0);
}
else{
int y=pre[x];
int z=pre[y];
if(ch[z][0]==y)
if(ch[y][0]==x){ /* 一字形旋转 */
rotate(y,1);
rotate(x,1);
}
else{ /* 之字形旋转 */
rotate(x,0);
rotate(x,1);
}
else
if(ch[y][1]==x){ /* 一字形旋转 */
rotate(y,0);
rotate(x,0);
}
else{ /* 之字形旋转 */
rotate(x,1);
rotate(x,0);
}
}
push_up(x);
if(goal==0) root=x;
}
}
/* rotateTo(k,goal):将序列中第k个数转到goal的子节点 */
inline void rotateTo(int k,int goal){
/* 第k位要利用中序遍历来查找 */
int tmp,t;
for(t=root;;){
push_down(t); /* 标记下延 */
tmp=sz[ch[t][0]];
if(k==tmp+1) break;
if(k<=tmp) /* 第k个节点在t的左子树，向左遍历 */
t=ch[t][0];
else{
k-=tmp+1;
t=ch[t][1];
}
}
splay(t,goal);
}
/* join(s1,s2):将s1和s2两个Splay Tree合并为一个Splay Tree,s1的所有结点都小于s2的所有结点;返回合并后的根节点 */
inline int join(int s1,int s2){
if(s1&&s2){
int right_end=getEnd(s1,1);
splay(right_end,pre[s1]);
ch[right_end][1]=s2;
pre[s2]=right_end;
push_up(right_end);
return right_end;
}
if(s1) return s1;
if(s2) return s2;
return 0;
}
/* erase(x):把x为节点的子树删除，放到内存池 */
inline void erase(int x){
int head,tail;
for(que[tail++]=x;head<tail;head++){
ss[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];
}
}
/* eraseNode(x): 将x结点删除，其子树进行和并 */
inline void eraseNode(int x){
int ret = join(ch[x][0],ch[x][1]);
if(pre[x]){
if(ch[pre[x]][0]==x)
ch[pre[x]][0]=ret;
else
ch[pre[x]][1]=ret;
}
else{
root=ret;
}
if(ret)
pre[ret]=pre[x];
if(pre[x])
splay(pre[x],0);
}
/* getEnd(x,c): 得到x节点最边缘的节点 c=0 最左边的, c=1 最右边的 */
inline int getEnd(int x,int c){
push_down(x);
while(ch[x][c]){
x=ch[x][c];
push_down(x);
}
return x;
}
/* getNear(x,c): 得到x节点最近的节点 c=0 前驱节点, c=1 后继节点 */
inline int getNear(int x,int c){
if(ch[x][c]){
return getEnd(ch[x][c],1-c);
}
while(pre[x]&&ch[pre[x]][c]==x)
x=pre[x];
return pre[x];
}
/* getSucc(x): 得到x节点的后继节点 */
inline int getSucc(int x) { return getNear(x,1); }
/* getPrev(x): 得到x节点的前驱节点 */
inline int getPrev(int x) { return getNear(x,0); }
/*****************************************END*********************************************/
/**********************************以下代码会随着题目的不同改变****************************/
/* 标记结点 */
inline void markNode(int x){
if(x){
_rev[x]=!_rev[x];
/*swap(ch[x][0],ch[x][1])交换左右结点*/
int tmp;
tmp=ch[x][0];
ch[x][0]=ch[x][1];
ch[x][1]=tmp;
}
}
/* push_down 把延迟标记推到孩子 */
inline void push_down(int x){
if(_rev[x]){
markNode(ch[x][0]);
markNode(ch[x][1]);
_rev[x]=false;
}
}
/* push_up 把孩子的状态更新上来 */
inline void push_up(int x){
sz[x]=1+sz[ch[x][0]]+sz[ch[x][1]];
}
/* findKthNode(int k): 在Splay Tree中找到第k个节点 */
inline int findKthNode(int k){
/* 第k位要利用中序遍历来查找 */
int tmp,t;
for(t=root;;){
push_down(t); /* 标记下延 */
tmp=sz[ch[t][0]];
if(k==tmp+1) break;
if(k<=tmp) /* 第k个节点在t的左子树，向左遍历 */
t=ch[t][0];
else{
k-=tmp+1;
t=ch[t][1];
}
}
return t;
}
/* To create a new node 题目不同，函数内容不同 */
inline void newNode(int &x,int m){
if(top2) x=ss[--top2];
else x=++top1;
ch[x][0]=ch[x][1]=pre[x]=0;
sz[x]=1;
val[x]=m;
_rev[x]=false;
}
/* To build a splay tree 题目不同，函数内容不同 */
inline void makeTree(int &x,int l,int r,int f){//x-son，f-father
if(l>r) return ;
int m=(r+l)>>1;
newNode(x,m);
makeTree(ch[x][0],l,m-1,x);
makeTree(ch[x][1],m+1,r,x);
pre[x]=f;
push_up(x);
}
/* 初始化函数(调用建树函数)，题目不同，函数内容不同 */
inline void init(int n){
ch[0][0]=ch[0][1]=pre[0]=sz[0]=0;
root=top1=top2=0;
/* 增加第一个边界结点 */
/* Read into the Datas */
/* 增加第二个边界节点 */
makeTree(root,0,n,0);
push_up(root);
}
/* update 更新函数 题目不同内容不同 */
inline void update(){
}
/* query 查询函数 题目不同内容不同 */
inline void query(){
}
/* run() */
inline void run(int n,int m){
int i;
for(i=0;i<m;i++){
char in[5];
scanf("%s",in);
int a,b,c;
if(in[0]=='C'){//先切再插入一段
scanf("%d%d%d",&a,&b,&c);
a=findKthNode(a);
splay(a,0);
b=findKthNode(b+2);
splay(b,root);
int cut=ch[b][0];//cut是要操作的区间子树的根
//push_down(b); //
ch[b][0]=0;
//splay(b,0);
a=findKthNode(c+1);
splay(a,0);//将a转到根
b=getSucc(a);//后继
splay(b,root);//后继转到根的右子结点
ch[b][0]=cut;//把切出来的子树挂到根右子结点的左子结点上
pre[cut]=b;
splay(b,0);
//debug();
}
else{//翻转
scanf("%d%d",&a,&b);
a=findKthNode(a);
splay(a,0);
b=findKthNode(b+2);
splay(b,root);
markNode(ch[b][0]);//交换左右结点
}
}
num = -1;
outputNode(root,n);
printf("\n");
}
/* binarySearch(k): 查找第k号人 */
inline int binarySearch(int k,int n){
return 0;
}
/* isSmaller(a,b): val[a]<val[b] retrun 1*/
inline int isSmaller(int a,int b){
return 0;
}
/*output(x,n): 中序遍历输出节点值，最左和最右的值不输出 */
inline void outputNode(int x,int n){
if(x){
push_down(x);
outputNode(ch[x][0],n);//先遍历左
num++;
if(num!=0&&num!=n+1){
if(num==n) printf("%d",val[x]);
else printf("%d ",val[x]);
}
outputNode(ch[x][1],n);//再遍历右
}
}
/* Optional Variables 题目不同，变量不同 */
int val[N];
bool _rev[N];
int num;
/*****************************************END**********************************************/
/****************************************Debug*********************************************/
#if (DEBUG_ENABLE == 1)
void debug() {printf("%d\n",root);Treaval(root);}
void Treaval(int x) {
if(x) {
printf("结点 %2d: 左儿子 %2d 右儿子 %2d 父结点 %2d size = %2d val = %2d rev = %2d\n",x,ch[x][0],ch[x][1],pre[x],sz[x],val[x],_rev[x]);
Treaval(ch[x][0]);
Treaval(ch[x][1]);
}
}
#endif
/*****************************************END**********************************************/
}spt;
int main(){
int n,m;
while(scanf("%d%d",&n,&m) && n != -1 && m != -1){
spt.init(n+1);
//spt.debug();
spt.run(n,m);
}
return 0;
}
版权声明：本文为leolin_原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。