一些“出现次数”相关的序列模型

V1（【COCI 2016/2017 #5】Poklon）

题目大意

  给出一个长度为 $n$ 的序列 $a_1...a_n$。
  有 $Q$ 次询问，每次询问序列中的一个区间，有多少个数恰好出现两次。
  $n,Q \leq 5 \times 10^5$

题解

  套路题。

  记 $last_i$ 表示上一个与 $a_i$ 相同的是谁。
  把询问按右端点排序，然后从左往右扫这个序列，并用线段树维护右端点为当前位置的区间的答案。当扫到第 $i$ 位的时候，就给区间 $[ last_{last_i}+1 , last_i ]$ 加 $1$，给区间 $[ last_{last_{last_i}}+1 , last_{last_i} ]$ 减 $1$。然后处理右端点为 $i$ 的询问。
  时间复杂度 $O(n \log n)$

V1.1

题目大意

  给出一个长度为 $n$ 的序列 $a_1...a_n$。
  有 $Q$ 次询问，每次询问序列中的一个区间，出现了多少种数。
  $n,Q \leq 10^5$

题解

  跟 V1 差不多的套路，每次新加入 $i$，就在 $[ last_i+1, i ]$ 这个区间 $+1$。
  维护一个指针（单调向前）还可以统计有多少个区间出现了全部的数。
  时间复杂度 $O(n \log n)$

V1.2

题目大意

  给出一个长度为 $n$ 的序列 $a_1...a_n$。
  有 $m$ 次操作：
   1：单点修改
   2：询问序列的某个区间内有多少个数恰好出现 1 次
  （可强制在线）

  $n,m \leq 10^5$

题解

  蒟蒻我想不到什么好方法啊。。。
  离线的话可以用带修改莫队来艹，时间复杂度 $O(n^{\frac{5}{3}})$
  在线可以树套树，第一棵树表示左端点，第二棵树表示右端点。单点修改相当于插入删除，类似 V1 那样讨论一下。时间复杂度 $O(n \log^2 n)$。（不知会不会炸空间。。。）

V2

题目大意

  给出一个长度为 $n$ 的序列 $a_1...a_n$。
  有 $m$ 次操作：
   1：单点修改
   2：询问序列有多少个子区间，满足区间内每个数最多出现 1 次

  $n,m \leq 10^5$

题解1

  设 $f_i$ 表示以 $i$ 为左端点，最右能到多少。那么 $\sum f_i$ 就是答案。
  记 $last_i$ 表示上一个与 $a_i$ 相同的是谁，我们把 $last_i$ 向 $i$ 连一条线段，那么每条线段就有个存在时间。每条线段对 $f$ 的影响是区间取 min 操作（$[ l, r-1 ] ~\min= r$）。
  我们按操作时间来分治，每个分治区间只考虑存在时间完全包含当前区间的线段。现在问题变成：有一堆区间取 min 操作，中间还有一些询问 $\sum f[i]$，并且操作要可撤销。
  所以用主席树来维护，由于 $f$ 是递增的，所以区间取 min 可以看作是某一段的区间赋值，然后这样就可撤销啦！（加上空间回收就不怕 MLE 啦！）

  时间复杂度 $O(n \log^2 n)$

题解2

  来个在线做法。

  还是用线段树维护 $f_i$ 表示以 $i$ 为左端点，最右能到多少。并且维护一下每个区间的答案。
  修改相当于删除一个 $last_i$ 和加入一个 $last_i$，这些讨论一下都是区间取 min 和区间赋值操作。
  然后询问，相当于要合并 $\log$ 个区间。我们从右往左合并，每次我们知道右区间的最小的 $f$ 是多少，比如是 $f_x$，然后在左区间二分出 $f$ 值大于 $f_x$ 的区间，这时候就可以知道对答案的影响了。

  时间复杂度 $O(n \log^2 n)$

V2.1

题目大意

  给出一个长度为 $n$ 的序列 $a_1...a_n$，和一个常数 $k$。
  有 $m$ 次操作：
   1：单点修改
   2：询问序列的某个区间内有多少个子区间，满足区间内每个数最多出现 $k$ 次

  $n,m \leq 1e5,~k \leq 5$

题解

  可以用 V2 的解法1，然后主席树询问的时候改成区间询问。
  $k$ 次就相当于线段是 $last_{ last_{ ...(k次) } }$ 连向 $i$ 的线段。

V2.2（【bzoj 2017省选十连测】 巧克力）

题目大意

  给出一个长度为 $n$ 的序列 $a_1...a_n$。
  有 $m$ 次操作：
   1：单点修改
   2：询问第 $x$ 次修改操作后的序列有多少个子区间，满足区间内每个数最多出现 1 次

  $n,m \leq 1e5$，强制在线

题解

  V2 的解法2，把修改操作可持久化一下

V3（【CodeM 初赛A】5）

题目大意

  给出一个长度为 $n$ 的序列 $a_1...a_n$，有 $m$ 个询问，每次询问给出 $l, r, k$，问 $a_l~a_r$ 中，有多少数的出现次数与 $k$ 互质。
  $n,m \leq 5e4,~1\leq a_i,k \leq n$
  时限 6s

题解

  区间问题可以考虑莫队，可以维护一个桶 $t_i$ 表示有多少数的出现次数是 $i$。

  但是统计答案不方便，要把整个桶扫一次。

  于是设个阈值 $S=\sqrt n$。如果某个数在全局的出现次数 $>S$，就提取出来单独对每个询问做贡献，剩下的数就做莫队。

V4（学长出题）

题目大意

  上面的题的出现次数都是固定的，如果不固定呢？

  给出一个长度为 $n$ 的序列 $a_1...a_n$。
  有 $Q$ 次询问，每次询问给出 $l,r,k$，问区间 $[l,r]$ 有多少个数的出现次数小于等于 $k$。
  $n,Q \leq 10^5$

题解

  一种比较直接的想法是，莫队，用一个树状数组维护每个数的出现次数。时间 $O(n\sqrt n~log~n)$。
  但这样有点慢。

  实际上，出现次数我们需要的是一个前缀和。我们直接维护前缀和。
  莫队时的本质是增加一个数或去掉一个数，因此造成的影响只会是某个数的出现次数加 $1$ 或减 $1$，对应在前缀和上最多只影响 1 位。比如 $5$ 在当前区间出现了 $3$ 次，现在又加了一个 $5$ 进来，它的出现次数由 $3$ 变成 $4$，那么前缀和数组就只是 $3$ 这个位置减 $1$。
  因此就不用树状数组了，直接记录前缀和数组每个位置的变化量和一个全局量（某个数从 $0$ 次变为 $1$ 次，是同时给数组所有元素 $+1$）就行了。这样就是 $O(n\sqrt n)$ 了。

V5（【Ynoi2016】掉进兔子洞）

题目大意

  一个长为 $n$ 的序列 $a$。
  有 $m$ 个询问，每次询问三个区间，把三个区间中同时出现的数一个一个删掉，问最后三个区间剩下的数的个数和，询问独立。
  注意这里删掉指的是一个一个删，不是把等于这个值的数直接删完，
  比如三个区间是 $[1,2,2,3,3,3,3]$，$[1,2,2,3,3,3,3]$ 与 $[1,1,2,3,3]$，就一起扔掉了 1 个 $1$，1 个 $2$，2 个 $3$。

  $n,m \leq 10^5,~1 \leq a_i \leq 10^9$
  3s，512M

题解

  说到出现次数，还是不能缺少 bitset。有时候莫队+bitset 是处理“数字是否出现”或“出现次数”的好办法。至于 bitset 如何处理相同的数字，那就是这题为例了。
  这里是题解

未完待续