题解

【SDOI2009】HH的项链

题目链接

LuoguP1972

题目描述

$\text{HH}$ 有一串由各种漂亮的贝壳组成的项链。$\text{HH}$ 相信不同的贝壳会带来好运,所以每次散步完后,他都会随意取出一段贝壳,思考它们所表达的含义。$\text{HH}$ 不断地收集新的贝壳,因此,他的项链变得越来越长。有一天,他突然提出了一个问题:某一段贝壳中,包含了多少种不同的贝壳?这个问题很难回答……因为项链实在是太长了。于是,他只好求助睿智的你,来解决这个问题。

输入输出格式

输入格式:

第一行:一个整数 $\text{N}$,表示项链的长度。
第二行:$\text{N}$ 个整数,表示依次表示项链中贝壳的编号(编号为 $0$ 到 $1000000$ 之间的整数)。
第三行:一个整数 $\text{M}$,表示 $\text{HH}$ 询问的个数。
接下来 $\text{M}$ 行:每行两个整数,$\text{L}$ 和 $\text{R}(1 \leq L \leq R \leq N)$,表示询问的区间。

输出格式:

$\text{M}$ 行,每行一个整数,依次表示询问对应的答案。

输入输出样例

输入样例#1:

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

输出样例#1:

2
2
4

说明

数据范围:
对于 $100 \%$ 的数据,$ n \leq 500000, m \leq 500000$

题解

题意很简单明了,就是求区间不同的数的个数,可以离线
主席树当然是可以做的,主席树可以在线解决。但是我好久没写了,而且常数还大,莫队也可以跑过去
但是有点大材小用,树状数组离线就够了
分析一下题目的性质,不难看出,如果查询的区间 $[l, r]$ 内有重复的数,这个重复的数只会在一个位置被计算贡献,其他位置的贡献要去掉。
先把询问读进来,然后按照右端点的位置升序排序,用树状数组记录贡献,某一个询问的答案用树状数组查询一下前缀和差分一下就可以得到。但是这样是会重复计算相同的数的贡献的,考虑去重。
对于一个数 $\text{w}$,如果它在序列中多次出现,那么我们按照这样排序之后,只需要保留最靠右的 $\text{w}$ 的贡献,因为对于一次右端点在 $\text{w}$ 右边的查询,这次查询要么不包含任意一个 $\text{w}$,要么包含一个或者多个。我们只保留最靠右的那一个的贡献,就会消除掉重复的贡献,故思路是对的。开一个数组 $\text{last[i]}$ 表示 $\text{i}$ 最后一次出现的位置,如果出现过就去掉前面的贡献

代码

#include <cstdio>
#include <iostream>
#include <algorithm>
#define rep(i, l, r) for(int i = l; i <= r; i++)
const int MAXN = 1e6 + 7;
int n, m, a[MAXN], t[MAXN], last[MAXN], now = 1;
inline int lowbit(int x) {
    return x & (-x);
}
void add(int x, int d) {
    for (; x <= n; x += lowbit(x))
        t[x] += d;
}
int sum(int x) {
    int ret = 0;
    for (; x; x -= lowbit(x))
        ret += t[x];
    return ret;
}
inline int query(int l, int r) {
    return sum(r) - sum(l - 1);
}
struct Pro {
    int l, r, pos;
    bool operator < (const Pro &other) const {
        return r < other.r;
    }
} ask[MAXN];
int ans[MAXN];
int main(int argc, char *argv[]) {
    scanf("%d", &n);
    rep(i, 1, n) {
        scanf("%d", a + i);
    }
    scanf("%d", &m);
    rep(i, 1, m) {
        scanf("%d %d", &ask[i].l, &ask[i].r);
        ask[i].pos = i;
    }
    std::sort(ask + 1, ask + m + 1);
    rep(i, 1, m) {
        rep(j, now, ask[i].r) {
            if (last[a[j]]) add(last[a[j]], -1);
            add(j, 1);
            last[a[j]] = j;
        }
        ans[ask[i].pos] = query(ask[i].l, ask[i].r);
        now = ask[i].r + 1;
    }
    rep(i, 1, m) {
        printf("%d\n", ans[i]);
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注