我们惺惺相惜
[题目链接](https://www.nowcoder.com/practice/e5cb693b91fe405e8aa233503b7fced5)
思路
核心转化：Dilworth 定理
题目要求判断子数组 能否分成两个非空的严格递增子序列。由 Dilworth 定理，一个序列能被划分成至多
条严格递增子序列，当且仅当最长非递增子序列的长度不超过
。
注意，如果子数组本身就是严格递增的，我们也可以把它拆成两个非空部分，两部分各自严格递增。因此只要子数组长度 且能被至多 2 条严格递增子序列覆盖，答案就是 YES。
等价条件：子数组 是"好区间"
且不存在三元组
满足
。
如何高效判断？
对每个位置 ，预处理两个值：
：最大的
使得
（不存在则为
）。
：最小的
使得
（不存在则为
）。
这两个数组都可以用单调栈在 时间内求出。
有了这两个数组，判定条件变为：子数组 中存在非递增三元组
存在某个
，使得
且
。
离线 + 线段树
将所有询问按 从大到小排序。从
递减到
：
- 当处理到
时，把所有满足
的位置
激活，在线段树的
- 对于
，在线段树上查询
的最小值。若最小值
，说明存在非递增三元组，答案为 NO；否则为 YES。
正确性解释： 当 递减时，条件
等价于
在
范围内。由于
是最靠右的满足
的位置，一旦
，就保证在
中确实存在
的元素。线段树维护的是所有已激活位置的
最小值，查询
恰好是在检查有没有合法的中间点
。
举例
以样例 ，查询
为例：
（
），
（
）
- 当
时，
已激活（因
），查询
得到
存在三元组 ：
，所以答案 NO。
代码
#include <bits/stdc++.h>
using namespace std;
struct SegTree {
int n;
vector<int> tree;
void init(int _n) {
n = _n;
tree.assign(4 * n, INT_MAX);
}
void update(int pos, int val, int node, int lo, int hi) {
if (lo == hi) {
tree[node] = min(tree[node], val);
return;
}
int mid = (lo + hi) / 2;
if (pos <= mid) update(pos, val, 2*node, lo, mid);
else update(pos, val, 2*node+1, mid+1, hi);
tree[node] = min(tree[2*node], tree[2*node+1]);
}
void update(int pos, int val) { update(pos, val, 1, 1, n); }
int query(int l, int r, int node, int lo, int hi) {
if (l > r) return INT_MAX;
if (l <= lo && hi <= r) return tree[node];
int mid = (lo + hi) / 2;
int res = INT_MAX;
if (l <= mid) res = min(res, query(l, r, 2*node, lo, mid));
if (r > mid) res = min(res, query(l, r, 2*node+1, mid+1, hi));
return res;
}
int query(int l, int r) {
if (l > r) return INT_MAX;
return query(l, r, 1, 1, n);
}
};
int main() {
int T;
scanf("%d", &T);
while (T--) {
int n, q;
scanf("%d%d", &n, &q);
vector<int> a(n + 1);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
vector<int> prev_ge(n + 1, 0);
{
stack<int> stk;
for (int j = 1; j <= n; j++) {
while (!stk.empty() && a[stk.top()] < a[j]) stk.pop();
if (!stk.empty()) prev_ge[j] = stk.top();
stk.push(j);
}
}
vector<int> next_le(n + 1, n + 1);
{
stack<int> stk;
for (int j = n; j >= 1; j--) {
while (!stk.empty() && a[stk.top()] > a[j]) stk.pop();
if (!stk.empty()) next_le[j] = stk.top();
stk.push(j);
}
}
vector<vector<int>> by_prev(n + 1);
for (int j = 1; j <= n; j++) {
if (prev_ge[j] > 0) by_prev[prev_ge[j]].push_back(j);
}
struct Query { int l, r, idx; };
vector<Query> queries(q);
for (int i = 0; i < q; i++) {
scanf("%d%d", &queries[i].l, &queries[i].r);
queries[i].idx = i;
}
sort(queries.begin(), queries.end(), [](const Query& a, const Query& b) {
return a.l > b.l;
});
SegTree seg;
seg.init(n);
vector<bool> ans(q);
int qi = 0;
for (int l = n; l >= 1; l--) {
for (int j : by_prev[l]) seg.update(j, next_le[j]);
while (qi < q && queries[qi].l == l) {
int r = queries[qi].r;
int idx = queries[qi].idx;
if (r - l + 1 < 2) {
ans[idx] = false;
} else {
int mn = seg.query(l + 1, r - 1);
ans[idx] = (mn > r);
}
qi++;
}
}
for (int i = 0; i < q; i++) puts(ans[i] ? "YES" : "NO");
}
return 0;
}
import java.util.*;
import java.io.*;
public class Main {
static int[] tree;
static int N;
static void init(int n) {
N = n;
tree = new int[4 * n + 4];
Arrays.fill(tree, Integer.MAX_VALUE);
}
static void update(int pos, int val, int node, int lo, int hi) {
if (lo == hi) { tree[node] = Math.min(tree[node], val); return; }
int mid = (lo + hi) / 2;
if (pos <= mid) update(pos, val, 2 * node, lo, mid);
else update(pos, val, 2 * node + 1, mid + 1, hi);
tree[node] = Math.min(tree[2 * node], tree[2 * node + 1]);
}
static void update(int pos, int val) { update(pos, val, 1, 1, N); }
static int query(int l, int r, int node, int lo, int hi) {
if (l > r) return Integer.MAX_VALUE;
if (l <= lo && hi <= r) return tree[node];
int mid = (lo + hi) / 2;
int res = Integer.MAX_VALUE;
if (l <= mid) res = Math.min(res, query(l, r, 2 * node, lo, mid));
if (r > mid) res = Math.min(res, query(l, r, 2 * node + 1, mid + 1, hi));
return res;
}
static int query(int l, int r) {
if (l > r) return Integer.MAX_VALUE;
return query(l, r, 1, 1, N);
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int T = Integer.parseInt(br.readLine().trim());
while (T-- > 0) {
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int q = Integer.parseInt(st.nextToken());
int[] a = new int[n + 1];
st = new StringTokenizer(br.readLine());
for (int i = 1; i <= n; i++) a[i] = Integer.parseInt(st.nextToken());
int[] prevGe = new int[n + 1];
Deque<Integer> stk = new ArrayDeque<>();
for (int j = 1; j <= n; j++) {
while (!stk.isEmpty() && a[stk.peek()] < a[j]) stk.pop();
if (!stk.isEmpty()) prevGe[j] = stk.peek();
stk.push(j);
}
int[] nextLe = new int[n + 1];
Arrays.fill(nextLe, n + 1);
stk.clear();
for (int j = n; j >= 1; j--) {
while (!stk.isEmpty() && a[stk.peek()] > a[j]) stk.pop();
if (!stk.isEmpty()) nextLe[j] = stk.peek();
stk.push(j);
}
@SuppressWarnings("unchecked")
List<Integer>[] byPrev = new ArrayList[n + 1];
for (int i = 0; i <= n; i++) byPrev[i] = new ArrayList<>();
for (int j = 1; j <= n; j++) {
if (prevGe[j] > 0) byPrev[prevGe[j]].add(j);
}
int[][] queries = new int[q][3];
for (int i = 0; i < q; i++) {
st = new StringTokenizer(br.readLine());
queries[i][0] = Integer.parseInt(st.nextToken());
queries[i][1] = Integer.parseInt(st.nextToken());
queries[i][2] = i;
}
Arrays.sort(queries, (x, y) -> y[0] - x[0]);
init(n);
boolean[] ans = new boolean[q];
int qi = 0;
for (int l = n; l >= 1; l--) {
for (int j : byPrev[l]) update(j, nextLe[j]);
while (qi < q && queries[qi][0] == l) {
int r = queries[qi][1];
int idx = queries[qi][2];
if (r - l + 1 < 2) {
ans[idx] = false;
} else {
int mn = query(l + 1, r - 1);
ans[idx] = (mn > r);
}
qi++;
}
}
for (int i = 0; i < q; i++) sb.append(ans[i] ? "YES" : "NO").append('\n');
}
System.out.print(sb);
}
}
复杂度分析
- 时间复杂度：
。单调栈预处理
，线段树每个位置至多更新一次
，每次查询
。
- 空间复杂度：
。存储数组、单调栈预处理结果、线段树和查询。
京公网安备 11010502036488号