纵星辰陨落，你仍将歌唱。

· · 题解

宝宝题。

有结论：一个序列是合法的当且仅当不存在形如 a,b,a,b 的子序列。此时你删除中间的 a 或者 b 都会导致两侧的 a 或者 b 删不掉，而不存在这种子序列说明至多存在子序列 a,b,a，此时删除中间的 b 之后可以拼合两边的 a 一起删除。

考虑上述子序列，一个四元组 (i,j,k,l) 满足 i<j<k<l 且 p=a_i=a_k，q=a_j=a_l，p\ne q，他是一个上述的非法子序列，此时所有包含 [i,l] 的区间都非法。这个东西有支配对，首先可以只保留 j,l 是 q 相邻两次出现位置的四元组，贡献不劣，原因是如果 j,l 不是相邻的两次出现，那么 j 可以往右移或者 l 可以往左移，区间 [i,l] 的变化不劣。所以枚举 j，此时 l 已经确定，i 取最大的满足在 (j,l) 中存在一个 a_j=a_i 的位置即可。因此，对于一个 j 只有一个四元组是有贡献的，四元组总数 O(n)。用线段树求四元组，扫描 j 的同时求出每个位置 x 上一次在 j 之前出现的位置，单点修改查询区间最大值。把得到的区间信息挂在 l 上，得到 p_k 表示当四元组的 l=k 时，左端点 i 最大是多少。

于是可以简单判断区间合法性。我们记 f_r 表示以 r 结尾的合法区间的左端点最小是多少，查询等于判断 f_r\le l。f 是好求的，等于 p 的前缀 \max 加一。

时间复杂度 1log。

#include <bits/stdc++.h>
#define LL long long
#define ull unsigned long long
#define uint unsigned int
using namespace std;
const int N = 2e5 + 10;
int n, Q, A[N], pos[N], nxt[N], res[N];

namespace Sgt {

#define ls(x) (x << 1)
#define rs(x) (x << 1 | 1)
int tr[N << 2];
void build() { for (int i = 1; i <= n * 4; i ++) tr[i] = 0; }
void update(int p, int l, int r, int x, int k) {
    if (x > r || x < l) return ;
    if (l == r) { tr[p] = k; return ; }
    int mid = (l + r) >> 1;
    update(ls(p), l, mid, x, k), update(rs(p), mid + 1, r, x, k);
    tr[p] = max(tr[ls(p)], tr[rs(p)]); return ;
}
int query(int p, int l, int r, int x, int y) {
    if (x > r || y < l) return 0;
    if (x <= l && y >= r) return tr[p];
    int mid = (l + r) >> 1;
    return max(query(ls(p), l, mid, x, y), query(rs(p), mid + 1, r, x, y));
}

}

int main() {
    freopen(".in", "r", stdin); freopen(".out", "w", stdout);
    ios::sync_with_stdio(false); cin.tie(0), cout.tie(0);
    int _; cin >> _;
    while (_ --) {
        cin >> n >> Q; Sgt::build();
        for (int i = 1; i <= n; i ++) pos[i] = nxt[i] = res[i] = 0;
        for (int i = 1; i <= n; i ++) {
            cin >> A[i];
            if (pos[A[i]]) nxt[pos[A[i]]] = i;
            pos[A[i]] = i;
        }
        for (int i = 1; i <= n; i ++) {
            if (nxt[i]) res[nxt[i]] = Sgt::query(1, 1, n, i + 1, nxt[i] - 1);
            Sgt::update(1, 1, n, nxt[i], i);
        }
        for (int i = 1; i <= n; i ++) res[i] = max(res[i], res[i - 1]);
        int x, y;
        while (Q --) {
            cin >> x >> y; cout << (res[y] < x ? "YES\n" : "NO\n");
        }
    }
    return 0;
}