SP3267 D-query

题意

给出一段序列。求取区间范围[l,r] 中的序列出现的次数。

思路

足够详细的博文

这个题目最好的方法是采用前缀和的方式离线查询。

不过，为了学习莫队算法，这个题目主要用来讲解莫队算法该如何工作。

首先，我们对于区间 [l,r] 的查询，由于我们可以通过改变区间的方式进行不断的增大减小。

所以我们不妨开出来两个指针 l \ r 用来表示当前的区间，另外设置一个数字来表示当前的答案是多少。

每次查询的时候我们通过移动指针来更新答案。

由于我个人比较习惯闭区间的各种写法，因此我初始化区间为 [0 , -1] 。即 l = 0 , r = -1 表示空区间。

对于每次查询，我们都会获得当前的区间 [ql , qr] 。

然后我们尝试把 l \ r 移动到我们当前的区间上去。

由于我并不了解空区间进行移动的时候会不会出现未遇见的错误，因此我通常会采取先扩张后缩减的做法。

在做好两端区间的增减操作后，采用下面的进行即可。

while(r < qr) add(++r);
while(l > ql) add(--l);
while(r > qr) del(r--);
while(l < ql) del(l++);

由于此时，我们并没有顺序。

这样无规则移动的话必定带来TLE

因此我们需要为此算法规定一个方向。

我们对每个元组$(l,r)(l,r)$ 进行如下方式的排序。

const int part = sqrt(n) + 1;
sort(querry.begin() , querry.end() , [&](auto &A , auto &B){
    if(A.l / part == B.l / part) return A.r < B.r;
    return A.l / part < B.l / part;
}) ;

可以看到，我们的第一关键字为，该元素所在的区间块，第二关键字为右端点。

我们不妨计算一下 l \ r 分别会移动几次。

首先，对于 l 由于是一块一块的移动。

首先为跨块的情况每次移动 $O(\sqrt{N})O(\backslash sqrt\; N)$ ，最多在块内移动 $NN$ 次，由于我们最多会产生 $\sqrt{N}\times \sqrt{N}=N\backslash sqrt\; N\; \backslash times\; \backslash sqrt\; N\; =\; N$ 的跨块移动。所以最终的移动次数在 $O(N\sqrt{N}+N)O(N\backslash sqrt\; N\; +\; N)$ 也就是 $O(N\sqrt{N})O(N\backslash sqrt\; N)$

我们在来看 $rr$ 的移动范围。首先，如果 l 为进行跨块的话，我们的 r 是单调递增的，时间复杂度为$O(N)O(N)$ 由于我们共会产生 $O(\sqrt{N})O(\backslash sqrt\; N)$ 次跨块的行为。

所以我们最终的时间复杂度为 $O(N\sqrt{N})O(N\backslash sqrt\; N)$

所以最后，我们依据排序过后的数据进行区间的增减即可。

#include <algorithm>
#include <iostream>
#include <tuple>
#include <vector>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  
  int maxx = -1;
  int n;
  cin >> n;
  vector<int> v(n);
  for (auto &x : v) {
    cin >> x;
    x--;
    maxx = max(maxx, x);
  }
  vector<int> cnt(maxx + 1, 0);

  int q;
  cin >> q;

  vector<tuple<int, int, int>> querry(q);

  auto get_mid = [](int x) -> int {
    int l = 0, r = 1e4;
    int res = -1;
    while (l <= r) {
      int m = (l + r) >> 1;
      if (m * m >= x) {
        res = m;
        r = m - 1;
      } else {
        l = m + 1;
      }
    }
    return res;
  };

  const int prt = get_mid(n);

  for (int i = 0; i < q; i++) {
    auto &[l, r, id] = querry[i];
    cin >> l >> r;
    l--, r--;
    id = i;
  }

  sort(querry.begin(), querry.end(), [&](auto &A, auto &B) {
    auto [la, ra, ida] = A;
    auto [lb, rb, idb] = B;
    if (la / prt == lb / prt) return ra < rb;
    return la / prt < lb / prt;
  });

  vector<int> ans(q);

  int l = 0, r = -1;

  int res = 0;

  auto add = [&](int idex) -> void {
    if (cnt[v[idex]] == 0) res++;
    cnt[v[idex]]++;
  };

  auto mov = [&](int idex) -> void {
    cnt[v[idex]]--;
    if (cnt[v[idex]] == 0) res--;
  };

  for (auto [ql, qr, id] : querry) {
    while (r < qr) add(++r);
    while (l > ql) add(--l);
    while (l < ql) mov(l++);
    while (r > qr) mov(r--);
    ans[id] = res;
  }

  for (auto &x : ans) cout << x << '\n';

  return 0;
}

线段树的做法

#include <algorithm>
#include <iostream>
#include <tuple>
#include <vector>

using namespace std;

struct SEG_Tree {
  vector<pair<int, int>> Range;
  vector<int> cnt;
  SEG_Tree(int n) {
    int size = 1;
    while (size < n) size *= 2;
    Range.assign(size * 2, {});
    cnt.assign(size * 2, {});
    build(0, n - 1);
  }

  int Lson(int x) { return x * 2 + 1; }
  int Rson(int x) { return x * 2 + 2; }

  void build(int l, int r, int p = 0) {
    Range[p] = {l, r};
    if (l == r) return;
    int m = (l + r) >> 1;
    build(l, m, Lson(p));
    build(m + 1, r, Rson(p));
    push_up(p);
  }

  void push_up(int p) { cnt[p] = cnt[Lson(p)] + cnt[Rson(p)]; }

  void add(int x, int val, int p = 0) {
    auto [l, r] = Range[p];
    if (l == x && r == x) {
      cnt[p] = val;
      return;
    }
    int m = (l + r) >> 1;
    if (x <= m) add(x, val, Lson(p));
    if (x > m) add(x, val, Rson(p));
    push_up(p);
  }

  int sum(int x, int y, int p = 0) {
    auto [l, r] = Range[p];
    if (x <= l && r <= y) {
      return cnt[p];
    }
    int m = (l + r) >> 1;
    int res = 0;
    if (x <= m) res += sum(x, y, Lson(p));
    if (y > m) res += sum(x, y, Rson(p));
    return res;
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  vector<int> v(n);
  const int N = 1e6 + 10;
  vector<int> pos(N, -1);
  for (auto &x : v) cin >> x;
  int q;
  cin >> q;

  vector<int> ans(q);
  vector<tuple<int, int, int>> que(q);

  int now = 0;

  for (auto &[r, l, id] : que) {
    id = now++;
    cin >> l >> r;
    l--, r--;
  }

  sort(que.begin(), que.end());

  now = 0;

  SEG_Tree st(n);
  for (auto [r, l, id] : que) {
    while (now < v.size() && now <= r) {
      if (pos[v[now]] != -1) st.add(pos[v[now]], 0);
      st.add(now, 1);
      pos[v[now]] = now;
      now++;
    }
    ans[id] = st.sum(l, r);
  }

  for (auto x : ans) cout << x << '\n';

  return 0;
}