• 更快的询问排序方法
• 时间复杂度：$O(n\sqrt{n})$
• 期望得分：100 分

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int l, r, id;    
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    
    int n, m;
    cin >> n >> m;
    
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    
    vector<Node> q(m);
    for (int i = 0; i < m; i++) cin >> q[i].l >> q[i].r, q[i].id = i;
    
    int d = sqrt(n);
    sort(q.begin(), q.end(), [&](const Node& x, const Node& y) {
        // 将询问的左端点, 每块长为 d 编号, 编号小的排前面
        if (x.l / d != y.l / d) return x.l / d < y.l / d;
        
        // 右端点 r 奇偶排序优化, 预计快 30%
        // 左端点块号为奇数, 右端点从小到大排序
        if (x.l / d & 1) return x.r < y.r;
        
        // 左端点块号偶奇数, 右端点从大到小排序
        return x.r > y.r;
    });
    
    int tol = 0;                // 不同数个数
    int L = 1, R = 0;           // 当前处理的区间, 初始是空的
    vector<int> cnt(n + 1, 0);  // cnt[i]: i 出现的次数
    vector<bool> ans(m);
    
    for (int i = 0; i < m; i++) {
        int l = q[i].l, r = q[i].r, id = q[i].id;
        
        // 右边界 R 往右扩展
        while (R < r) tol += (++cnt[a[++R]] == 1);
        
        // 左边界 L 往左扩展
        while (L > l) tol += (++cnt[a[--L]] == 1);
        
        // 右边界 R 往左缩小
        while (R > r) tol -= (--cnt[a[R--]] == 0);
        
        // 左边界 L 往右缩小
        while (L < l) tol -= (--cnt[a[L++]] == 0);
        
        // 处理完后记录答案
        ans[id] = (tol == r - l + 1);
    }
    for (int i = 0; i < m; i++) cout << (ans[i] ? "Yes" : "No") << '\n';
    
    return 0;
}

• 尝试先把询问排序
• 把左右端点靠近的询问，安排在一起处理，以此减少左右端点的移动
• 时间复杂度：$O(n\sqrt{n})$
• 期望得分：100分

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int l, r, id;    
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    
    int n, m;
    cin >> n >> m;
    
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    
    vector<Node> q(m);
    for (int i = 0; i < m; i++) cin >> q[i].l >> q[i].r, q[i].id = i;
    
    int d = sqrt(n);
    sort(q.begin(), q.end(), [&](const Node& x, const Node& y) {
        // 将询问的左端点按长度为 d 分组编号, 编号小的排前面
        if (x.l / d != y.l / d) return x.l / d < y.l / d;
        
        // 左端点编号相同的, 右端点从小到大排序
        return x.r < y.r;
    });
    
    int tol = 0;                // 不同数个数
    int L = 1, R = 0;           // 当前处理的区间, 初始是空的
    vector<int> cnt(n + 1, 0);  // cnt[i]: i 出现的次数
    vector<bool> ans(m);
    
    for (int i = 0; i < m; i++) {
        int l = q[i].l, r = q[i].r, id = q[i].id;
        
        // 右边界 R 往右扩展
        while (R < r) tol += (++cnt[a[++R]] == 1);
        
        // 左边界 L 往左扩展
        while (L > l) tol += (++cnt[a[--L]] == 1);
        
        // 右边界 R 往左缩小
        while (R > r) tol -= (--cnt[a[R--]] == 0);
        
        // 左边界 L 往右缩小
        while (L < l) tol -= (--cnt[a[L++]] == 0);
        
        // 处理完后记录答案
        ans[id] = (tol == r - l + 1);
    }
    for (int i = 0; i < m; i++) cout << (ans[i] ? "Yes" : "No") << '\n';

    return 0;
}

• 尝试先把询问排序
  • 按左端点从小到大排序
  • 左端点相同的，按右端点从小到大排序
• 这样的话，对于同一个左端点 $l$，右端点做多只会从 $1$ 移动到 $n$
• 期望得分 60 分

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int l, r, id;    
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    
    int n, m;
    cin >> n >> m;
    
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    
    vector<Node> q(m);
    for (int i = 0; i < m; i++) cin >> q[i].l >> q[i].r, q[i].id = i;
    
    sort(q.begin(), q.end(), [&](const Node& x, const Node& y) {
        
        // 左端点从小到大排序
        return x.l < y.l;
    });
    
    int tol = 0;                // 不同数个数
    int L = 1, R = 0;           // 当前处理的区间, 初始是空的
    vector<int> cnt(n + 1, 0);  // cnt[i]: i 出现的次数
    vector<bool> ans(m);
    
    for (int i = 0; i < m; i++) {
        int l = q[i].l, r = q[i].r, id = q[i].id;
        
        // 右边界 R 往右扩展
        while (R < r) tol += (++cnt[a[++R]] == 1);
        
        // 左边界 L 往左扩展
        while (L > l) tol += (++cnt[a[--L]] == 1);
        
        // 右边界 R 往左缩小
        while (R > r) tol -= (--cnt[a[R--]] == 0);
        
        // 左边界 L 往右缩小
        while (L < l) tol -= (--cnt[a[L++]] == 0);
        
        // 处理完后记录答案
        ans[id] = (tol == r - l + 1);
    }
    for (int i = 0; i < m; i++) cout << (ans[i] ? "Yes" : "No") << '\n';
    
    return 0;
}

• 尝试多个询问复用一个 cnt[] 数组
• 然后不断移动询问左右端点
• 还是 50 分

#include <bits/stdc++.h>
using namespace std;

int main() {	
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    
    int n, m, l, r;
    cin >> n >> m;
    
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    
    int tol = 0;                // 不同数个数
    int L = 1, R = 0;           // 当前处理的区间, 初始是空的
    vector<int> cnt(n + 1, 0);  // cnt[i]: i 出现的次数
    
    while (m--) {
        cin >> l >> r;
        
        // 右边界 R 往右扩展
        while (R < r) tol += (++cnt[a[++R]] == 1);
        
        // 左边界 L 往左扩展
        while (L > l) tol += (++cnt[a[--L]] == 1);
        
        // 右边界 R 往左缩小
        while (R > r) tol -= (--cnt[a[R--]] == 0);
        
        // 左边界 L 往右缩小
        while (L < l) tol -= (--cnt[a[L++]] == 0);

        cout << (tol == r - l + 1 ? "Yes" : "No") << '\n';
    }
    return 0;
}

• 参考 P1638【普及】包含所有数的最短区间 的方法
• 对每个询问，记录：
  • cnt[i]：$i$ 出现的次数
• 时间复杂度：$O(nq)$，会 TLE，期望得分 $50$

#include <bits/stdc++.h>
using namespace std;

int main() {	
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    
    int n, m, l, r;
    cin >> n >> m;
    
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    
    while (m--) {
        cin >> l >> r;
        
        int tol = 0;                // 不同数个数
        vector<int> cnt(n + 1, 0);  // cnt[i]: i 出现的次数
        for (int i = l; i <= r; i++) {
            if (++cnt[a[i]] == 1) tol++;
        }
        cout << (tol == r - l + 1 ? "Yes" : "No") << '\n';
    }
    return 0;
}