SDOI2094 HH的项链

原题链接:https://www.luogu.org/problem/P1972

收录于 NOI 系列题解集


思路

将贝壳考虑为 10,对于相同种类的贝壳,仅把区间内最右侧的那一个视作 1,左侧重复的均视作 0

这样,我们可以将询问按右边界从小到大排序。向右不断更新贝壳的值为 1,若遇到相同种类,则同时将上一处的值更新为 0。这样在每次更新到每个询问的右边界时,区间和即为询问的答案。

涉及到单点修改,区间查询,由于区间可减,我们可以使用树状数组。

代码

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>

const int MAXN = 1000005, MAXM = 1000005;
int N, M, a[MAXN], bit[MAXN], ans[MAXM], prev[MAXN], id;

struct Query {
  int id, l, r;
} q[MAXM];

bool cmp(const Query &a, const Query &b) {
  return a.r < b.r;
}

inline int lowbit(int x) {
  return x & -x;
}

void update(int p, int x) {
  while (p <= N) {
    bit[p] += x;
    p += lowbit(p);
  }
}

int query(int p) {
  int res = 0;
  while (p >= 1) {
    res += bit[p];
    p -= lowbit(p);
  }
  return res;
}

int main() {
  scanf("%d", &N);
  for (int i = 1; i <= N; ++i) {
    scanf("%d", &a[i]);
  }
  scanf("%d", &M);
  for (int i = 0; i < M; ++i) {
    int l, r;
    scanf("%d%d", &l, &r);
    q[i].id = i;
    q[i].l = l;
    q[i].r = r;
  }
  std::sort(q, q + M, cmp);
  id = 1;
  for (int i = 0; i < M; ++i) {
    while (id <= q[i].r) {
      if (prev[a[id]] != 0) {
        update(prev[a[id]], -1);
      }
      update(id, 1);
      prev[a[id]] = id;
      ++id;
    }
    ans[q[i].id] = query(q[i].r) - query(q[i].l - 1);
  }
  for (int i = 0; i < M; ++i) {
    printf("%d\n", ans[i]);
  }
  return 0;
}
点赞

Leave a Reply