我们惺惺相惜

[编程题]我们惺惺相惜

热度指数：697 时间限制：C/C++ 5秒，其他语言10秒空间限制：C/C++ 1024M，其他语言2048M
算法知识视频讲解

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

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

输入描述:

第一行一个整数 ，表示有  次询问。

对于每次询问，第一行两个整数 ，第二行  个整数 ，表示数组 。

接下来  行，每行两个整数 ，表示询问的区间。

单个测试文件保证  和  的和均不超过 。

输出描述:

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

示例1

输入

输出

YES
YES
YES
NO
YES

算法知识视频讲解

Silencer76

发表于 2025-09-09 01:27:11

题目链接我们惺惺相惜题目描述给定一个长度为的数组，我们定义一个区间是“好的”，当且仅当这个区间可以被分成两个非空的、元素相对顺序不变的严格单调递增子序列。对于给出的多次询问，你需要回答指定区间是不是“好的”。输入: 第一行一个整数，表示有次询问。对于每次询问，第一行两个整数展开全文

丨阿伟丨

发表于 2025-09-12 17:08:25

题目链接我们惺惺相惜思路分析 1. 问题转换首先，我们需要理解“好区间”的定义：一个区间可以被划分成两个非空的严格单调递增子序列。这是一个与 Dilworth 定理相关的问题。Dilworth 定理的一个推论是：将一个序列划分为严格单调递增子序列所需的最少数量，等于该序列中最长非递增子序列的展开全文