Description
您需要写一种数据结构（可参考题目标题），来维护一个有序数列，其中需要提供以下操作：翻转一个区间，例如原有序序列是5 4 3 2 1，翻转区间是[2,4]的话，结果是5 2 3 4 1
Input
第一行为n,m n表示初始序列有n个数，这个序列依次是(1,2……n-1,n) m表示翻转操作次数
接下来m行每行两个数[l,r] 数据保证 1<=l<=r<=n
Output
输出一行n个数字，表示原始序列经过m次变换后的结果
Sample Input
5 3
1 3
1 3
1 4
Sample Output
4 3 2 1 5
HINT
N,M<=100000
思路
一看就知道是Splay。。。。如此经典。也是我写过的第二道splay。第一道是文本编辑器，但是本地测AC，提交的话就WA到死。。
只有区间翻转操作，如果我们要翻转[L,R]的话，就将L-1转到根，再将第R+1大的转到根的右子树。把根的右子树的左子树打上翻转标记就行了。
[1,L-1]和[R+1,n]都被转到别的地方去了，所以不会被旋转。
然后别的都是splay的基本操作啦～只要每次记得push_down就行啦～
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <list>
#include <vector>
#include <ctime>
#include <functional>
#define pritnf printf
#define scafn scanf
#define sacnf scanf
#define For(i,j,k) for(int i=(j);i<=(k);(i)++)
#define Clear(a) memset(a,0,sizeof(a))
using namespace std;
typedef unsigned int Uint;
const int INF=0x3fffffff;
///==============struct declaration==============
struct Node{
int Val;bool Rev;
int siz;
Node *lc,*rc;
Node(){lc=rc=NULL;Rev=false;siz=;}
};
///==============var declaration=================
const int MAXN=;
int n,q;
int num[MAXN];
Node *root=NULL;
///==============function declaration============
void BuildTree(int l,int r,Node *&o);
int find_kth(int rank,Node *&o);
void Splay(int Rank,Node *&o);
void Rrotate(Node *&x);void Lrotate(Node *&x);
void push_down(Node *&x);void Output(Node *&x);
void update(Node *&x);void TestOutput(Node *&x);
///==============main code=======================
int main()
{
#define FILE__
#ifdef FILE__
freopen("input","r",stdin);
freopen("output","w",stdout);
#endif
scanf("%d%d",&n,&q);
BuildTree(,n+,root);//TestOutput(root);printf("\n");
while (q--){
int L,R;scanf("%d%d",&L,&R);
if (L==R) continue;
Splay(L,root);
if (root->lc==NULL)
Splay(R+,root->rc);
else
Splay(R+-root->lc->siz,root->rc);
if (root->rc!=NULL&&root->rc->lc!=NULL)
root->rc->lc->Rev^=;
//TestOutput(root);printf("\n");
}
Output(root);
return ;
}
///================fuction code====================
void BuildTree(int l,int r,Node *&o){
int m=(l+r)>>;
o=new(Node);o->Val=m;
if (l==r) return;
if (m>l) BuildTree(l,m-,o->lc);
if (m<r) BuildTree(m+,r,o->rc);
if (o->lc!=NULL) o->siz+=o->lc->siz;
if (o->rc!=NULL) o->siz+=o->rc->siz;
}
void Lrotate(Node *&x){
push_down(x);push_down(x->lc);
Node *y=x->lc;
x->lc=y->rc;
y->rc=x;x=y;
update(x->rc);update(x);
}
void Rrotate(Node *&x){
push_down(x);push_down(x->rc);
Node *y=x->rc;
x->rc=y->lc;
y->lc=x;x=y;
update(x->lc);update(x);
}
void push_down(Node *&x){
if (x->Rev){
swap(x->lc,x->rc);
x->Rev=false;
if (x->lc!=NULL) x->lc->Rev^=;
if (x->rc!=NULL) x->rc->Rev^=;
}
}
void update(Node *&x){
x->siz=;
if (x->lc!=NULL) x->siz+=x->lc->siz;
if (x->rc!=NULL) x->siz+=x->rc->siz;
}
void Splay(int Rank,Node *&o){
int ls=;push_down(o);
if (o->lc!=NULL) ls=o->lc->siz;
if (Rank==ls+) return;
if (Rank>ls+){
Splay(Rank-ls-,o->rc);
Rrotate(o);
}
else{
Splay(Rank,o->lc);
Lrotate(o);
}
}
void Output(Node *&x){
if (x==NULL) return;
push_down(x);
Output(x->lc);
if (x->Val!=&&x->Val!=n+)
printf("%d ",x->Val);
Output(x->rc);
}
void TestOutput(Node *&x){
if (x==NULL) return;
if (!x->Rev){
printf("%d(",x->Val);
TestOutput(x->lc);
printf(",");
TestOutput(x->rc);
printf(")");
}
else{
printf("%d(",x->Val);
TestOutput(x->rc);
printf(",");
TestOutput(x->lc);
printf(")");
}
}
BZOJ 3223
那个TestOutput是我用来在不改变标记的情况下看数的结构的。