HH 的项链 解题报告（SDOI 2009 线段树 排序 离线处理）
2018-05-23
HH 有一串由各种漂亮的贝壳组成的项链。HH 相信不同的贝壳会带来好运，所以每次散步完后，他都会随意取出一段贝壳，思考它们所表达的含义。HH 不断地收集新的贝壳，因此他的项链变得越来越长。
本文迁移自老博客，原始链接为 https://lookas2001.com/hh-%e7%9a%84%e9%a1%b9%e9%93%be-%e8%a7%a3%e9%a2%98%e6%8a%a5%e5%91%8a/
有一天，他突然提出了一个问题：某一段贝壳中，包含了多少种不同的贝壳？
这个问题很难回答。。。因为项链实在是太长了。于是，他只好求助睿智的你，来解决这个问题。
输入
第一行：一个整数N，表示项链的长度。
第二行：N个整数，表示依次表示项链中贝壳的编号（编号为0到1000000之间的整数）。
第三行：一个整数M，表示HH询问的个数。
接下来M行：每行两个整数，L和R（1 ≤ L ≤ R ≤ N），表示询问的区间。
N ≤ 50000，M ≤ 200000。
输出
M行，每行一个整数，依次表示询问对应的答案。
样例输入
6
1 2 3 4 3 5
3
1 2
3 5
2 6
样例输出
2
2
4
来源
SDOI 2009
在线评测
算法设计
看到题目，首先想了想所学的数据结构，当前还没有如此高级的数据结构可以求任意的一个区间内有多少种数字。那么我们试试能不能在确定一个端点的前提下，通过简单的数据结构得到结果。
这道题目我们需要离线处理，将所有的查询根据右节点从小到大排序，使其变得有序后进行操作。
我们定义一个变量 k 为当前推进（或者说枚举）到的右节点，定义一棵线段树，第 j 个节点的含义为 j-k 内不同的数字个数
我们定义一个数组 last 数组，第 i 个元素为 第 i 个贝壳序号 在 贝壳序列中 上一次出现的位置。
我们可以发现，如果我们推进到了一个新的 k，很明显 1 ~ last[k] 到 k 这些段中一定是存在 第 k 个贝壳序号，而在 last[k] + 1 ~ k 到 k 这些段中是不存在的。那反映到线段树中 last[i] + 1 ~ k 所有节点都应该 + 1。
没听懂？没关系，可以看看下面的代码。
示例代码
#include <cstdio>
#include <cstring>
#include <algorithm>
//using namespace std;
const int N = 55000, M = 220000, MAX = 1100000;
int n, m, a[N];
int last[N];
int idx[MAX]; // 本来是 index 但是与头文件中的函数冲突了
struct q_d {
int l, r, id;
} q[M];
int result[M];
inline bool cmp(q_d a, q_d b) {
return a.r < b.r;
}
struct node {
int l, r;
int f;
node *lc, *rc;
} mem[2 * N];
node *memp;
node *root;
inline void push_down(node *p) {
if (p->f) {
p->lc->f += p->f;
p->rc->f += p->f;
p->f = 0;
}
}
node *init(int l, int r) {
node *p = memp++;
p->l = l;
p->r = r;
p->f = 0;
if (l == r) {
p->lc = p->rc = NULL;
} else {
int mid = (l + r) >> 1;
p->lc = init(l, mid);
p->rc = init(mid + 1, r);
}
return p;
}
void change(node *p, int l, int r) {
if (l <= p->l && p->r <= r) {
++p->f;
return;
}
push_down(p);
int mid = (p->l + p->r) >> 1;
if (l <= mid) change(p->lc, l, r);
if (mid < r) change(p->rc, l, r);
}
int query(node *p, int i) {
if (p->l == p->r) {
return p->f;
}
push_down(p);
int mid = (p->l + p->r) >> 1;
if (i <= mid) return query(p->lc, i);
return query(p->rc, i);
}
int main() {
// freopen("input.txt", "r", stdin);
scanf("%d", &n);
memset(idx, 0, sizeof idx);
for (int i = 1; i <= n; ++i) {
scanf("%d", a + i);
last[i] = idx[a[i]];
idx[a[i]] = i;
}
scanf("%d", &m);
for (int i = 1; i <= m; ++i) {
scanf("%d%d", &q[i].l, &q[i].r);
q[i].id = i;
}
std::sort(q + 1, q + m + 1, cmp);
//
// for (int i = 1; i <= m; ++i) printf("%d %d\n", q[i].l, q[i].r);
int j = 1;
memp = mem;
root = init(1, n);
for (int i = 1; i <= n; ++i) {
change(root, last[i] + 1, i);
for (; q[j].r == i && j <= m; ++j) {
result[q[j].id] = query(root, q[j].l);
}
}
for(int i = 1; i <= m; ++i) printf("%d\n", result[i]);
return 0;
}