A1817 [GESP-8.24.03.T2] 接竹竿

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

using ll = long long;

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

// [GESP-8.24.03.T2] 接竹竿
//
// 队列里始终不会有两张点数相同的牌（新牌放进来时，相同点数的旧牌以及它上面的牌
// 都会被收走）。于是「某个点数还在队列里吗」可以用一个数组 O(1) 回答。
//
// 直接对每个询问模拟是 O(nq)，太慢。这里用一个「跳跃链」把它压到 O((n+q) log n)。
//
// 记 f(l) = 把 l..r 的牌按顺序放完后队列里剩下的牌数（队列一开始是空的）。
// 设 nxt[i] = i 之后第一张与 a[i] 点数相同的牌的位置（没有则记 n+1），则
//
//   * 若 nxt[l] > r：l 号牌之后没有同点数的牌，它会一直留在队列里；
//     它上面的那些牌相当于「从 l+1 开始单独玩」的结果，所以 f(l) = 1 + f(l+1)。
//   * 若 nxt[l] <= r：nxt[l] 这张牌放进来时，l 号牌以及它上面的牌都被收走，
//     队列被清空，之后相当于从 nxt[l]+1 重新开始，所以 f(l) = f(nxt[l]+1)。
//
// 两种情况都把 l 换成一个更大的位置。于是顺着这条链走一遍就能算出 f(l)：
// 链上每遇到「nxt[p] <= r」就说明队列被清空、跳到 nxt[p]+1；
// 每遇到「nxt[p] > r」就说明 p 号牌会留在队列里，答案 +1，然后走到 p+1。
//
// 为了不一步一步地跳，定义 F[i] = nxt[i] + 1（队列被清空后重新开始的位置）。
// F 链是单调递增的，并且「i 是重置点（nxt[i] <= r）」等价于「F[i] <= r+1」，
// 所以沿 F 链的「重置点」是连着的一段，可以用倍增整段跳过。
// 而两个重置点之间那一段「+1 步」（这些牌会留在队列里）的终点，
// 就是不小于起点的第一个重置点，用并查集（按 r 从大到小删点）O(alpha) 求出。
//
// 跳过的段数 = 答案 <= 队列里不同点数的个数 <= 13，所以每个询问只要 O(13 log n)。

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        vector<int> a(n + 1);
        int maxA = 0;
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
            maxA = max(maxA, a[i]);
        }

        // nxt[i]：i 之后第一张与 a[i] 点数相同的牌；没有则 n+1
        vector<int> last(maxA + 1, n + 1);
        vector<int> nxt(n + 3, n + 1);
        for (int i = n; i >= 1; i--) {
            nxt[i] = last[a[i]];
            last[a[i]] = i;
        }

        // F[i] = nxt[i] + 1：i 号牌被收走后，队列从 F[i] 重新开始
        vector<int> F(n + 3);
        for (int i = 1; i <= n; i++) F[i] = nxt[i] + 1;
        F[n + 1] = n + 1;
        F[n + 2] = n + 2;

        // 倍增：up[j][i] = 沿 F 链走 2^j 步到达的位置
        int LOG = 1;
        while ((1 << LOG) <= n + 2) LOG++;
        vector<vector<int>> up(LOG, vector<int>(n + 3));
        for (int i = 1; i <= n + 2; i++) up[0][i] = F[i];
        for (int j = 1; j < LOG; j++) {
            for (int i = 1; i <= n + 2; i++) up[j][i] = up[j - 1][up[j - 1][i]];
        }

        int q;
        cin >> q;
        vector<Query> qs(q);
        for (int i = 0; i < q; i++) {
            cin >> qs[i].l >> qs[i].r;
            qs[i].id = i;
        }
        sort(qs.begin(), qs.end(), [](const Query& x, const Query& y) { return x.r > y.r; });

        // 并查集：find(x) = 不小于 x 的第一个重置点（nxt[p] <= r）；没有则 n+1
        vector<int> par(n + 3);
        iota(par.begin(), par.end(), 0);
        auto find = [&](int x) {
            while (par[x] != x) {
                par[x] = par[par[x]];
                x = par[x];
            }
            return x;
        };
        // bucket[v]：所有 nxt[p] == v 的位置（r 变小时它们依次变成非重置点）
        vector<vector<int>> bucket(n + 3);
        for (int i = 1; i <= n; i++) bucket[nxt[i]].push_back(i);

        vector<ll> ans(q, 0);
        int curR = n + 1;
        for (const Query& qu : qs) {
            // 把 nxt[p] > qu.r 的位置删掉，剩下的就是重置点
            while (curR > qu.r) {
                for (int p : bucket[curR]) par[p] = find(p + 1);
                curR--;
            }

            ll res = 0;
            int p = qu.l;
            while (p <= qu.r) {
                // 沿 F 链跳过连着的一段重置点，cur 是第一个「不是重置点」的位置
                int cur = p;
                for (int j = LOG - 1; j >= 0; j--) {
                    if (up[j][cur] <= qu.r + 1) cur = up[j][cur];
                }
                if (cur > qu.r) break;
                // cur 到下一个重置点之间的牌都会留在队列里
                int stop = find(cur);
                res += min(stop, qu.r + 1) - cur;
                p = (stop <= qu.r) ? F[stop] : qu.r + 1;
            }
            ans[qu.id] = res;
        }

        for (ll v : ans) cout << v << "\n";
    }
    return 0;
}