P1972 [SDOI2009]HH的项链 题目背景
无 题目描述
HH 有一串由各种漂亮的贝壳组成的项链。HH 相信不同的贝壳会带来好运，所以每次散步完后，他都会随意取出一段贝壳，思考它们所表达的含义。HH 不断地收集新的贝壳，因此，他的项链变得越来越长。有一天，他突然提出了一个问题：某一段贝壳中，包含了多少种不同的贝壳？这个问题很难回答……因为项链实在是太长了。于是，他只好求助睿智的你，来解决这个问题。
输入输出格式 输入格式：
第一行：一个整数N，表示项链的长度。
第二行：N 个整数，表示依次表示项链中贝壳的编号（编号为0 到1000000 之间的整数）。
第三行：一个整数M，表示HH 询问的个数。
接下来M 行：每行两个整数，L 和R（1 ≤ L ≤ R ≤ N），表示询问的区间。
输出格式：
M 行，每行一个整数，依次表示询问对应的答案。
输入输出样例 输入样例#1：
6 1 2 3 4 3 5 3 1 2 3 5 2 6
输出样例#1：
2 2 4
说明
数据范围：
对于100%的数据，N <= 50000，M <= 200000。
下面是我要介绍的两种做法：
<1>离线方法： 首先， 我们可以现将贝壳编号离散化， 缩小数据范围（0 ～ 1000000） -> （0 ～ 50000） 然后， 观察询问， 发现并不强制在线， 那就先把所有询问记录下来(q)， 顺便编个号(id), 然后按照左端点（l）升序排序， 若相同， 就按右端点（r）排序， （详见cmp2()函数）， 接下来就可以一个个地解决问题啦（solve()） 定义： l, r ： 现在统计到的区间[l, r] now： 现在解决到第几个问题 sum： 现在区间中有多少个不同的贝壳 对于每一个问题， 我们都一个个地把l, r 移动到相应位置， 顺便统计答案， 然后将答案存下来（ans[]）， 最后按顺序输出就行啦！
代码：
#include<algorithm> #include<iostream> #include<cstdlib> #include<cstring> #include<cstdio> #define maxn 50005 #define For(a, b, c) for(a = b; a <= c; ++a) using namespace std; int n, m, id[maxn], ans[200010]; int p[maxn], cnt; struct B{ int c, id; }a[maxn]; struct que{ int l, r, id; }q[200010]; int read(){ char x; while((x = getchar()) > '9' || x < '0') ; int u = x - '0'; while((x = getchar()) <= '9' && x >= '0') u = (u << 3) + (u << 1) + x - '0'; return u; } bool cmp1(B a, B b){ return a.c < b.c; } bool cmp2(que a, que b){ if(a.l == b.l) return a.r < b.r; return a.l < b.l; } void pre(){ int i; sort(q + 1, q + m + 1, cmp2); sort(a + 1, a + n + 1, cmp1);//离散化 For(i, 1, n) id[a[i].id] = (a[i].c == a[i - 1].c) ? cnt : ++cnt; //编号相同应属于同一类 } void solve(){ int l = 1, r = 1, sum = 1, now = 1; ++p[id[1]]; while(now <= m){ while(r < q[now].r) if(++p[id[++r]] == 1) ++sum; while(l < q[now].l) if(!--p[id[l++]]) --sum; while(r > q[now].r) if(!--p[id[r--]]) --sum;//移动l, r，记录 ans[q[now++].id] = sum;//存入答案 } } int main(){ #ifndef ONLINE_JUDGE freopen("L.in", "r", stdin); freopen("L.out","w",stdout); #endif int i; n = read(); For(i, 1, n) a[i].c = read(), a[i].id = i; m = read(); For(i, 1, m) q[i].l = read(), q[i].r = read(), q[i].id = i; pre(); solve(); For(i, 1, m) printf("%d\n", ans[i]); return 0; }<2>在线主席树 对于每一个贝壳， 记录它后面最近一个与它相同的贝壳的位置（ne[i]），若没有则记为 n + 1 那么， 对于每一个询问[l, r]，我们就是要求出所有的 i (i >= l && i <= r && ne[i] > r) 的个数 于是， 就可以主席树做了
代码：
#include<iostream> #include<cstdlib> #include<cstdio> #define L(x) ch[x][0] #define R(x) ch[x][1] #define maxn 50005 #define maxm 1000001 #define For(a, b, c) for(a = b; a <= c; ++a) #define Rep(a, b, c) for(a = b; a >= c; --a) using namespace std; int n, m, a[maxn], pro[1000005], ne[maxn]; int read(){ char x; while((x = getchar()) > '9' || x < '0') ; int u = x - '0'; while((x = getchar()) <= '9' && x >= '0') u = (u << 3) + (u << 1) + x - '0'; return u; } inline void pre(){ int i; Rep(i, n, 1){ ne[i] = pro[a[i]] ? pro[a[i]] : n + 1; pro[a[i]] = i; } } struct Chairman_Tree{ int e, rt[maxn], ch[maxm][2], w[maxm]; void cpy(int x, int y){ ch[x][0] = ch[y][0], ch[x][1] = ch[y][1], w[x] = w[y]; } void insert(int &q, int x, int l = 1, int r = n + 1){ cpy(++e, q); ++w[q = e]; if(l == r) return ; int mid = (l + r) >> 1; if(x <= mid) insert(L(q), x, l, mid); else insert(R(q), x, mid + 1, r); } int query(int t1, int t2, int num, int l = 1, int r = n + 1){ if(l == r) return num > l ? w[t2] - w[t1] : 0; int mid = (l + r) >> 1, k = w[L(t2)] - w[L(t1)]; if(num <= mid) return query(L(t1), L(t2), num, l, mid) + w[R(t2)] - w[R(t1)]; else return query(R(t1), R(t2), num, mid + 1, r); } }d; void build(){ int i; pre(); For(i, 1, n) d.rt[i] = d.rt[i - 1], d.insert(d.rt[i], ne[i]); } int main(){ #ifndef ONLINE_JUDGE freopen("L.in", "r", stdin); freopen("L.out","w",stdout); #endif int i; n = read(); For(i, 1, n) a[i] = read(); build(); m = read(); For(i, 1, m){ int l = read(), r = read(); printf("%d\n", d.query(d.rt[l - 1], d.rt[r], r)); } return 0; } ---------- 然后这道题就完了， 离线还可以用莫队算法优化一下， 有兴趣的可以到： [莫队算法——解决序列上询问的利器 ](http://blog.csdn.net/wt_cnyali/article/details/54897102)