【P1972】HH的项链——树状数组+询问离线

（题面摘自luogu）

题目背景

无

题目描述

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

输入输出格式

输入格式：

第一行：一个整数N，表示项链的长度。

第二行：N 个整数，表示依次表示项链中贝壳的编号（编号为0 到1000000 之间的整数）。

第三行：一个整数M，表示HH 询问的个数。

接下来M 行：每行两个整数，L 和R（1 ≤ L ≤ R ≤ N），表示询问的区间。

输出格式：

M 行，每行一个整数，依次表示询问对应的答案。

说明

数据范围：

对于100%的数据，N <= 500000，M <= 500000。

　　老师讲了两种办法，先只打了第一种。（好像莫队也能做……以后再说）

　　首先我们把询问离线，按右端点排序。然后我们从左至右扫描原序列（可以离散化）：假如我们想处理[l, r]这个询问，我们在扫描序列的时候把每个颜色对应的位置在树状数组中+1，扫描到r的时候直接查询[l, r]的区间和即可。但是布星，有重复的颜色怎么破？

　　再来考虑我们扫描的过程：一个颜色产生对[l, r]的贡献，当且仅当这个颜色在已扫描序列[1, r]的最右端的位置pos，满足pos >= l。那么我们动态维护某个颜色出现的位置，在扫描的时候一边往BIT里扔贡献，一边删掉该颜色上次出现位置的贡献，然后更新这个颜色的最后一个位置。这时每查到一个询问再询问l, r区间和就是可行的。

　　代码中有个小细节很坑，可供参考。

  1. #include <cstdio>    
  2. #include <cstring>    
  3. #include <iostream>    
  4. #include <algorithm>    
  5. //#define L second    
  6. //#define R first    
  7. //#define mp make_pair    
  8. #define BUG puts("$$$")    
  9. #define lowbit(i) (i & -i)    
  10. #define maxn 500010    
  11. template <typename T>    
  12. void read(T &x) {    
  13.     x = 0;    
  14.     int f = 1;    
  15.     char ch = getchar();    
  16.     while (!isdigit(ch)) {    
  17.         if (ch == '-')    
  18.             f = -1;    
  19.         ch = getchar();    
  20.     }    
  21.     while (isdigit(ch)) {    
  22.         x = x * 10 + (ch ^ 48);    
  23.         ch = getchar();    
  24.     }    
  25.     x *= f;    
  26.     return;    
  27. }    
  28. using namespace std;    
  29. struct Query {    
  30.     int l, r, id;    
  31.     friend bool operator < (Query a, Query b) {    
  32.         return a.r < b.r;    
  33.     }    
  34. } Q[maxn];    
  35. int bit[maxn], a[maxn], pos[maxn], n, m, N;    
  36. int st[maxn], ans[maxn];//辅助     
  37. int contra(int* a) {    
  38.     memcpy(st, a, sizeof(st));    
  39.     sort(st + 1, st + 1 + n);    
  40.     int len = unique(st + 1, st + 1 + n) - st - 1;    
  41.     for (int i = 1; i <= n; ++i)    
  42.         a[i] = lower_bound(st + 1, st + len + 1, a[i]) - st;    
  43.     return len;    
  44. }    
  45. void modify(int x, int del) {    
  46.     for (int i = x; i <= n; i += lowbit(i))    
  47.         bit[i] += del;    
  48. }    
  49. int query(int l, int r) {    
  50.     int sum = 0;    
  51.     for (int i = r; i; i -= lowbit(i))    
  52.         sum += bit[i];    
  53.     for (int i = l - 1; i; i -= lowbit(i))    
  54.         sum -= bit[i];    
  55.     return sum;    
  56. }    
  57. void solve() {    
  58.     register int i = 1, j = 1;//i指向序列，j指向询问     
  59.     while (j <= m) {    
  60.         while (i <= Q[j].r) {    
  61.             if (pos[a[i]])    
  62.                 modify(pos[a[i]], -1);    
  63.             modify(i, 1);    
  64.             pos[a[i]] = i;    
  65.             ++i;    
  66.         }    
  67.         --i;  //这里：有可能出现右端点相同的情况，不加这句话就跳过了  
  68.         ans[Q[j].id] = query(Q[j].l, Q[j].r);    
  69.         ++j;    
  70.     }    
  71.     return;    
  72. }    
  73. int main() {    
  74.     read(n);    
  75.     for (int i = 1; i <= n; ++i)     
  76.         read(a[i]);    
  77.     contra(a);    
  78.     read(m);    
  79.     for (int i = 1; i <= m; ++i)     
  80.         read(Q[i].l), read(Q[i].r), Q[i].id = i;    
  81.     sort(Q + 1, Q + 1 + m);    
  82.     solve();    
  83.     for (int i = 1; i <= m; ++i)    
  84.         printf("%d ", ans[i]);    
  85.     return 0;    
  86. }    
  87.         

 　　另一种方法不用离线，我们用数组last记录每个位置上该颜色上次出现的位置（第一次出现记0），然后询问每个区间内，有多少个点i满足last[i] < l；但是这个东西怎么维护呢？我想想……我晓得了，是主席树！(OwO)/ 以后再打吧。

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/TY02/p/11191354.html