[SDOI2009] HH的项链

题目描述

HH 有一串由各种漂亮的贝壳组成的项链。HH 相信不同的贝壳会带来好运，所以每次散步完后，他都会随意取出一段贝壳，思考它们所表达的含义。HH 不断地收集新的贝壳，因此，他的项链变得越来越长。  

有一天，他突然提出了一个问题：某一段贝壳中，包含了多少种不同的贝壳？这个问题很难回答…… 因为项链实在是太长了。于是，他只好求助睿智的你，来解决这个问题。

输入格式

一行一个正整数 $n$，表示项链长度。   
第二行 $n$ 个正整数 $a_i$，表示项链中第 $i$ 个贝壳的种类。

第三行一个整数 $m$，表示 HH 询问的个数。   
接下来 $m$ 行，每行两个整数 $l,r$，表示询问的区间。

输出格式

输出 $m$ 行，每行一个整数，依次表示询问对应的答案。

样例 #1

样例输入 #1

6
1 2 3 4 3 5
3
1 2
3 5
2 6

样例输出 #1

2
2
4

提示

【数据范围】  

对于 $20\%$ 的数据，$1\le n,m\leq 5000$；   
对于 $40\%$ 的数据，$1\le n,m\leq 10^5$；   
对于 $60\%$ 的数据，$1\le n,m\leq 5\times 10^5$；  
对于 $100\%$ 的数据，$1\le n,m,a_i \leq 10^6$，$1\le l \le r \le n$。

本题可能需要较快的读入方式，最大数据点读入数据约 20MB。

解题思路

  先给出大部分题解给到的做法。

  如果一个区间中重复出现了颜色 $c$，显然只能有一个位置的颜色 $c$ 能给出贡献，这里不妨假设最靠右的位置有贡献。定义 $\text{last}_i$ 表示上一个颜色为 $a_i$ 的位置，这样当我们依次从左往右遍历每个元素 $a_i$ 时，把对颜色 $a_i$ 有贡献的位置从 $\text{last}_i$ 改成 $i$，就能得到以 $i$ 为右端点的前缀中每种颜色产生贡献的位置。如果某个位置有贡献，那么将这个位置变成 $1$，否则变成 $0$，然后用树状数组来维护前缀和，就能得到任意区间 $[l, i], \, l \in [1, i]$ 内不同颜色的数目了，即 query(i) - query(l-1)。

  因此可以离线处理询问，把询问区间按照右端点从小到大排序，枚举到询问 $(l_i, r_i)$ 时，按照上面的方法处理 $i \leq r_i$ 的 $a_i$，那么该询问的答案就是 query(ri) - query(li-1)。

  AC 代码如下，时间复杂度为 $O(m \log{m} + n + m \log{n})$：

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

const int N = 1e6 + 10;

int n, m;
int a[N], last[N];
int l[N], r[N], p[N];
int tr[N];
int ans[N];

int lowbit(int x) {
    return x & -x;
}

void add(int x, int c) {
    for (int i = x; i <= n; i += lowbit(i)) {
        tr[i] += c;
    }
}

int query(int x) {
    int ret = 0;
    for (int i = x; i; i -= lowbit(i)) {
        ret += tr[i];
    }
    return ret;
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", a + i);
    }
    scanf("%d", &m);
    for (int i = 1; i <= m; i++) {
        scanf("%d %d", l + i, r + i);
        p[i] = i;
    }
    sort(p + 1, p + m + 1, [&](int i, int j) {
        return r[i] < r[j];
    });
    for (int i = 1, j = 1; i <= m; i++) {
        while (j <= r[p[i]]) {
            if (last[a[j]]) add(last[a[j]], -1);
            add(j, 1);
            last[a[j]] = j;
            j++;
        }
        ans[p[i]] = query(r[p[i]]) - query(l[p[i]] - 1);
    }
    for (int i = 1; i <= m; i++) {
        printf("%d\n", ans[i]);
    }
    
    return 0;
}

  再给出另外一种做法，主要受到字符串的总引力这题的启发。

  这道题求的是字符串的所有连续子串中不同字符的种类。子串问题的经典做法就是先把子串按照右端点进行分类，当枚举到 $i$ 时，以 $i$ 为右端点的子串就是 $s[l \sim i], \, l \in [1, i]$。

  现在假设我们已经知道以 $i-1$ 为右端点的所有子串中不同字符的种类，记作 $f(l)$ 表示子串 $s[l \sim i-1]$ 的结果，现在求关于子串 $s[l \sim i]$ 的 $f'(l)$。对于 $i$，显然对于满足 $l \in [\text{last}_i+1, i]$ 的 $l$（$\text{last}_i$ 表示上一个字符为 $s_i$ 的位置），子串 $s[l, i]$ 的 $f'(l) = f(l)+1$。而 $l \in [1, \text{last}_i]$ 的 $l$，则有 $f'(l) = f(l)$，因为有重复的 $s_i$ 而 $s_i$ 不会有贡献。

  我们就可以把这个结论用到这道题。当枚举到 $a_i$，只需对 $l \in [\text{last}_i+1, i]$ 中的 $f(l)$ 加 $1$ 即可，因此可以用树状数组维护关于 $f(l)$ 的差分数组。然后与上面一样离线处理询问即可，每个询问的答案就是 query(li)。

  AC 代码如下，时间复杂度为 $O(m \log{m} + n + m \log{n})$：

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

const int N = 1e6 + 10;

int n, m;
int a[N], last[N];
int l[N], r[N], p[N];
int tr[N];
int ans[N];

int lowbit(int x) {
    return x & -x;
}

void add(int x, int c) {
    for (int i = x; i <= n; i += lowbit(i)) {
        tr[i] += c;
    }
}

int query(int x) {
    int ret = 0;
    for (int i = x; i; i -= lowbit(i)) {
        ret += tr[i];
    }
    return ret;
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", a + i);
    }
    scanf("%d", &m);
    for (int i = 1; i <= m; i++) {
        scanf("%d %d", l + i, r + i);
        p[i] = i;
    }
    sort(p + 1, p + m + 1, [&](int i, int j) {
        return r[i] < r[j];
    });
    for (int i = 1, j = 1; i <= m; i++) {
        while (j <= r[p[i]]) {
            add(last[a[j]] + 1, 1);
            add(j + 1, -1);
            last[a[j]] = j;
            j++;
        }
        ans[p[i]] = query(l[p[i]]);
    }
    for (int i = 1; i <= m; i++) {
        printf("%d\n", ans[i]);
    }
    
    return 0;
}

  还可以用主席树来实现在线处理询问。

  这时我们假设同一种颜色中最靠左的位置有贡献，对于询问 $(l,r)$，如何判断某个位置是否是该颜色最靠左的位置？很明显如果 $\text{last}_i < l$ 那么 $i$ 一定是颜色 $a_i$ 最靠左的位置。因此对于每个询问，本质求的是 $\sum\limits_{i=l}^{r}[\text{last}_i < l]$，其中 $[$ $]$ 是艾弗森括号。

  这个可以用可持久化线段树来维护，其中线段树是权值线段树，每个线段树节点维护的是对应的值域区间中出现的数的个数 $s$。从左到右依次枚举 $a_i$，在 $i-1$ 个版本的线段树的基础上对 $\text{last}_i$ 这个位置加 $1$，得到第 $i$ 个版本的线段树，从而维护出 $n$ 个版本的线段树。询问时只需求区间 $[0, l-1]$ 内的 $s$ 即可，其中这里的 $s$ 是第 $r$ 个版本的线段树与第 $l-1$ 个版本的线段树的 $s$ 的差值。

  AC 代码如下，时间复杂度为 $O(n \log{n} + m \log{n})$：

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

const int N = 1e6 + 10;

int a[N], last[N];
struct Node {
    int l, r, s;
}tr[N * 25];
int root[N], idx;

int build(int l, int r) {
    int u = ++idx;
    if (l == r) return u;
    int mid = l + r >> 1;
    tr[u].l = build(l, mid);
    tr[u].r = build(mid + 1, r);
    return u;
}

int modify(int u, int l, int r, int x) {
    int v = ++idx;
    tr[v] = tr[u];
    if (l == r) {
        tr[v].s++;
        return v;
    }
    int mid = l + r >> 1;
    if (x <= mid) tr[v].l = modify(tr[u].l, l, mid, x);
    else tr[v].r = modify(tr[u].r, mid + 1, r, x);
    tr[v].s = tr[tr[v].l].s + tr[tr[v].r].s;
    return v;
}

int query(int u, int v, int l, int r, int ql, int qr) {
    if (l >= ql && r <= qr) return tr[v].s - tr[u].s;
    int mid = l + r >> 1, ret = 0;
    if (ql <= mid) ret = query(tr[u].l, tr[v].l, l, mid, ql, qr);
    if (qr >= mid + 1) ret += query(tr[u].r, tr[v].r, mid + 1, r, ql, qr);
    return ret;
}

int main() {
    int n, m;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", a + i);
    }
    root[0] = build(0, n);
    for (int i = 1; i <= n; i++) {
        root[i] = modify(root[i - 1], 0, n, last[a[i]]);
        last[a[i]] = i;
    }
    scanf("%d", &m);
    while (m--) {
        int l, r;
        scanf("%d %d", &l, &r);
        printf("%d\n", query(root[l - 1], root[r], 0, n, 0, l - 1));
    }
    
    return 0;
}

参考资料

  题解 P1972 【[SDOI2009]HH的项链】：https://www.luogu.com.cn/blog/user3432/solution-p1972

  题解 P1972 【[SDOI2009]HH的项链】：https://www.luogu.com.cn/blog/yiw/solution-p1972

  考虑引力和的变化量（Python/Java/C++/Go）：https://leetcode.cn/problems/total-appeal-of-a-string/solutions/1461618/by-endlesscheng-g405/