首页 > 试题广场 >

我们惺惺相惜

[编程题]我们惺惺相惜
  • 热度指数：697 时间限制：C/C++ 5秒，其他语言10秒 空间限制：C/C++ 1024M，其他语言2048M
  • 算法知识视频讲解
给定一个长度为 n 的数组 a，我们定义一个区间 [l,r]是好的，当且仅当这个区间可以分成两个非空的子序列，元素之间相对顺序不变，使得这两个子序列都是严格单调递增子序列。

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

输入描述:
第一行一个整数 T(1\leq T\leq 20000)，表示有 T 次询问。

对于每次询问，第一行两个整数 n,q(2\leq n,q\leq 2\times 10^5)，第二行 n 个整数 a_i(1\leq a_i\leq 10^9)，表示数组 a。

接下来 q 行，每行两个整数 l,r(1\leq l< r\leq n)，表示询问的区间。

单个测试文件保证 n 和 q 的和均不超过 2\times 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
算法知识视频讲解
添加回答
Java
pe1shen9头像 pe1shen9
要使一个区间 [l,r] 可以分成两个严格递增的子序列，这意味着原区间中的元素不能有“三个递减”的点。换句话说，如果存在三个索引 i,j,k（l≤i<j<k≤r）满足 ai≥aj≥ak，那么无论如何分割，这三个元素中至少有两个会在同一个子序列中，导致该子序列不是严格递增的。因此，这样的区间不可能是“好的”。

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int t = in.nextInt();
        for (int i = 0; i < t; i++) {
            int n = in.nextInt();
            int q = in.nextInt();
            int[] arr = new int[n];
            for (int j = 0; j < n; j++) {
                arr[j] = in.nextInt();
            }

            //left[j] 表示 j 左边第一个 ≥ a[j] 的元素的索引
            int[] left = new int[n];
            Arrays.fill(left, -1);
            Deque<Integer> stack = new ArrayDeque<>();
            for (int j = 0; j < n; j++) {
                while (!stack.isEmpty() && arr[stack.peek()] < arr[j]) {
                    stack.pop();
                }
                if (!stack.isEmpty()) {
                    left[j] = stack.peek();
                }
                stack.push(j);
            }
            stack.clear();

            //right[j] 表示 j 右边第一个 ≤ a[j] 的元素的索引
            int[] right = new int[n];
            Arrays.fill(right, -1);
            for (int j = n - 1; j >= 0; j--) {
                while (!stack.isEmpty() && arr[stack.peek()] > arr[j]) {
                    stack.pop();
                }
                if (!stack.isEmpty()) {
                    right[j] = stack.peek();
                }
                stack.push(j);
            }
            //如果 left[j] 和 right[j] 都存在，则记录 (left[j], right[j])
            List<int[]> list = new ArrayList<>();
            for (int j = 0; j < n; j++) {
                if (left[j] != -1 && right[j] != -1) {
                    list.add(new int[] {left[j], right[j]});
                }
            }
            //按照left[j]的大小进行排序
            //由于题目最大时间为4MS，直接遍历是否符合好区间即可
            //如果时间复杂度要求更高，可以用二分优化
            list.sort((o1, o2) -> o1[0] - o2[0]);
            for (int j = 0; j < q; j++) {
                int l = in.nextInt() - 1;
                int r = in.nextInt() - 1;
                boolean falg = true;
                for (int k = 0; k < list.size(); k++) {
                    if (list.get(k)[0] >= l && list.get(k)[1] <= r) {
                        falg = false;
                        break;
                    }
                }
                System.out.println(falg ? "YES" : "NO");
            }
        }
    }
}
发表于 2025-06-09 20:20:12 回复(1)
C++
牛客446325680号头像 牛客446325680号
#include <iostream>
#include <vector>
#include <deque>
using namespace std;

int main() {
    int T;
    cin >> T;
    for (int i = 0; i < T; ++i) {
        int n, q;
        cin >> n >> q;
        vector<int> a(n, 0);
        for (int i = 0; i < n; ++i) {
            cin >> a[i];
        }
        vector<vector<int>> query(q, vector<int>(2, 0));
        for (int i = 0; i < q; ++i) {
            cin >> query[i][0] >> query[i][1];
        }
        vector<int> width(n, 0);
        int r = 0;
        int mi = 0, mx = a[0];
        for (int i = 0; i < n; ++i) {
            if (r >= n) {
                width[i] = n;
                continue;
            }
            int ni = r - 1;
            while (++r < n) {
                if (a[r] > mx) {
                    mx = a[r];
                } else if (a[r] > mi) {
                    mi = a[r];
                } else {
                    mi = a[r];
                    mx = a[r - 1];
                    break;
                }
                if (a[r] <= a[r - 1])
                    ni = r - 1;
            }
            width[i] = r;
            while (i < ni) {
                width[++i] = r;
            }

        }
        for (auto& qu : query) {
            if (qu[1] - qu[0] > 0 && width[qu[0] - 1]  > qu[1] - 1) {
                cout << "YES" << endl;
            } else {
                cout << "NO" << endl;
            }
        }
    }
}
可以使用双指针的解法
发表于 2025-07-19 02:58:56 回复(0)
提交观点

问题信息

数组 美团 单调栈
难度：
2条回答 525浏览

热门推荐

相关试题

我们惺惺相惜

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号