洛谷 P1972 [SDOI2009] HH 的项链

// P1972 第 ① 版：**每问一次就数一遍** —— 拿一个「时间戳」数组当去重的桶
//
// ★ 它值多少分，题面自己分好了档：
//     · 「对于 20% 的数据，1 ≤ n, m ≤ 5000」    ⇒ 2.5×10⁷ 次，本机约 0.01 秒 ⇒ ★ 稳拿 20 分；
//     · 「对于 40% 的数据，1 ≤ n, m ≤ 10⁵」     ⇒ 10¹⁰ 次 ⇒ 挂；
//     · 顶格 n = m = 10⁶                        ⇒ 10¹² 次 ⇒ 想都别想。
//
// ★ vis 用「这次询问的编号」当标记，就不用每次 memset 一遍 10⁶ 个格子了
//   （不然光清零就 10¹² 次）—— 这个小技巧本身值 n/(r−l+1) 倍。

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

const int MAXV = 1000006;
int vis[MAXV];

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

    int n;
    if (!(cin >> n)) return 0;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    int m;
    cin >> m;

    string out;
    for (int q = 1; q <= m; q++) {
        int l, r;
        cin >> l >> r;
        int cnt = 0;
        for (int i = l; i <= r; i++)
            if (vis[a[i]] != q) { vis[a[i]] = q; cnt++; }   // ★ 时间戳去重，不用清零
        out += to_string(cnt);
        out += '\n';
    }
    cout << out;
    return 0;
}

// P1972 [SDOI2009] HH 的项链 —— ★ 这一版就能 AC（询问离线 + 树状数组）
//
// ============ ★★★ 关键一步：把「有多少种」改写成「有多少个 1」 ============
//
//   直接问「[l, r] 里有多少种贝壳」没法用前缀和 —— 种类数**不可加**
//   （[1,3] 有 2 种、[4,6] 有 2 种，合起来可能是 2 也可能是 4）。
//
//   ★ 换一个问法：**每种贝壳只让它「最后出现的那个位置」记 1，别的位置记 0**。
//     那么对固定的右端点 r，[l, r] 里的种类数 = 位置 l..r 上这些 1 的**个数** ——
//     因为每种在 [l, r] 里出现的贝壳，恰好有一个「在 [l, r] 内最后出现的位置」。
//   ⇒ 种类数变成了**区间求和**，而区间求和正是树状数组的看家本领。
//
//   ⚠ 但「最后出现的位置」是跟着 r 变的 ⇒ 得让 r 从小到大走一遍。
//   ⇒ **把所有询问按右端点排序，离线回答**：
//       扫到 i 时：如果 a[i] 上次在 pre 出现过，就 add(pre, −1)；再 add(i, +1)；
//       然后回答所有 r = i 的询问：sum(r) − sum(l − 1)。
//
// ============ ⚠ 为什么非离线不可 ============
//   那个 add(pre, −1) 是**不可回退**的：一旦把 pre 位置的 1 抹掉，
//   就再也答不了「右端点小于 i」的询问了（p1972Online.cpp 演示这件事，第 ④ 步）。
//   ⇒ **排序不是为了快，是为了让每个位置只被抹一次、而且抹得不早不晚。**
//
// 复杂度 O((n + m) log n)；每个位置至多被 add 两次 ⇒ 总共 2n 次 add。
//
// ⚠ 读入：题面自己写着「本题可能需要较快的读入方式，最大数据点读入数据约 20MB」
//   —— 第 ⑥ 步量了三种读法，默认 cin 在顶格上要 2.6 秒（时限 2 秒）。

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

const int MAXN = 1000006;
int c[MAXN], a[MAXN], pre[MAXN], ans[MAXN];
int n, m;

inline int lowbit(int i) { return i & -i; }
void add(int p, int v) { for (int i = p; i <= n; i += lowbit(i)) c[i] += v; }
int sum(int r) { int s = 0; for (int i = r; i > 0; i -= lowbit(i)) s += c[i]; return s; }

/* 手写快读（题面点名要它） */
static char ibuf[1 << 22];
static size_t ipos = 0, ilen = 0;
static inline int gc() {
    if (ipos == ilen) { ilen = fread(ibuf, 1, sizeof(ibuf), stdin); ipos = 0; if (!ilen) return EOF; }
    return ibuf[ipos++];
}
static inline int readInt() {
    int ch = gc(), x = 0;
    while (ch != EOF && (ch < '0' || ch > '9')) ch = gc();
    for (; ch >= '0' && ch <= '9'; ch = gc()) x = x * 10 + (ch - '0');
    return x;
}

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

int main() {
    n = readInt();
    for (int i = 1; i <= n; i++) a[i] = readInt();
    m = readInt();
    vector<Q> qs(m);
    for (int i = 0; i < m; i++) { qs[i].l = readInt(); qs[i].r = readInt(); qs[i].id = i; }

    // ★ 按右端点升序 —— 这一句就是「离线」两个字
    sort(qs.begin(), qs.end(), [](const Q& x, const Q& y) { return x.r < y.r; });

    int j = 0;
    for (int i = 1; i <= n; i++) {
        if (pre[a[i]]) add(pre[a[i]], -1);      // ⚠ 把这种贝壳上一次的那个 1 抹掉
        add(i, 1);
        pre[a[i]] = i;
        while (j < m && qs[j].r == i) { ans[qs[j].id] = sum(qs[j].r) - sum(qs[j].l - 1); j++; }
    }

    string out;
    for (int i = 0; i < m; i++) { out += to_string(ans[i]); out += '\n'; }
    fwrite(out.data(), 1, out.size(), stdout);
    return 0;
}