显示代码纯文本
#include<cstdio>
#include<cmath>
using namespace std;
void swap(int &x,int &y){
int tem=x;
x=y;
y=tem;
}
struct Lump{
int siz;
int last,next;
bool rev;
int a[8000];
void insert(int x){
a[++siz]=x;
}
void out(){
for(int i=1;i<=siz;i++)printf("%d ",a[i]);
}
void Rev(){
for(int i=1;i<=siz/2;i++)swap(a[i],a[siz-i+1]);
rev=0;
}
void copy(Lump &x){
for(int i=siz/2+1;i<=siz;i++)x.a[++x.siz]=a[i];
siz/=2;
}
void get(Lump &x){
for(int i=1;i<=x.siz;i++)a[++siz]=x.a[i];
x.siz=0;
}
}lump[4000];
const int inf=100005;
int n,m,len,cnt;
int head,tail;
int st1[inf],st2[inf],top1,top2;
int get(int x){
int now=head;
while(x>lump[now].siz){
x-=lump[now].siz;
now=lump[now].next;
}
return now;//????????,???????
}
int st[400],top;
int New(){
return top?st[top--]:++cnt;
}
void split(int x){
int u=New();
if(x==tail)tail=u;
lump[u].last=x;
lump[lump[u].next=lump[x].next].last=u;
lump[x].next=u;
lump[x].copy(lump[u]);
}
void merge(int x,int y){
if(y==tail)tail=x;
st[++top]=y;
lump[x].get(lump[y]);
lump[lump[x].next=lump[y].next].last=x;
lump[y].next=lump[y].last=0;
if(lump[x].siz>2*len)split(x);
}
void change(int l,int r){
int L=get(l);
int R=get(r);
if(L==R){//?????,????
int now=head;
if(lump[L].rev)lump[L].Rev();
while(now!=L){
l-=lump[now].siz;
r-=lump[now].siz;
now=lump[now].next;
}
for(int i=l;i<(l+r+1)/2;i++){
swap(lump[L].a[i],lump[L].a[r-i+l]);
// printf("%d\n",lump[L].a[i]);
}
return ;
}
for(int i=lump[L].next;i!=R;){
int u=lump[i].next;
swap(lump[i].last,lump[i].next);
lump[i].rev^=1;
i=u;
}
if(lump[L].next!=R){//printf("%d ",2);
swap(lump[lump[L].next].next,lump[lump[R].last].last);
swap(lump[L].next,lump[R].last);
}
if(lump[L].rev)lump[L].Rev();
if(lump[R].rev)lump[R].Rev();
int now=head;
while(l>lump[now].siz){
l-=lump[now].siz;
now=lump[now].next;
}
now=head;
while(r>lump[now].siz){//printf("%d",r);
r-=lump[now].siz;
now=lump[now].next;
}
for(int i=lump[L].siz;i>=l;i--){
st1[++top1]=lump[L].a[i];
lump[L].siz--;
}
lump[R].Rev();
while(r--)st2[++top2]=lump[R].a[lump[R].siz--];
while(top1)lump[R].a[++lump[R].siz]=st1[top1--];
lump[R].Rev();
while(top2)lump[L].a[++lump[L].siz]=st2[top2--];
if(lump[L].siz>len*2)split(L);
if(lump[L].siz<len/2){
if(L==head){
if(lump[lump[L].next].rev)lump[lump[L].next].Rev();
merge(L,lump[L].next);
}
else {
if(lump[lump[L].last].rev)lump[lump[L].last].Rev();
merge(lump[L].last,L);
}
}
if(lump[R].siz>len*2)split(R);
if(lump[R].siz&&lump[R].siz<len/2){
if(lump[lump[R].last].rev)lump[lump[R].last].Rev();
merge(lump[R].last,R);
}
}
int main()
{
freopen("sph.in","r",stdin);
freopen("sph.out","w",stdout);
// freopen("1.txt","r",stdin);
// freopen("a.out","w",stdout);
scanf("%d%d",&n,&m);
len=sqrt(n);
for(int i=1;i<=n;i++){
lump[(i-1)/len+1].insert(i);
}
cnt=(n-1)/len+1;
head=1;tail=cnt;
for(int i=1;i<=cnt;i++){
if(i-1>=1)lump[i].last=i-1;
if(i+1<=cnt)lump[i].next=i+1;
}
for(int i=1;i<=m;i++){
int l,r;
scanf("%d%d",&l,&r);
change(l,r);
}
while(head){
if(lump[head].rev)lump[head].Rev();
lump[head].out();
head=lump[head].next;
}
return 0;
}
hyghb