题解 P1903 【【模板】分块/带修改莫队（数颜色）】

_rqy · 2017-12-26 13:56:26 · 题解

大暴力。

zkw线段树，每个节点上开一个bitset记录该区间里有哪些数。为了数的范围不大，开一个map来实时离散化（反正离散化不要求大小）。

没了。

时间复杂度是O((n+m)\log n*n/b)，其中b是字长（32或64）。

代码：

#include <algorithm>
#include <cstdio>
#include <bitset>
#include <map>
const int N = 12000;
unsigned A[N];
std::bitset<N> B[32768];
std::bitset<N> ans;
int L;
void build(int n) {
  L = 1;
  while (L < n) L <<= 1;
  for (int i = 0; i < L; ++i) {
    B[i + L].reset();
    B[i + L].set((unsigned)A[i]);
  }
  for (int i = L - 1; i; --i)
    B[i] = B[i << 1] | B[i << 1 | 1];
}
void modify(int x, unsigned y) {
  unsigned z = A[x];
  if (z == y) return;
  int i = x + L;
  A[x] = y;
  do {
    B[i].set(y); i >>= 1;
  } while (i && !B[i].test(y));
  B[i = x + L].reset(z);
  while (i > 1 && !B[i ^ 1].test(z))
    B[i >>= 1].reset(z);
}
int query(int x, int y) {
  ans.reset();
  --x; ++y;
  for (x += L, y += L; x != (y ^ 1); x >>= 1, y >>= 1) {
    if (~x & 1) ans |= B[x ^ 1];
    if (y & 1) ans |= B[y ^ 1];
  }
  return (int)ans.count();
}
unsigned get(int x) {
  static unsigned p = 0;
  static std::map<int, unsigned> M;
  if (M.count(x)) return M[x];
  return M[x] = p++;
}
char s[10];
int main() {
  int n, q, x, y;
  scanf("%d%d", &n, &q);
  for (int i = 1; i <= n; ++i) {
    scanf("%d", &x);
    A[i] = get(x);
  }
  build(n + 2);
  while (q--) {
    scanf("%s%d%d", s, &x, &y);
    if (*s == 'R') modify(x, get(y));
    else printf("%d\n", query(x, y));
  }
  return 0;
}

不要喷我，毕竟@huang_yue 都把纯暴力扔上去了qwq。