此为平衡树系列第二道：文艺平衡树您需要写一种数据结构，来维护一个有序数列，其中需要提供以下操作：
翻转一个区间，例如原有序序列是5 4 3 2 1，翻转区间是[2,4]的话，结果是5 2 3 4 1
输入
第一行为n,m n表示初始序列有n个数，这个序列依次是(1,2……n-1,n) m表示翻转操作次数
接下来m行每行两个数[l,r] 数据保证 1<=l<=r<=n
输出
输出一行n个数字，表示原始序列经过m次变换后的结果
样例输入
5 3
1 3
1 3
1 4
样例输出
4 3 2 1 5
提示
n,m<=100000
非旋转treap相比于旋转treap支持区间操作，所以对于这道题只需要每次把树拆成[1~l-1]、[l~r]、[r+1~tot]三段，然后把[l~r]打上标记进行翻转，再把三段区间合并就行了。对于打标记的点只有在查到这个点时才翻转，如果一个点被打了两次标记就相当于不翻转。
最后附上代码.
指针版
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
char *p1,*p2,buf[100000];
#define nc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
int rd() {int x=0,f=1; char c=nc(); while(!isdigit(c)) {if(c=='-') f=-1; c=nc();} while(isdigit(c)) x=(((x<<2)+x)<<1)+(c^48),c=nc(); return x*f;}
ll rd2() {ll x=0,f=1; char c=nc(); while(!isdigit(c)) {if(c=='-') f=-1; c=nc();} while(isdigit(c)) x=(((x<<2)+x)<<1)+(c^48),c=nc(); return x*f;}
int n,m;
int L,R;
struct treap
{
int size;
int rnd;
int val;
int rev;
treap *ls,*rs;
treap(){}
treap(int k,treap *son)
{
size=1;
rnd=rand();
val=k;
ls=rs=son;
rev=0;
}
void pushup()
{
size=ls->size+rs->size+1;
}
void pushdown()
{
if(rev)
{
rev^=1;
ls->rev^=1;
rs->rev^=1;
swap(ls,rs);
}
}
}tr[100010],nil;
typedef treap* node;
node root,cnt,null;
void init()
{
nil=treap(0,NULL);
null=&nil;
null->ls=null->rs=null;
null->size=0;
root=null;
cnt=tr;
}
node build(int x)
{
*cnt=treap(x,null);
return cnt++;
}
node merge(node x,node y)
{
if(x==null)
{
return y;
}
if(y==null)
{
return x;
}
x->pushdown();
y->pushdown();
if(x->rnd<y->rnd)
{
x->rs=merge(x->rs,y);
x->pushup();
return x;
}
else
{
y->ls=merge(x,y->ls);
y->pushup();
return y;
}
}
void split(node rt,node &x,node &y,int k)
{
if(rt==null)
{
x=y=null;
return ;
}
rt->pushdown();
if(rt->ls->size>=k)
{
y=rt;
split(rt->ls,x,y->ls,k);
rt->pushup();
}
else
{
x=rt;
split(rt->rs,x->rs,y,k-rt->ls->size-1);
rt->pushup();
}
}
void print(node rt)
{
rt->pushdown();
if(rt->ls!=null)
{
print(rt->ls);
}
printf("%d",rt->val);
if(--n!=0)
{
printf(" ");
}
if(rt->rs!=null)
{
print(rt->rs);
}
}
node build_tree(int l,int r)
{
if(l==r)
{
return build(l);
}
int mid=(l+r)>>1;
return merge(build_tree(l,mid),build_tree(mid+1,r));
}
int main()
{
init();
n=rd();
m=rd();
root=build_tree(1,n);
while(m--)
{
L=rd();
R=rd();
node x,y,z;
split(root,y,z,R);
split(y,x,y,L-1);
y->rev^=1;
root=merge(merge(x,y),z);
}
print(root);
}
非指针版
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<cstring>
using namespace std;
int n,m;
int r[100010];
int v[100010];
int s[100010][3];
int size[100010];
bool d[100010];
int root;
int tot;
int L,R;
int x,y,z;
int flag;
void pushup(int x)
{
size[x]=size[s[x][0]]+size[s[x][1]]+1;
}
int build(int x)
{
v[++tot]=x;
r[tot]=rand();
size[tot]=1;
return tot;
}
void pushdown(int x)
{
swap(s[x][0],s[x][1]);
if(s[x][0])
{
d[s[x][0]]^=1;
}
if(s[x][1])
{
d[s[x][1]]^=1;
}
d[x]=0;
}
int merge(int x,int y)
{
if(!x||!y)
{
return x+y;
}
if(r[x]<r[y])
{
if(d[x])
{
pushdown(x);
}
s[x][1]=merge(s[x][1],y);
pushup(x);
return x;
}
else
{
if(d[y])
{
pushdown(y);
}
s[y][0]=merge(x,s[y][0]);
pushup(y);
return y;
}
}
void split(int i,int k,int &x,int &y)
{
if(!i)
{
x=y=0;
return ;
}
if(d[i])
{
pushdown(i);
}
if(size[s[i][0]]<k)
{
x=i;
split(s[i][1],k-size[s[i][0]]-1,s[i][1],y);
}
else
{
y=i;
split(s[i][0],k,x,s[i][0]);
}
pushup(i);
}
void print(int x)
{
if(!x)
{
return ;
}
if(d[x])
{
pushdown(x);
}
print(s[x][0]);
if(flag==0)
{
printf("%d",v[x]);
flag=1;
}
else
{
printf(" %d",v[x]);
}
print(s[x][1]);
}
int main()
{
srand(12378);
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
root=merge(root,build(i));
}
for(int i=1;i<=m;i++)
{
scanf("%d%d",&L,&R);
split(root,L-1,x,y);
split(y,R-L+1,y,z);
d[y]^=1;
root=merge(merge(x,y),z);
}
print(root);
return 0;
}