HEOI2012 采花

未分类

要计算在一个区间内出现两次以上的数的个数，可以看成每种颜色只有第二个出现的才有贡献，那么将查询离线按 $l$ 排序，然后树状数组维护。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
const int MAXN = 3e6;
int n, m;
int a[MAXN | 1], nxt[MAXN | 1], col[MAXN | 1];
int bit[MAXN | 1], ans[MAXN | 1];
struct Query {
  int l, r, id;
  Query() : l(0), r(0), id(0) {}
  friend bool operator< (const Query &lhs, const Query &rhs) {
    return lhs.l < rhs.l;
  }
} que[MAXN | 1];
inline int read() {
  register int x = 0;
  register char ch = getchar();
  while (!isdigit(ch)) ch = getchar();
  while (isdigit(ch)) {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x;
}
int query(int x) {
  int res = 0;
  while (x > 0) {
    res += bit[x];
    x -= x & (-x);
  }
  return res;
}
void modify(int x, int y) {
  while (x <= n) {
    bit[x] += y;
    x += x & (-x);
  }
}
int main() {
  freopen("code.in", "r", stdin);
  freopen("code.out", "w", stdout);
  n = read();
  read();
  m = read();
  for (int i = 1; i <= n; ++i) a[i] = read();
  for (int i = n; i >= 1; --i) {
    nxt[i] = col[a[i]];
    col[a[i]] = i;
  }
  for (int i = 1; i <= m; ++i) {
    que[i].l = read();
    que[i].r = read();
    que[i].id = i;
  }
  std::sort(que + 1, que + 1 + m);
  memset(col, 0, sizeof(col));
  for (int i = 1; i <= n; ++i) {
    if (++col[a[i]] == 2) modify(i, 1);
  }
  for (int i = 1; i <= m; ++i) {
    if (que[i].l != que[i - 1].l) {
      for (int j = que[i - 1].l; j < que[i].l; ++j) {
        if (nxt[j]) modify(nxt[j], -1);
        if (nxt[nxt[j]]) {
          modify(nxt[nxt[j]], 1);
        }
      }
    }
    ans[que[i].id] = query(que[i].r) - query(que[i].l - 1);
  }
  for (int i = 1; i <= m; ++i) printf("%d\n", ans[i]);
  return 0;
}