## Ideas
题目中给出了两种操作:
1. 当 p~i~ = 0 时,表示将 a~1~, a~2~, · · · , a~qi~ 降序排列;
2. 当 p~i~ = 1 时,表示将 a~qi~ , a~qi+1~, · · · , a~n~ 升序排列。
按照题目暴力排序应该可以骗一点分,但如果想AC,就需要优化算法。可以根据测试用例的范围:1 ≤ n, m ≤ 100000,估计一下时间复杂度要控制在O(nlog n)。
首先对于连续的p=0,即:p~i~=0 q~i~=a;p~i+1~=0 q~i+1~=b。如果b>a,那么(p~i~, q~i~)的操作将无效,因为(p~i+1~, q~i+1~)已经将(p~i~, q~i~)的范围包含了。同理,如果p~i+2~=0; q~i+2~=c,而b>c,那么p~i+2~和q~i+2~的操作也将无效。
然后对于连续的p=1,即:p~i~=1 q~i~=a;p~i+1~=1 q~i+1~=b。同理,如果a<b,那么(p~i+1~, q~i+1~)的操作将无效,因为(p~i~, q~i~)已经将(p~i+1~, q~i+1~)的范围包含了。
因此我们可以总结出,对于连续的p=0和p=1,只需要分别保留q最大和q最小的那次操作即可。
有了上面的简化之后,整个操作序列其实就被压缩成了p=0和p=1的交替操作,由于一开始的序列是升序排列的,所以第一个有效操作肯定是p~i~ = 0,让我们将某一个前缀降序排列。
我们举个例子来分析一下,令n=9,即[1, 2, 3, 4, 5, 6, 7, 8, 9]:
1. p=0,q=3,即1~3位置降序排,变成了[3, 2, 1, 4, 5, 6, 7, 8, 9]
2. p=1,q=7,即7~9位置升序排,不发生变化,还是[3, 2, 1, 4, 5, 6, 7, 8, 9]
3. p=0,q=6,即1~6位置降序排,变成了[6, 5, 4, 3, 2, 1, 7, 8, 9]
4. p=1,q=4,即4~9位置升序排,变成了[6, 5, 4, 1, 2, 3, 7, 8, 9]
5. p=0,q=5,即1~5位置降序排,变成了[6, 5, 4, 2, 1, 3, 7, 8, 9]
通过这个例子我们可以发现一些规律,有些数字的位置被固定下来了,基本不会变。
为了会这样呢?我们分析一下。
对于第1次有效操作,假设是将[1, x]降序排列,由于最初我们的数据都是升序的,所以∀b∈[x+1, n] > ∀a∈[0, x]。
那么之后我们对[y, n]升序排列(y<=x) 的话其实[x, n]这部分是不变的。
这是因为[y, x] ∈ [0, x] < [x+1, n],所以[x+1, n]这部分的任意值是始终大于[y, x]中的任意值。
因此我们对[y, n]升序排序的话,其实[x, n]这部分不会挪动位置,换句话说,[x, n]已经被固定下来了。
同理,[1, y]其实也被固定下来了,所以说我们不停的操作其实就是不停的从数组的两边向中间固定元素。
我们可以用两个变量 left 和 right,分别表示数组的两边被固定下来的位置,left 不断增加,right 不断减小,最终数组被固定。
最后扣一下边界,如果最后一次操作是前缀降序,那相当于确定一个[x, n],我们手动把一个[i, x]确定下来就可以了,反之亦然。
## Code
### Python
```python
if __name__ == '__main__':
n, m = map(int, input().split())
nums = [i + 1 for i in range(n)]
seq = [] # 用于存储操作序列
for _ in range(m):
p, q = map(int, input().split())
if p == 0:
while seq and seq[-1][0] == 0: # 如果是连续的 p = 0,只取最大的 q
q = max(q, seq[-1][1])
seq.pop()
while len(seq) > 1 and seq[-2][1] <= q: # 如果此次前缀降序的右边界大于上一次前缀降序的有边界,可以省略在此之前的两次操作
seq.pop()
seq.pop()
seq.append((0, q))
elif seq: # seq 不为空保证这是有一个 p = 0 之后的 p = 1 操作
while seq and seq[-1][0] == 1: # 如果是连续的 p = 1,只取最小的 q
q = min(q, seq[-1][1])
seq.pop()
while len(seq) > 1 and seq[-2][1] >= q: # 如果此次后缀升序的左边界小于上一次后缀升序的有边界,可以省略在此之前的两次操作
seq.pop()
seq.pop()
seq.append((1, q))
k, left, right = n, 1, n
for i in range(len(seq)):
if seq[i][0] == 0: # 前缀降序
while right > seq[i][1] and left <= right:
nums[right - 1] = k # 从后往前设置
right -= 1
k -= 1
else: # 后缀升序
while left < seq[i][1] and left <= right:
nums[left - 1] = k # 从前往后设置
left += 1
k -= 1
if left > right:
break
if len(seq) % 2: # 最后一次操作为前缀降序
while left <= right:
nums[left - 1] = k
left += 1
k -= 1
else: # 最后一次操作为后缀升序
while left <= right:
nums[right - 1] = k
right -= 1
k -= 1
print(' '.join(map(str, nums)))
```
没有合适的资源?快使用搜索试试~ 我知道了~
蓝桥杯备战.zip蓝桥杯备战.zip蓝桥杯备战.zip
共1883个文件
py:660个
txt:605个
cpp:138个
需积分: 5 1 下载量 2 浏览量
2024-01-08
11:18:57
上传
评论
收藏 39.57MB ZIP 举报
温馨提示
蓝桥杯备战.zip蓝桥杯备战.zip蓝桥杯备战.zip蓝桥杯备战.zip
资源推荐
资源详情
资源评论
收起资源包目录
蓝桥杯备战.zip蓝桥杯备战.zip蓝桥杯备战.zip (1883个子文件)
18023309 29KB
18023309 14KB
18023309 14KB
18023309 13KB
18023309 13KB
18023309 9KB
18023309 9KB
18023309 9KB
18023309 9KB
18023309 9KB
18023309 8KB
18023309 8KB
19103117 8KB
19103117 8KB
19103213 13KB
19103213 13KB
19103213 13KB
19103213 13KB
19103213 13KB
19103213 9KB
19103213 9KB
19103213 9KB
19103213 8KB
19103213 8KB
19103214 8KB
19103214 8KB
19103224 14KB
19103224 8KB
19103224 8KB
19103325 8KB
19103325 8KB
19103328 14KB
19103328 9KB
19103328 8KB
19103328 8KB
19103328 8KB
19103411 8KB
19103411 8KB
19103429 8KB
19103429 8KB
19103429 8KB
19103429 8KB
19105133 8KB
19103429.c 2KB
19103325.c 959B
19105133.c 952B
19103429.c 788B
19103328.c 733B
19103429.c 625B
19103224.c 446B
19103429.c 412B
19103325.c 345B
19103325.c 329B
19103328.c 239B
19103328.c 218B
19103328.c 180B
template.cpp 4KB
code.cpp 3KB
template.cpp 3KB
18023309.cpp 3KB
code.cpp 2KB
18023309.cpp 2KB
18023309.cpp 2KB
18023309.cpp 2KB
c++.cpp 2KB
18023309.cpp 1KB
code.cpp 1KB
code.cpp 1KB
18023309.cpp 1KB
18023309.cpp 1KB
solve.cpp 1KB
code.cpp 1KB
19103213.cpp 1KB
19103213.cpp 1KB
shareStack.cpp 1KB
19103224.cpp 1KB
code.cpp 1KB
code.cpp 1KB
c++.cpp 1KB
code.cpp 1KB
c++.cpp 1KB
c++.cpp 1KB
19103214.cpp 1KB
c++.cpp 1KB
18023309.cpp 1KB
19103213.cpp 1KB
18023309.cpp 1KB
code.cpp 1KB
18023309.cpp 1KB
code.cpp 1008B
code.cpp 1000B
18023309.cpp 993B
solve.cpp 990B
code.cpp 988B
code.cpp 964B
19103213.cpp 930B
code.cpp 929B
19103328.cpp 923B
19103224.cpp 919B
19103328.cpp 892B
共 1883 条
- 1
- 2
- 3
- 4
- 5
- 6
- 19
资源评论
xiaoshun007~
- 粉丝: 3777
- 资源: 3146
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功