每日一题：Different Integers（树状数组/莫队）

题意

给定长度为 $n$ 的数组，$q$ 次询问 $[1,l]+[r,n]$ 组成的新数组中不相同的元素个数。$(1<=n,q<=1e5)$

solution1

一眼莫队题，主要是要想怎么样把它变成一个连续的区间。其实只要把整个数组再复制一遍接上就可以了，则原来查询的 $r$ 变为 $l$，$l$ 变为 $l+n$，区间连续。

Code

// 1812 ms

#include <bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
const int N = 2e5 + 5;

struct Node {
  int l, r, id;
} node[N];

int n, q, blocks, a[N], b[N], ans[N];

bool cmp(Node a, Node b) {
  if (a.l / blocks == b.l / blocks) return a.r < b.r;
  return a.l < b.l;
}

int main() {
  while (~scanf("%d%d", &n, &q)) {
    for (int i = 1; i <= n; i++) {
      scanf("%d", &a[i]);
      a[i + n] = a[i];
    }
    memset(b, 0, sizeof(b));
    blocks = sqrt(2 * n);
    for (int i = 1; i <= q; i++) {
      scanf("%d%d", &node[i].r, &node[i].l);
      node[i].r += n;
      node[i].id = i;
    }
    sort(node + 1, node + q + 1, cmp);

    int l = 1, r = 0, num = 0;
    for (int i = 1; i <= q; i++) {
      while (l < node[i].l) num -= !--b[a[l++]];
      while (l > node[i].l) num += !b[a[--l]]++;
      while (r < node[i].r) num += !b[a[++r]]++;
      while (r > node[i].r) num -= !--b[a[r--]];
      ans[node[i].id] = num;
    }

    for (int i = 1; i <= q; i++) printf("%d\n", ans[i]);
  }
  return 0;
}

solution2

同样是复制一遍，然后考虑树状数组+离线处理。我们需要保证之前的更新不会对当前的查询构成干扰，可以对查询按照右端点从小到大排序，然后把当前的数更新到当前位置，删除之前的位置，这样保证数是跟排序后的查询一样是从左往右流动的。

Code

// 702 ms
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;

int n, q, a[N], b[N], c[N], ans[N];

struct Node {
  int l, r, id;
} node[N];

bool cmp(Node x, Node y) { return x.r < y.r; }

void update(int x, int y) {
  for (; x <= n; x += x & (-x)) c[x] += y;
}

int query(int x) {
  int sum = 0;
  for (; x >= 1; x -= x & (-x)) sum += c[x];
  return sum;
}

int main() {
  while (~scanf("%d%d", &n, &q)) {
    for (int i = 1; i <= n; i++) {
      scanf("%d", &a[i]);
      a[i + n] = a[i];
    }
    memset(b, 0, sizeof(b));
    memset(c, 0, sizeof(c));
    for (int i = 1; i <= q; i++) {
      scanf("%d%d", &node[i].r, &node[i].l);
      node[i].r += n;
      node[i].id = i;
    }
    sort(node + 1, node + q + 1, cmp);
    n <<= 1;
    int pre = 1;
    for (int i = 1; i <= q; i++) {
      for (int j = pre; j <= node[i].r; j++) {
        if (b[a[j]]) update(b[a[j]], -1);
        b[a[j]] = j;
        update(b[a[j]], 1);
      }
      pre = node[i].r + 1;
      ans[node[i].id] = query(node[i].r) - query(node[i].l - 1);
    }
    for (int i = 1; i <= q; i++) printf("%d\n", ans[i]);
  }
  return 0;
}