牛客 区间翻转

牛客 区间翻转
小明拿到了一个排列，最开始的排列顺序是
{
1
,
2
,
3
,
4
,
…
…
n
}
{1,2,3,4,……n} ，即顺序排列。
小明进行了
k
k 次操作，每次操作他选择一个区间
[
l
,
r
]
[l,r] 进行翻转。
保证翻转的区间的起始点和终点都是非递减的，即记两次操作为
i
i 和
j
j ，若
i
<
j
i<j，必有
l
i
≤
l
j
l
i
​
≤l
j
​
且
r
i
≤
r
j
r
i
​
≤r
j
​
。
小明想知道，所有操作结束之后，排列顺序是什么？
输入描述：
第一行输入两个正整数
n
n 和
k
k ，分别代表排列的数字个数、翻转的次数。
(
1
≤

n
,
k
≤
1
0
5
)
(1≤ n,k≤10
5
)
接下来的
k
k 行，每行输入两个正整数
l
l 和
r
r ，代表翻转的区间。
(
1
≤
l
,
r
≤
n
)
(1≤l,r≤n)
输出描述：
输出
n
n 个数，每两个数用空格隔开，代表最终的排列。

include

include

include

using namespace std;
using ll=long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr),cout.tie(nullptr);
ll n,k;
cin>>n>>k;
dequehuo;
ll l=1;
ll r=1;
bool nx=false;
while(k--)
{
ll left,right;
cin>>left>>right;
while(l<left)
{
if(huo.empty())
{
cout<<l<<" ";
l++;
if(r<l)r++;
continue;
}
else{
if(nx)
{
cout<<huo.back()<<" ";
huo.pop_back();
}
else if(!nx)
{
cout<<huo.front()<<" ";
huo.pop_front();
}
}
l++;
if(r<l)r++;
}
while(r<=right)
{
if(nx)huo.push_front(r);
else if(!nx)huo.push_back(r);
r++;
}
nx=!nx;
}
while(!huo.empty())
{
if(nx)
{
cout<<huo.back()<<" ";
huo.pop_back();
}
else
{
cout<<huo.front()<<" ";
huo.pop_front();
}
}
while(r<=n)
{
cout<<r<<" ";
r++;
}

return 0;

}