#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<int,int>PII;
typedef pair<double,double>PDD;
typedef long long LL;
typedef unsigned long long ull;
#define N 100005
PII arr[N];
int ans[N];
int main()
{
int n,m,p,q,j=1;
scanf("%d%d",&n,&m);
if(n==1)
{
printf("1\n");
return 0;
}
for(int i=1;i<=m;i++)
{
scanf("%d%d",&p,&q);
if(arr[1].y!=0)
{
if(p==0)
{
if(arr[j].x==0)
{
q=max(arr[j--].y,q);
}
while(j>=2&&arr[j-1].y<=q)
{
j-=2;
}
}
else
{
if(arr[j].x==1)
{
q=min(arr[j--].y,q);
}
while(j>=2&&arr[j-1].y>=q)
{
j-=2;
}
}
arr[++j].x=p;
arr[j].y=q;
}
else
{
if(p==0&&q!=0)
{
arr[j].x=p;
arr[j].y=q;
}
}
}
int k=1,l=n,o=n;
for(int i=1;i<=j;i++)
{
if(arr[i].x==0&&k<=l)
{
while(l-arr[i].y)
{
ans[l--]=o--;
}
}
else
{
while(arr[i].y-k&&k<=l)
{
ans[k++]=o--;
}
}
}
if(j%2)
{
while(k<=l)
{
ans[k++]=o--;
}
}
else
{
while(k<=l)
{
ans[l--]=o--;
}
}
for(int i=1;i<=n;i++)
{
if(i==1)
{
printf("%d",ans[i]);
}
else
{
printf(" %d",ans[i]);
}
}
printf("\n");
return 0;
}
参考yxc大佬的方法
|