题意
略
题解
Step1:
对于连续的同一种指令,易推论,覆盖范围最广的指令会覆盖掉其他指令。
例如,
p = 0, q = 3
会被p = 0, q = 5
覆盖掉 ,p = 1, q = 5
会被p = 1, q = 3
覆盖掉。故对于连续的同种指令,我们只需要保留覆盖范围最大的一个指令即可。因此,在所有指令中,升序、降序操作是相间执行的。
Step2:
1.当前指令与上一条指令的覆盖范围不相交,则滤过这条指令。
例如:
原数组:
[1, 2, 3, 4, 5, 6, 7]
p = 0, q = 5
,对区间[1, 5]
逆置操作,[5, 4, 3, 2, 1, 6, 7]
p = 1, q = 3
,对相交区间[3, 5]
逆置操作,[5, 4, 1, 2, 3, 6, 7]
p = 0, q = 3
,此时[1, 3]
与[3, 7]
并不相交,上一步的逆置并没有改变[1, 3]
的顺序,故这一指令不需要做任何操作。2.当前指令与上一条指令的覆盖范围相交。
(1)若该相交的范围在上一对指令的相交范围之内,则对此时相交的范围进行逆置即可。
例如:
原数组:
[1, 2, 3, 4, 5, 6, 7]
p = 0, q = 5
,对区间[1, 5]
逆置操作,[5, 4, 3, 2, 1, 6, 7]
p = 1, q = 3
,对相交区间[3, 5]
逆置操作,[5, 4, 1, 2, 3, 6, 7]
p = 0, q = 4
,对相交区间[3, 4]
逆置操作,[5, 4, 2, 1, 3, 6, 7]
(2)若该相交的范围不在上一对指令的相交范围之内,则此时的操作将会覆盖掉上一对指令的操作,即上一对操作是无效操作。
例如:
原数组:
[1, 2, 3, 4, 5, 6, 7]
p = 0, q = 5
,对区间[1, 5]
逆置操作,[5, 4, 3, 2, 1, 6, 7]
p = 1, q = 3
,对相交区间[3, 5]
逆置操作,[5, 4, 1, 2, 3, 6, 7]
p = 0, q = 6
,相交区间[3, 6]
不在区间[3, 5]
之内,无法通过逆置达到指令目的,需要对区间[1, 6]
进行排序,[6, 5, 4, 3, 2, 1, 7]
若进行排序操作,会使总复杂度上升至O(n^3),导致TLE。值得注意的是,若当前相交的范围不在上一对指令的相交范围之内,那么此时我们的sort会覆盖上两条指令的操作,也就是说,上两条指令是无效的,可以滤过。若滤过上两条指令后,依旧出现如上情况则继续重复滤过操作,直至变成第一(1)种情形。
以上述例子为例,滤过前两条指令,得:
原数组:
[1, 2, 3, 4, 5, 6, 7]
p = 0, q = 6
,对区间[1, 6]
逆置操作,[6, 5, 4, 3, 2, 1, 7]
此时我们通过逆置得到的数组,与原操作是等效的。
Step3:
通过上述步骤的处理,所有指令变成了在一个范围的子范围内不断进行逆置操作的过程。在此过程中,由于范围是不断在缩小的,故范围外的值一旦确定便不会再进行更改,可以通过向数组填数达到最终的目的,详见代码。
CODE
#python3
N = int(1e5 + 10)
class PII: #定义pair
def __init__(self, x, y):
self.x = x
self.y = y
def update(self, x, y):
self.x = x
self.y = y
n, m = map(int, input().split())
stk = [PII(0, 0) for i in range(N)]
ans = [0 for i in range(N)]
top = 0
for i in range(m):
p, q = map(int, input().split())
if p == 0:
if top:
if stk[top].x == 0: #Step1
q = max(q, stk[top].y)
top -= 1
else:
if q <= stk[top].y: #Step2(1)
continue
while top >= 2 and stk[top - 1].y <= q: #Step2(2)
top -= 2
top += 1
stk[top].update(0, q) #Step1
elif top:
if top:
if stk[top].x == 1: #Step1
q = min(q, stk[top].y)
top -= 1
else:
if q >= stk[top].y: #Step2(1)
continue
while top >= 2 and stk[top - 1].y >= q: #Step2(2)
top -= 2
top += 1
stk[top].update(1, q) #Step1
k, l, r = n, 1, n
for i in range(1, top + 1): #Step3
if stk[i].x == 0:
while r > stk[i].y and l <= r:
ans[r] = k
r -= 1
k -= 1
else:
while l < stk[i].y and l <= r:
ans[l] = k
l += 1
k -= 1
if (l > r): #若已经填满了答案数组,则无需继续操作(该操作可有可无)
break
if (top % 2): #填充剩下的答案数组
while l <= r:
ans[l] = k
l += 1
k -= 1
else:
while l <= r:
ans[r] = k
r -= 1
k -= 1
for i in range(1, n + 1):
print(ans[i], end = ' ')
//c++
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<int, int> PII;
const int N = 1e5 + 10;
int n, m;
PII stk[N];
int ans[N];
int main(){
scanf("%d%d", &n, &m);
int top = 0;
while (m -- ){
int p, q;
scanf("%d%d", &p, &q);
if (!p){
if (top){
if (stk[top].x == 0)
q = max(q, stk[top --].y);
else
if (q <= stk[top].y)
continue;
}
while (top >= 2 && stk[top - 1].y <= q) top -= 2;
stk[ ++ top] = {0, q};
}
else if (top){
if (top){
if (stk[top].x == 1)
q = min(q, stk[top --].y);
else
if (q >= stk[top].y)
continue;
}
while (top >= 2 && stk[top - 1].y >= q) top -= 2;
stk[ ++ top] = {1, q};
}
}
int k = n, l = 1, r = n;
for (int i = 1; i <= top; i ++ ){
if (stk[i].x == 0)
while (r > stk[i].y && l <= r) ans[r --] = k --;
else
while (l < stk[i].y && 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;
}
stk[top - 1].y >= q这一步是怎么做到那个操作的
stk[top - 1].y >= q这一步是什么意思啊
题解写得很认真,就是举例子的时候写错了很多:原数组{1,2,3,4,5,6,7},长度为7,当p = 1, q = 3,难道不是应该对区间[3, 7]进行升序操作吗,为什么是区间[3,5]? 然后2.(2)中p = 0, q = 6,操作完的结果不是应该影响到第6位吗(应该为{6, 5, 4, 3, 2, 1, 7}),为什么是{5, 4, 3, 2, 1, 6, 7}?
第一个逆置相交区间就可以了;第二个应该就是单纯的写题解没注意然后写错了,感谢提醒,已更正。