给定序列 (a1,a2,⋅⋅⋅,an)=(1,2,⋅⋅⋅,n),即 ai=i。

小蓝将对这个序列进行 m 次操作,每次可能是将 a1,a2,⋅⋅⋅,aqi降序排列,或者将 aqi,aqi+1,⋅⋅⋅,an 升序排列。

请求出操作完成后的序列。

输入格式

输入的第一行包含两个整数 n,m,分别表示序列的长度和操作次数。

接下来 m 行描述对序列的操作,其中第 i 行包含两个整数 pi,qi 表示操作类型和参数。当 pi=0 时,表示将 a1,a2,⋅⋅⋅,aqi
降序排列;当 pi=1 时,表示将 aqi,aqi+1,⋅⋅⋅,an 升序排列。

输出格式

输出一行,包含 n 个整数,相邻的整数之间使用一个空格分隔,表示操作完成后的序列。

数据范围

对于 30% 的评测用例,n,m≤1000;
对于 60% 的评测用例,n,m≤5000;
对于所有评测用例,1≤n,m≤10^5,0≤pi≤1,1≤qi≤n。

输入样例:
3 3 0 3 1 2 0 2
输出样例:
3 1 2
样例解释

原数列为 (1,2,3)。

第 1 步后为 (3,2,1)。

第 2 步后为 (3,1,2)。

第 3 步后为 (3,1,2)。与第 2 步操作后相同,因为前两个数已经是降序了。

分析:我们先来简单地分析几种特殊的情况,以降序为例,假如我们有两个连续命令,一个是将1~a降序,另一个是将1~b降序,这时候a和b有三种大小关系,若a和b相等,则两个命令是等价的,只需执行一个即可,若a>b,由于一开始已经将1~a降序排列了,那么显然1~b本身就是降序,所以没必要执行后一个命令,那假如a<b呢?这时候我们必须要执行后一个命令了,但是前一个命令的执行又有什么意义呢?因为他已经被后面的命令所包含了,分析这个例子我们不难得出,
当多个连续的降序命令需要被执行时,我们只需要执行边界最靠右的那个即可(因为左边界均为1),其余命令都是多余的,同理,简单分析就可以得
当多个连续的升序命令需要被执行时,我们只需要执行边界最靠左的那个即可
(因为右边界均为n),其他命令也是多余的。这样处理完答案后我们所需要执行的命令就是升序和降序相间排布的,就是一个升序接着一个降序再接着一个升序……,当然,仅仅这样处理后还不行,我们还需要对命令进行其他处理:

我们假设前i个降序命令的右边界是递减的,升序命令左边界是递增的(为了归纳证明有效命令是符合这种规律的)
,第i个命令是对1~a降序,第i+1个命令是对b~n升序,第i+2个命令是对1~a+x降序

由于前i个
降序命令的右边界是递减的,升序命令左边界是递增的,所以我们每次更新到的都只能时两个相邻命令区间的交界部分,而且越来越小,突然降序命令的右边界出现了一个大于之前的数(升序命令左边界出现了一个小于之前的数也是同样的分析方式),那我们看看可以怎样简化命令,之前的分析能够让我们知道,我们第i个命令和第i+1个命令能够更新到的数只有区间[b,a]上的数(因为
前i个
降序命令的右边界是递减的,升序命令左边界是递增的,也就是b左边的区间和a右边的区间已经是有序的了),但是这个区间的数被区间[1,a+x]覆盖了,那么之前两个命令进行的更新都会被这次的命令重新打乱,所以说前两个命令就可以直接舍去,直到找到一个降序命令有边界大于a+x为止,所以说我们
最终有效命令中降序命令的右边界是递减的,升序命令左边界是递增的。

题目分析到这就把命令处理完了,处理答案的方法在代码中:
#include<cstdio> #include<iostream> #include<cstring> #include<vector>
#include<algorithm> #include<map> #include<cmath> #include<queue> using
namespace std; const int N=100010; typedef pair<int,int> PII; PII stk[N]; int
ans[N],top; int main() { int n,m; cin>>n>>m; while(m--) { int p,q;
scanf("%d%d",&p,&q); if(!p) { while(top&&stk[top].first==0)
q=max(q,stk[top--].second);//求出连续的降序命令中的最大右边界
while(top>=2&&stk[top-1].second<=q) top-=2;//若当前右边界大于上一命令的右边界,则上一命令无效
stk[++top]={0,q};//把当前命令入栈 } else if(top) { while(top&&stk[top].first==1)
q=min(q,stk[top--].second);//求出连续的升序命令中的最大左边界
while(top>=2&&stk[top-1].second>=q) top-=2;//若当前左边界小于上一命令的左边界,则上一命令无效
stk[++top]={1,q};//把当前命令入栈 } } int k=n,l=1,r=n; for(int i=1;i<=top;i++) {
if(stk[i].first==0) while(r>stk[i].second&&l<=r) ans[r--]=k--; else
while(l<stk[i].second&&l<=r) ans[l++]=k--; if(l>r) break; } if(top%2)//应该处理升序命令
while(l<=r) ans[l++]=k--; else//应该处理降序命令 while(l<=r) ans[r--]=k--; for(int
i=1;i<=n;i++) printf("%d ",ans[i]); return 0; }

技术
©2019-2020 Toolsou All rights reserved,
Python学习笔记(一)Linux【shell】 shell编程创建一个线程——— Javaweb (3)evo工具使用问题——Degenerate covariance rank, Umeyama alignment is not possibleVMware 16安装centos 7详细教程C语言做一个简易的登陆验证(功能)界面C语言——qsort函数Spring Boot面试必问:自动配置原理Android EditText密码显示隐藏Qt入门教程【基础控件篇】QCalendarWidget日历控件