P1972 [SDOI2009] HH的项链

[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\le 5000$；
对于 $40\%$ 的数据，$1\le n,m\le 10^5$；
对于 $60\%$ 的数据，$1\le n,m\le 5\times 10^5$；
对于 $100\%$ 的数据，$1\le n,m,a_i\le 10^6$，$1\le l\le r\le n$。

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

解析：

第一眼是莫队，一看数据范围是 $10^6$，莫队估计是不行了。

点开标签，有可持久化线段树，那就用主席树做吧。

每个版本的主席树维护的是前缀和中的信息。对于数字 $a_i$，版本 $rt$ 维护的是左侧距离 $rt$ 最近的 $a_i$。

对于 $a_i$，如果之前 $a_i$ 未出现，进行一次修改即可；如果之前出现了，先删掉上一个 $a_i$，在把当前 $a_i$ 加进去

对于询问 $(l,r)$，在版本为 $r$ 的主席树内查询 $[l,n]$ 中数的个数。在每个版本中，一个数最多出现一次，因此可以实现查询。

输入和输出用快读和快写。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define fi first
#define se second
const int maxn = 1e6+10;
const int INF = 0x3f3f3f3f;
typedef pair<int, int> pii;struct node{int ls, rs, sum;	
}t[maxn * 36];
int tot, n, m, a[maxn], las[maxn], root[maxn];
void build(int &rt, int l, int r){rt = ++tot;if(l == r)return;int mid = (l+r) >> 1;build(t[rt].ls, l, mid);build(t[rt].rs, mid+1, r);	
}
void update(int &rt, int pre, int l, int r, int pos, int v){rt = ++tot;t[rt].ls = t[pre].ls; t[rt].rs = t[pre].rs, t[rt].sum = t[pre].sum + v;if(l == r && l == pos)return;int mid = (l+r) >> 1;if(pos <= mid)update(t[rt].ls, t[pre].ls, l, mid, pos, v);elseupdate(t[rt].rs, t[pre].rs, mid+1, r, pos, v);
}
int query(int k, int l, int r, int pos){if(l == r)return t[k].sum;int mid = (l+r) >> 1;if(pos <= mid)return query(t[k].ls, l, mid, pos) + t[t[k].rs].sum;elsereturn query(t[k].rs, mid+1, r, pos);
}
int read() {int x = 0, f = 1;char c = getchar();while(c<'0' || c>'9'){if(c == '-') f = -1;c = getchar();}while(c>='0' && c<='9') {x = x*10 + c-'0';c=getchar();}		return x*f;
}
void write(int x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x/10);putchar(x%10 + '0');
}
int main(){n = read();build(root[0], 1, n);for(int i = 1; i <= n; i++){a[i] = read();if(las[a[i]] != 0){int tmp; update(tmp, root[i-1], 1, n, las[a[i]], -1);update(root[i], tmp, 1, n, i, 1);}elseupdate(root[i], root[i-1], 1, n, i, 1);		las[a[i]] = i;}m = read();while(m--){int l, r;l = read(); r = read();int res = query(root[r], 1, n, l);write(res); putchar('\n');}return 0;
}