#include<bits/stdc++.h>
using namespace std;
struct node{
int l;
int r;
int val;
int key;
int sz;
int lz;
}fhq[100010];
int root;
int cnt;
void update(int now)
{
fhq[now].sz = 1+fhq[fhq[now].l].sz+fhq[fhq[now].r].sz;
}
int newnode(int val)
{
fhq[++cnt].val=val;
fhq[cnt].key=rand();
fhq[cnt].sz=1;
return cnt;
}
void pushdown(int now)
{
if(fhq[now].lz)
{
swap(fhq[now].l,fhq[now].r);
fhq[fhq[now].l].lz^=1;
fhq[fhq[now].r].lz^=1;
fhq[now].lz=0;
}
}
void split(int now,int size,int &x,int &y)
{
if(!now)
{
x=0,y=0;
return ;
}
pushdown(now);
if(size>fhq[fhq[now].l].sz)
{
x=now;
split(fhq[now].r,size-fhq[fhq[now].l].sz-1,fhq[now].r,y);
}
else
{
y=now;
split(fhq[now].l,size,x,fhq[now].l);
}
update(now);
int merge(int x,int y)
{
if(!x || !y)
return x+y;
if(fhq[x].key<fhq[y].key)
{
pushdown(x);
fhq[x].r=merge(fhq[x].r,y);
update(x);
return x;
}
else
{
pushdown(y);
fhq[y].l=merge(x,fhq[y].l);
update(y);
return y;
}
}
void dfs(int now)
{
if(!now) return ;
pushdown(now);
dfs(fhq[now].l);
cout<<fhq[now].val<<" ";
dfs(fhq[now].r);
}
void reverse(int l,int r)
{
int x,y,z;
split(root,l-1,x,y);
split(y,r-l+1,y,z);
fhq[y].lz^=1;
root=merge(x,merge(y,z));
}
int main()
{
srand(time(NULL));
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
{
int x;
cin>>x;
root=merge(root,newnode(x));
}
while(m--)
{
int l,r;
cin>>l>>r;
reverse(l,r);
}
dfs(root);
return 0;
}
京公网安备 11010502036488号