问题理解

我们有 n 个嫌疑人，每个嫌疑人的身高是一个区间 [l_i, r_i] 内的实数。
最多一个嫌疑人是罪犯，也可能都不是。

一次“排队”就是选择一个连续区间 [a, b] 的嫌疑人，让目击者看。
条件：必须保证这些人的身高可以安排成互不相同（即区间不重叠时可行）。
效果：如果罪犯在这些人中，目击者能认出；如果不在，也能判断出不在。

我们要回答 q 个问题：
对于 [p, q] 这个嫌疑人范围，在最坏情况下最少需要多少次排队才能确定罪犯（或确定不在这些人中）。

关键观察

1. 身高区间不重叠才能排队
   如果两个嫌疑人的身高区间有重叠，那么可能他们身高相等，目击者无法区分，所以不能放在同一次排队中。
   因此一次排队选择的嫌疑人，他们的身高区间必须两两不重叠。

2. 问题转化
   我们要在 [p, q] 这个区间内，用最少的“不重叠区间组”覆盖所有嫌疑人，并且这些组可以同时被目击者看（即组内不重叠）。
   但注意：排队是依次进行的，不是同时。所以我们要找的是：
   用最少的不重叠区间组覆盖 [p, q] 中的所有人，使得组内区间不重叠。
   这其实等价于：将 [p, q] 划分成若干段，每段内所有嫌疑人的身高区间两两不重叠。

3. 最少排队次数
   如果 [p, q] 内所有区间两两不重叠，那么一次排队就够了。
   否则，我们需要多次排队，每次选一个不重叠的子集。

4. 贪心策略
   从左到右扫描，每次尽可能取多的不重叠区间，直到不能取为止，然后另开一次排队。
   这其实等价于：最少排队次数 = 区间图中该段的最大团的大小。
   在区间图中，两个区间重叠则连边，最大团大小就是最多两两重叠的区间数，也就是最少需要的颜色数（即排队次数）。

   但是，对于连续区间 [p, q]，最大团大小 = 该段内某个点被多少个区间覆盖的最大值（区间图的性质）。
   所以问题变成：
   对于 [p, q]，求 max_{x} (count of i in [p,q] s.t. l_i <= x <= r_i)。

5. 简化
   我们只需要计算 [p, q] 内区间重叠的最大深度。
   因为如果某个实数 x 被 k 个区间覆盖，那么这 k 个区间两两重叠（都有 x 这个公共点），它们不能在同一个排队中，所以至少需要 k 次排队。

   所以：
   答案 = max over x of (覆盖 x 的区间个数)，其中区间限制在 [p, q]。

数据结构问题

我们需要快速回答多个查询 [p, q]：
求区间内所有 [l_i, r_i] 在某个点上的最大重叠数。

这是一个经典问题：

• 对每个查询 [p, q]，考虑所有下标在 [p, q] 的区间，求最大重叠数。
• 等价于：对每个 x，计算 [p, q] 中有多少个区间满足 l_i <= x <= r_i，取最大值。

高效算法

我们可以用离线扫描 + 线段树/ Fenwick 树：

1. 将每个区间 [l_i, r_i] 看作事件：
   • 在 l_i 处 +1
   • 在 r_i + 1 处 -1
2. 对 x 坐标离散化（所有 l_i, r_i+1）。
3. 对查询按右端点排序（Mo's algorithm 也可，但 n,q 大时可能用分块或线段树）。
4. 但我们这里需要的是区间 [p, q] 内的区间，不是全局的。

更直接的方法：
用持久化线段树，对每个右端点 r 建立版本，存储左端点对应的区间覆盖数。
然后查询 [p, q] 时，在版本 q 中查询区间 [p, q] 的最大值。

实现方案

我们这样设计：

• 对每个位置 i（右端点），记录所有左端点 <= i 的区间。
• 用扫描线：从 1 到 n，维护当前右端点时，每个左端点的区间覆盖数。
• 用线段树维护这个覆盖数，并支持区间最大值查询。
• 对查询 (p, q)，在右端点 q 的线段树上查询 [p, q] 的最大值。

但这里“覆盖数”是指：对于左端点 L，右端点 R 在扫描过程中，我们只考虑区间 [L, R] 内的区间对覆盖的贡献。
其实更简单：
我们固定右端点 q，看左端点 p 到 q 的区间，它们对某个 x 的覆盖数最大值。

实际上，有一个已知结论：
对于区间集合 S，最大重叠数 = 按左端点排序后，扫描时遇到左端点 +1，遇到右端点 -1，过程中的最大值。

所以对查询 [p, q]：

• 只考虑下标在 [p, q] 的区间
• 对这些区间做扫描线，求最大重叠数。

我们可以用莫队算法来做，因为 n, q 很大，但莫队 O(n√q) 可能勉强过（n,q=2e5 时 ≈ 9e8 操作，可能卡常）。

最终简化

其实这个问题就是：
给定 n 个区间 [l_i, r_i]，q 个查询 [p, q]，求子集 {p, p+1, ..., q} 这些区间在某个点上的最大重叠数。

这是一个经典问题，可以用离线 + 扫描右端点 + 线段树区间加区间最大值解决：

1. 将查询按右端点排序。
2. 从左到右扫描右端点 R，维护线段树，位置 L 的值表示区间 [L, R] 的最大重叠数。
3. 当加入区间 [l_i, r_i] 时，在线段树上区间 [1, i] 中所有左端点 <= i 的区间覆盖数 +1（不对，要仔细考虑）。

其实更简单：
我们维护一个数组 cnt[x] 表示当前扫描线位置下，覆盖点 x 的区间个数。
加入区间 [l_i, r_i] 时，在树状数组上区间 [l_i, r_i] +1，删除时 -1。
用线段树维护 cnt 数组的最大值。

但我们只关心 [p, q] 内的区间，所以用离线莫队：

• 对查询排序，用两个指针 L, R 表示当前处理的区间下标范围。
• 用线段树维护当前区间集合的覆盖数最大值。
• 移动指针时更新区间覆盖。

代码实现（莫队 + 线段树）

由于 n, q 最大 2e5，O(n√q log n) 可能有点大，但我们可以尝试优化。

这里给出一个可行的实现框架：

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

const int MAXN = 200005;

int n, q;
int l[MAXN], r[MAXN];
int ans[MAXN];

// 莫队相关
int block_size;
struct Query {
    int l, r, idx;
    bool operator<(const Query& other) const {
        if (l / block_size != other.l / block_size)
            return l / block_size < other.l / block_size;
        return r < other.r;
    }
} queries[MAXN];

// 线段树维护区间最大值
int tree[4 * MAXN], lazy[4 * MAXN];

void push_down(int idx) {
    if (lazy[idx]) {
        tree[idx*2] += lazy[idx];
        tree[idx*2+1] += lazy[idx];
        lazy[idx*2] += lazy[idx];
        lazy[idx*2+1] += lazy[idx];
        lazy[idx] = 0;
    }
}

void update(int idx, int l, int r, int ql, int qr, int val) {
    if (ql <= l && r <= qr) {
        tree[idx] += val;
        lazy[idx] += val;
        return;
    }
    push_down(idx);
    int mid = (l + r) / 2;
    if (ql <= mid) update(idx*2, l, mid, ql, qr, val);
    if (qr > mid) update(idx*2+1, mid+1, r, ql, qr, val);
    tree[idx] = max(tree[idx*2], tree[idx*2+1]);
}

// 离散化
vector<int> vals;
int compress(int x) {
    return lower_bound(vals.begin(), vals.end(), x) - vals.begin();
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> l[i] >> r[i];
        vals.push_back(l[i]);
        vals.push_back(r[i]);
    }
    // 离散化
    sort(vals.begin(), vals.end());
    vals.erase(unique(vals.begin(), vals.end()), vals.end());
    int m = vals.size();

    for (int i = 1; i <= n; i++) {
        l[i] = compress(l[i]);
        r[i] = compress(r[i]);
    }

    cin >> q;
    for (int i = 0; i < q; i++) {
        cin >> queries[i].l >> queries[i].r;
        queries[i].idx = i;
    }

    // 莫队分块
    block_size = sqrt(n);
    sort(queries, queries + q);

    int curL = 1, curR = 0;
    for (int i = 0; i < q; i++) {
        int L = queries[i].l, R = queries[i].r;
        while (curR < R) {
            curR++;
            update(1, 0, m-1, l[curR], r[curR], 1);
        }
        while (curR > R) {
            update(1, 0, m-1, l[curR], r[curR], -1);
            curR--;
        }
        while (curL < L) {
            update(1, 0, m-1, l[curL], r[curL], -1);
            curL++;
        }
        while (curL > L) {
            curL--;
            update(1, 0, m-1, l[curL], r[curL], 1);
        }
        ans[queries[i].idx] = tree[1];
    }

    for (int i = 0; i < q; i++) {
        cout << ans[i] << "\n";
    }

    return 0;
}

总结

这道题的核心是将“最少排队次数”转化为“区间集合在某个点上的最大重叠数”，然后用数据结构快速回答多个查询。
上面的代码使用了莫队算法 + 线段树区间加/区间最大值来求解，时间复杂度 O((n+q)√n log n)，在 n,q ≤ 2e5 时可能稍慢，但可以通过优化常数或使用更高效的数据结构（如分块）来提升性能。