题解

题面描述

给定一个长度为 $n$ 的数组 $a$，定义区间 $[l, r]$ 是好区间当且仅当该区间内的元素能被划分为两个非空子序列（保持原相对顺序），使得这两条子序列都是严格单调递增的。现有 $q$ 次询问，每次给出一对 $(l, r)$，判断 $[l, r]$ 是否为好区间。

思路

• Dilworth 定理（在一维序列上的特殊情形）告诉我们：
  把一个序列划分为不交的严格递增子序列的最小条数，正好等于该序列的最长严格递减子序列的长度。

• 因此，一个区间$[l,r]$能否被拆成两个非空的严格递增子序列，当且仅当这段子数组里的最长严格递减子序列长度 $<=2$。
  换言之，若存在三元递减 (i<j<k) 且 (a_i>a_j>a_k)，就不能拆成两条增序，否则一定可以。

• 预处理两个数组：

  • 前驱数组 $p[i]$：在 $i$ 左侧最近的下标，使得 $a[p[i]] \ge a[i]$，若不存在则为 $0$。
  • 后继数组 $nx[i]$：在 $i$ 右侧最近的下标，使得 $a[nx[i]] \le a[i]$，若不存在则为 $n+1$。

• 若对于某个 $j$，$p[j]>0$ 且 $nx[j]\le n$，则任意覆盖区间 $[l,r]$ 包含该 $j$ 时，且 $l\le p[j]<j<nx[j]\le r$，则该区间一定包含不可拆分的三元组。

• 构造辅助数组：

  • 初始化一个大数组 $b$，长度为 $n+2$，值全为 $n+1$。
  • 对每个 $j$ 若 $p[j]>0$ 且 $nx[j]\le n$，则更新$$b[p[j]] = \min\bigl(b[p[j]],\ nx[j]\bigr).$$
  • 定义数组 $m$，从右到左维护最小值：$$m[i] = \min\bigl(b[i],\, m[i+1]\bigr).$$
  • 则对于任意查询 $[l,r]$，如果 $m[l] > r$ 则无任何冲突三元组，区间为好区间，否则不是。

C++

#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int T;
    cin >> T;
    while(T--){
        int n, q;
        cin >> n >> q;
        vi a(n+2);
        for(int i = 1; i <= n; i++) cin >> a[i];

        vi p(n+2), nx(n+2);
        stack<int> st;

        // 构造前驱 p[i]
        for(int i = 1; i <= n; i++){
            while(!st.empty() && a[st.top()] < a[i]) st.pop();
            p[i] = st.empty() ? 0 : st.top();
            st.push(i);
        }
        while(!st.empty()) st.pop();

        // 构造后继 nx[i]
        for(int i = n; i >= 1; i--){
            while(!st.empty() && a[st.top()] > a[i]) st.pop();
            nx[i] = st.empty() ? n+1 : st.top();
            st.push(i);
        }

        const int INF = n + 1;
        vi b(n+2, INF), m(n+3, INF);

        // 更新 b
        for(int j = 1; j <= n; j++){
            if(p[j] > 0 && nx[j] <= n){
                b[p[j]] = min(b[p[j]], nx[j]);
            }
        }
        // 从右向左维护最小
        for(int i = n; i >= 1; i--){
            m[i] = min(b[i], m[i+1]);
        }

        // 查询回答
        while(q--){
            int l, r;
            cin >> l >> r;
            if(m[l] > r) cout << "YES\n";
            else cout << "NO\n";
        }
    }
    return 0;
}

Python

import sys
input = sys.stdin.readline

def solve():
    T = int(input())
    for _ in range(T):
        n, q = map(int, input().split())
        a = [0] + list(map(int, input().split()))

        p = [0] * (n+2)
        nx = [n+1] * (n+2)
        st = []

        # 构造前驱 p[i]
        for i in range(1, n+1):
            while st and a[st[-1]] < a[i]:
                st.pop()
            p[i] = st[-1] if st else 0
            st.append(i)
        st.clear()

        # 构造后继 nx[i]
        for i in range(n, 0, -1):
            while st and a[st[-1]] > a[i]:
                st.pop()
            nx[i] = st[-1] if st else n+1
            st.append(i)

        INF = n + 1
        b = [INF] * (n+2)
        m = [INF] * (n+3)

        # 更新 b
        for j in range(1, n+1):
            if p[j] > 0 and nx[j] <= n:
                b[p[j]] = min(b[p[j]], nx[j])

        # 从右向左维护最小
        for i in range(n, 0, -1):
            m[i] = min(b[i], m[i+1])

        # 查询回答
        for _ in range(q):
            l, r = map(int, input().split())
            print("YES" if m[l] > r else "NO")

if __name__ == '__main__':
    solve()

Java

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int T = Integer.parseInt(br.readLine());
        while(T-- > 0) {
            st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            int q = Integer.parseInt(st.nextToken());
            int[] a = new int[n+2];
            st = new StringTokenizer(br.readLine());
            for(int i = 1; i <= n; i++) a[i] = Integer.parseInt(st.nextToken());

            int[] p = new int[n+2], nx = new int[n+2];
            Arrays.fill(nx, n+1);
            Deque<Integer> stck = new ArrayDeque<>();

            // 构造前驱 p[i]
            for(int i = 1; i <= n; i++){
                while(!stck.isEmpty() && a[stck.peek()] < a[i]) stck.pop();
                p[i] = stck.isEmpty()?0:stck.peek();
                stck.push(i);
            }
            stck.clear();

            // 构造后继 nx[i]
            for(int i = n; i >= 1; i--){
                while(!stck.isEmpty() && a[stck.peek()] > a[i]) stck.pop();
                nx[i] = stck.isEmpty()?n+1:stck.peek();
                stck.push(i);
            }

            int INF = n + 1;
            int[] b = new int[n+2], mArr = new int[n+3];
            Arrays.fill(b, INF);
            Arrays.fill(mArr, INF);

            // 更新 b
            for(int j = 1; j <= n; j++){
                if(p[j] > 0 && nx[j] <= n) {
                    b[p[j]] = Math.min(b[p[j]], nx[j]);
                }
            }
            // 从右向左维护最小
            for(int i = n; i >= 1; i--) {
                mArr[i] = Math.min(b[i], mArr[i+1]);
            }

            // 查询回答
            StringBuilder sb = new StringBuilder();
            while(q-- > 0) {
                st = new StringTokenizer(br.readLine());
                int l = Integer.parseInt(st.nextToken());
                int r = Integer.parseInt(st.nextToken());
                sb.append(mArr[l] > r? "YES\n": "NO\n");
            }
            System.out.print(sb);
        }
    }
}

题目内容

给定一个长度为$n$的数组$a$，我们定义一个区间$[l,r]$是好的,当且仅当这个区间可以分成两个非空的子序列，元素之间相对顺序不变，使得这两个子序列都是严格单调递增子序列。

对于给出多次询问，你需要问答区间是不是好区间。

输入描述

第一行一个整数$T(1≤T≤20000)$，表示有$T$次时。

对于每次询问，第一行两个整数$n,q(2≤n,q≤2×10^5)$,第二行$n$个整数$a_i(1≤a_i≤10^9)$，表示数组a。 接下来$q$行，每行两个整数$1,r(1≤l<r≤n)$，表示询问的区间。

单个测试文件保证$n$和$q$的和均不超过$2×10^5$

输出描述

对于每次询问，输出一行，如果区间是好区间，输出$YES$，否则输出$NO$。

样例1

输入

2
4 2
1 2 3 3
1 3
1 2
5 3
4 5 4 5 3
1 4 
1 5
2 4

输出

YES
YES
YES
NO
YES