题意：
定义一个数组是好的，仅当其可分割成两个非空数组，使得左边元素都小于右边元素
即满足 max(al…ak) ≤ min(ak + 1…ar)
给定排列，q次查询，问 [l, r] 的子数组是否是好的
(n, q ≤ 3e5)
解析：
固定 l，r，若枚举 k，左右两侧都是单增，因此整体不存在单调性
法 1：
二维离线
从值考虑
我们考虑左侧区间中的最大值，
若 ai
成为最大值，我们记 i 左侧第一个大于 ai 的元素位置为
l1，则有限制 l1 < L ≤ i
我们记 i 右侧第一个大于 ai 的元素位置为
r1，记 r1 右侧第一个小于 ai 的元素位置为
r2，则有限制 r1 ≤ R < r2
这样的 [L, R] 就是左侧以 ai
为最大值的好区间
( i 左右找 > ai
的第一个位置是很典的问题，可以用单调队列，笛卡尔树，按值枚举甚至还可以用
set )
也就是，以 ai
为最大的合法情况落在矩阵 L ∈ [l1 + 1, i], R ∈ [r1, r2 − 1]
上
我们维护合法情况，离线所有查询，以 r 升序
从左向右枚举 i
当遍历到 r1
时，我们对 [l1 + 1, i]
区间+1，遍历到 r2
时，对 [l1 + 1, i]
区间-1，正值则代表该点合法
然后对 R=i 的查询， L 是否合法即可
trick：
在此过程中，我们需要 区间加&单点查
实现上可使用树状数组维护差分
区间加相当于在差分数组上单点修改，对某点的查询相当于差分数组的前缀和
(当然直接用线段树也是可以的喵)
时间复杂度 O(n + q)log
MYCODE
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
| #include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
struct BIT{
int n;
vector<ll> tree;
BIT(int _n) : n(_n){
tree.resize(n + 1);
}
void add(int x, ll v){
for(int i=x; i<=n; i+=i&-i){
tree[i] += v;
}
}
ll query(int x){
ll ans = 0;
for(int i=x; i>=1; i-=i&-i){
ans += tree[i];
}
return ans;
}
ll query(int x, int y){
return query(y) - query(x - 1);
}
};
void solve(){
int n;
cin >> n;
vector<int> a(n + 1);
vector<int> idx(n + 1);
for(int i=1; i<=n; i++){
cin >> a[i];
idx[a[i]] = i;
}
int q;
cin >> q;
vector<vector<pii>> qry(n + 1);
for(int i=1; i<=q; i++){
int l, r;
cin >> l >> r;
qry[r].push_back({l, i});
}
vector<int> L(n + 2), R(n + 2), Rle(n + 2);
{
set<int> st{0, n+1};
for(int i=n; i>=1; i--){
int p = idx[i];
L[p] = *prev(st.lower_bound(p));
R[p] = *st.lower_bound(p);
st.insert(p);
}
}
{
set<int> st{0, n+1};
for(int i=1; i<=n; i++){
int p = idx[i];
Rle[p] = *st.lower_bound(R[p]);
st.insert(p);
}
}
vector<vector<pii>> add(n + 2), del(n + 2);
for(int i=1; i<=n; i++){
int r1 = R[i];
int r2 = Rle[i];
if(L[i]+1<=i && r1 < r2){
add[r1].push_back({L[i], i});
del[r2].push_back({L[i], i});
}
}
vector<bool> ans(q + 1);
BIT bit(n+1);
for(int i=1; i<=n; i++){
for(auto[l, i] : add[i]){
bit.add(l+1, 1);
bit.add(i+1, -1);
}
for(auto[l, i] : del[i]){
bit.add(l+1, -1);
bit.add(i+1, 1);
}
for(auto[L, i] : qry[i]){
ans[i] = (bit.query(L)>0);
}
}
for(int i=1; i<=q; i++){
cout << (ans[i]? "Yes":"No") << '\n';
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1;
while(t--) solve();
return 0;
}
|
法 2：
RMQ 在线查询 & 跳表求离散数组最值
这种想法比较直接
我们直接固定 l，从 l 向右建单调队列
显然，ax
能成为最大值，仅当 ax
在单调队列里存在
我们枚举 ax，令 r1 为第一个满足 ar1 > ax
位置，令 r2
为第一个满足 r2 > r1, ar2 < ax
的位置
则合法的 R ∈ [r1, r2 − 1]
只需要在所有 ax 中找最远的
R
在以 l 为左端点的询问中，r ≤ R 即为 “Yes”
现在考虑如何快速的在离散的 ax 中找到最大
R
可以使用 st 表
若是连续区间，对两个长度为 2k − 1 区间求 max
即可
但离散的 ax
就不能这样了
我们需要先处理出从 x 后第 2k − 1
个元素的下标，也就是 nxt 表 (st表)
然后就能求离散数组的 max 了
具体实现参考代码
MYCODE
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
| #include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MX = 3e5;
vector<int> LOG(MX + 1);
void init(){
for(int i=2; i<=MX; i++){
LOG[i] = LOG[i>>1] + 1;
}
}
void solve(){
int n;
cin >> n;
vector<int> a(n + 1);
vector<int> idx(n + 1);
for(int i=1; i<=n; i++){
cin >> a[i];
idx[a[i]] = i;
}
vector<int> R(n + 2), Rle(n + 2);
{
set<int> st{0, n+1};
for(int i=n; i>=1; i--){
int p = idx[i];
R[p] = *st.lower_bound(p);
st.insert(p);
}
}
{
set<int> st{0, n+1};
for(int i=1; i<=n; i++){
int p = idx[i];
Rle[p] = *st.lower_bound(R[p]);
st.insert(p);
}
}
int m = LOG[n];
vector<vector<int>> nxt(n + 2, vector<int>(m + 1)), mx = nxt;
for(int i=1; i<=n; i++){
nxt[i][0] = R[i];
mx[i][0] = Rle[i]-1;
}
for(int k=1; k<=m; k++){
for(int i=1; i<=n; i++){
nxt[i][k] = nxt[nxt[i][k-1]][k-1];
mx[i][k] = max(mx[i][k-1], mx[nxt[i][k-1]][k-1]);
}
}
auto get = [&](int l, int r){
int R = 0, x = l;
for(int k=m; k>=0; k--){
if(nxt[x][k] && nxt[x][k] <= r){
R = max(R, mx[x][k]);
x = nxt[x][k];
}
}
return R;
};
int q; cin>>q;
for(int i=1; i<=q; i++){
int l, r;
cin >> l >> r;
int R = get(l, r);
cout << (r<=R? "Yes":"No") << '\n';
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
init();
int t = 1;
while(t--) solve();
return 0;
}
|
.jpg){kind=avatar}
