Capella @ 2018-03-04 14:23:40
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
using std::swap;
const int MAXN=100010;
int n,m;
class FHQ_Treap
{
public:
int rt;
FHQ_Treap(void)
{
rt=cnt=0;
memset(a,0,sizeof a);
}
void Insert(int x)
{
s[++cnt]=node(x,Random(),1);
Merge(rt,rt,cnt);
}
void Reverse(int x,int y)
{
int l=0,r=0,t=0;
Split(rt,x-1,l,t),Split(t,y-x+1,t,r),s[t].lazy^=1;
Merge(l,l,t),Merge(rt,l,r);
}
void Print(void)
{
DFS(rt),putchar('\n');
}
private:
bool a[MAXN];
int cnt;
struct node
{
int v,p,size,lazy,c[2];
node(int _v=0,int _p=0,int _size=0)
{
v=_v,p=_p,size=_size,lazy=0;
memset(c,0,sizeof c);
}
}s[MAXN];
int Random(void)
{
int x;
while(a[x=rand()%MAXN]);
a[x]=1;
return x;
}
void Update(int i)
{
s[i].size=s[s[i].c[0]].size+s[s[i].c[1]].size+1;
}
void PushDown(int i)
{
int &l=s[i].c[0],&r=s[i].c[1];
swap(l,r);
if(l)
s[l].lazy^=1;
if(r)
s[r].lazy^=1;
s[i].lazy=0;
}
void Split(int i,int x,int &l,int &r)
{
if(!i)
{
l=r=0;
return;
}
int t=s[s[i].c[0]].size+1;
if(s[i].lazy)
PushDown(i);
if(x<t)
Split(s[r=i].c[0],x,l,s[i].c[0]);
else
Split(s[l=i].c[1],x-t,s[i].c[1],r);
Update(i);
}
void Merge(int &i,int l,int r)
{
if(!l || !r)
{
i=l|r;
return;
}
if(s[l].p>s[r].p)
{
if(s[l].lazy)
PushDown(l);
Merge(s[i=l].c[1],s[l].c[1],r);
}
else
{
if(s[r].lazy)
PushDown(r);
Merge(s[i=r].c[0],l,s[r].c[0]);
}
Update(i);
}
void DFS(int i)
{
if(s[i].lazy)
PushDown(i);
if(s[i].c[0])
DFS(s[i].c[0]);
printf("%d ",s[i].v);
if(s[i].c[1])
DFS(s[i].c[1]);
}
}T;
int main(int argc,char *argv[])
{
srand((unsigned)time(NULL));
scanf("%d %d",&n,&m);
for(int i=1;i<=n;++i)
T.Insert(i);
for(int i=1,l,r;i<=m;++i)
{
scanf("%d %d",&l,&r);
T.Reverse(l,r);
}
T.Print();
return 0;
}
by yyy2015c01 @ 2018-03-04 14:33:38
您可以在洛谷的在线IDE里调试……毕竟评测是Linux上的。
by Capella @ 2018-03-04 17:32:13
@yyy2015c01 好的谢谢。
by Capella @ 2018-03-04 17:32:29
@yyy2015c01 我的机子也是 Linux 啊qwq