P1972 [SDOI2009]HH的项链

P1972 [SDOI2009]HH的项链

题目大意：

给定一个长度为 $n$ 的序列 $a_1, a_2, …, a_n$ ，和 $m$ 组询问， 每次给定 $l, r$ ，求区间 $[l, r]$ 中不同的数字有几种。

题目正解：

可持久化线段树

题目思路：

可持久化线段树不同于主席树的用法。

注意到这道题题目唯一的难点在于不同的数字，所以可以考虑对相同的数字消除贡献。

最简单有效的方法就是只留下每种数字最后出现的位置的贡献， 但同时又要保证上一次的贡献在这一次贡献出现前不被消除。

所以考虑每次更新某个数 $a_i$，如果之前出现过，直接在 $i - 1$ 版本消除贡献，紧跟着将这次的贡献加进来。

这样在每个点构造的线段树都是一个 $a$ 序列前缀的，每个数字只会在最后出现的位置被统计到的独立线段树。

所以查询答案时，直接在 $R$ 版本的线段树上，查询 $[L, R]$ 区间和即可。

时间复杂度：

$O(nlogn)$

题目代码：

// Code By CloudySky
#include <bits/stdc++.h>
// #define int long long
namespace IO  // namespace IO
using namespace IO;
const int Maxn = 1e6 + 10;
using namespace std;

struct Stree {
  int ls, rs, val;
#define ls(x) St[x].ls
#define rs(x) St[x].rs
#define v(x) St[x].val
} St[Maxn << 6];

int rt[Maxn], tot;

int add (int p, int l, int r, int v, int k) {
  int np = ++tot; 
  St[np] = St[p], v(np) += k;
  if (l == r) return np;
  int mid = (l + r) >> 1;
  if (v <= mid) 
    ls(np) = add (ls(p), l, mid, v, k);
  else 
    rs(np) = add (rs(p), mid + 1, r, v, k);
  return np;
}

int ask (int p, int l, int r, int v) {
  if (l == r) return v(p);
  int mid = (l + r) >> 1;
  if (v <= mid)
    return ask (ls(p), l, mid, v) + v(rs(p));
  else 
    return ask (rs(p), mid + 1, r, v);
}

int lst[Maxn];

signed main() {
  int n = read ();
  for (int i = 1, tmp, v; i <= n; ++i) {
    v = read ();
    if (!lst[v])
      rt[i] = add (rt[i - 1], 1, n, i, 1);
    else
      tmp = add (rt[i - 1], 1, n, lst[v], -1),
      rt[i] = add (tmp, 1, n, i, 1);
    lst[v] = i;
  }
  int m = read ();
  for (int i = 1; i <= m; ++i) {
    int l = read (), r = read ();
    print (ask (rt[r], 1, n, l));
  }
  return 0;
}

本文作者：CloudySky
写作时间： 2021-12-25
最后更新时间： 2021-12-25
遵循协议： BY-NC-SA