（题面摘自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\n", ans[i]);
  85. return 0;
  86. }

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

最新文章

  1. 【http代理报文】通过发包实现代理请求网页内容
  2. [转]SQL Server 存储过程 一些常用用法（事物、异常捕捉、循环）
  3. POJ 2486 Apple Tree
  4. 一步一步搭建客服系统 (3) js 实现“截图粘贴”及“生成网页缩略图”
  5. Floating Action Button（漂浮按钮）
  6. java线性表学习笔记（一）
  7. windows server 2003 服务器
  8. CCF 送货 + 欧拉路模板
  9. 如何：对 Web 窗体使用路由
  10. 【SSH 基金会】SSH框架--struts进一步的详细解释（两）
  11. MPlayerX播放视频屏幕中间有图标遮挡的解决办法
  12. 屏幕的尺寸（厘米）、屏幕分辨率（像素）、PPI它们之间是什么关系
  13. [随笔]利用云虚拟机和学校VPN实现校外访问校内站点（反向代理）
  14. 基于HTML5 Canvas实现用户交互
  15. Spark-1.X编译构建及配置安装
  16. mac 配置 ssh 到git (Could not resolve hostname github.com, Failed to connect to github.com port 443 Operation timed out)
  17. jsp 错误处理
  18. 正确实现用spring扫描自定义的annotation
  19. 苹果pns推送和唤醒
  20. 安装mysql.zip文件教程（包含常见问题修复）

热门文章

  1. 前后端分离Java后端主流开发环境框架20200622
  2. Redis学习笔记（四）——数据结构之List
  3. 数据结构（C++）——顺序栈
  4. Java数据结构-03单链表（二）
  5. 使用RS485串口服务器的方法
  6. 数据结构 - 二叉树的遍历（递归VS非递归）
  7. ubuntu下安装RabbitMQ
  8. php生成gitbook路径
  9. [MIT6.006] 16. Dijkstra
  10. Spring Boot 2.4.0 正式发布！全新的配置处理机制，拥抱云原生！