CF1904D2 Set To Max (D2)

发表于 更新于 分类于

题意

给定两个长度为\(n\)的序列\(a\)和\(b\)，每次操作可以选择一对\(\{l,r\}\)，将\(a_l, a_{l+1}, a_{l+2}...a_r\)变为其中的最大值，问是否能将\(a\)变为\(b\)。

思路

考虑能让\(a_i\)变成\(b_i\)的条件，分为三种情况：

  1. \(a_i=b_i\)，则必然可以。
  2. \(a_i> b_i\)，可知一定无解。
  3. \(a_i<b_i\)，则需要从两边寻找一个\(a_j=b_i\)使得\(a_i\)变成\(b_i\)。

对于第三种情况，可以发现如果要在不影响其他位置成立的情况下使得\(a_i\)变成\(b_i\)，其充分必要条件是对于\(a_{i...j}\)与\(b_{i...j}\)，满足 \[ a_k \leq b_i, for\ k\in[i, j]\\\ b_k \geq b_i, for\ k\in[i, j] \] 可以简化为 \[ max_{k=i}^{j}a_k\leq b_i \leq min_{k=i}^{j}b_k \]

从前往后、从后往前分别扫一遍，最值操作用st表或线段树预处理即可，时间复杂度\(\Theta(n log_2n)\)。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
// Problem: D2. Set To Max (Hard Version)
// Contest: Codeforces - Codeforces Round 914 (Div. 2)
// URL: https://codeforces.com/contest/1904/problem/D2
// Memory Limit: 256 MB
// Time Limit: 4000 ms
// Auther : MaxDYF
// 
// Powered by CP Editor (https://cpeditor.org)
//#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 10;
const int inf = 1 << 30;
const long long llinf = 1ll << 60;
const double PI = acos(-1);

#define lowbit(x) (x&-x)
typedef long long ll;
typedef double db;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<db, db> pdd;
typedef pair<ll, int> pli;

int n, m, k, q;
int a[N];
int b[N];
int vis[N];
int l2[N];
int st1[N][30], st2[N][30];
int lst[N];
void work()
{
	cin >> n;
	fill(vis, vis + n + 1, 0);
	
	for (int i = 1; i <= n; i++)
		for (int j = 0; j <= l2[n]; j++)
		{
			st1[i][0] = 0;
			st2[i][0] = inf;
		}
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
		st1[i][0] = a[i];
	}	
	for (int i = 1; i <= n; i++)
	{
		cin >> b[i];
		st2[i][0] = b[i];
	}
	for (int t = 1; t <= l2[n]; t++)
		for (int i = 1; i + (1 << t) - 1 <= n; i++)
			st1[i][t] = max(st1[i][t - 1], st1[i + (1 << (t - 1))][t - 1]);
	
	for (int t = 1; t <= l2[n]; t++)
		for (int i = 1; i + (1 << t) - 1 <= n; i++)
			st2[i][t] = min(st2[i][t - 1], st2[i + (1 << (t - 1))][t - 1]);
	auto query1 = [&](int l, int r)
	{
		int t = l2[r - l + 1];
		return max(st1[l][t], st1[r - (1 << t) + 1][t]);
	};
	auto query2 = [&](int l, int r)
	{
		int t = l2[r - l + 1];
		return min(st2[l][t], st2[r - (1 << t) + 1][t]);
	};
	fill(lst, lst + n + 1, -1);
	for (int i = 1; i <= n; i++)
	{
		lst[a[i]] = i;
		if (a[i] == b[i])
		{
			vis[i] = 1;
			continue;
		}
		if (lst[b[i]] == -1)
			continue;
		if (query1(lst[b[i]], i) <= b[i] && query2(lst[b[i]], i) >= b[i])
			vis[i] = true;
	}
	fill(lst, lst + n + 1, -1);
	for (int i = n; i >= 1; i--)
	{
		lst[a[i]] = i;
		if (a[i] == b[i])
		{
			vis[i] = 1;
			continue;
		}
		if (lst[b[i]] == -1)
			continue;
		if (query1(i, lst[b[i]]) <= b[i] && query2(i, lst[b[i]]) >= b[i])
			vis[i] = true;
	}
	bool suc = 1;
	for (int i = 1; i <= n; i++)
		if (!vis[i])
		{
			suc = 0;
			break;
		}
	cout << (suc ? "YES\n" : "NO\n");
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	l2[1] = 0;
	for (int i = 2; i < N; i++)
		l2[i] = l2[i / 2] + 1;
	int t;
	
	cin >> t;
	while (t --> 0)
	{
		work();
	}
}