首页 > 代码库 > [BZOJ 1878] [SDOI2009] HH的项链

[BZOJ 1878] [SDOI2009] HH的项链

2024-08-08 19:12:53   211人阅读

题目链接： BZOJ - 1878

 

题目分析

题目的询问是某个区间内的颜色种类数，所以我们希望这个区间内的每种颜色只被计数一次，那么我们就选取询问区间内的每种颜色第一次出现的元素计数，之后再出现已经在询问区间中出现过的颜色就不再计数。考虑一种离线算法，如果我们将所有询问按照询问区间的左端点排序，那么所有询问的左端点就是不递减的，一直向右推移。开始时预处理出每个元素后面第一个与它颜色相同的元素是哪一个，并将所有出现的颜色的第一个元素加入到树状数组中。那么开始时维护的区间就是从 1 开始的。每次处理一个询问，如果当前维护的区间左端点比询问的区间左端点靠左，那么就应该将左端点向右推移到询问的左端点。每次将左端点向右移动一格，一个元素被移除，这时它一定是它的颜色在此时维护的区间中的第一个元素，所以它一定存在于树状数组中，那么我们就将它在树状数组中删除，再将它的下一个与它同色的元素加入到树状数组中。然后对于以现在维护的左端点 L 为左端点的询问 (L, R)，只要用树状数组查询R的前缀和 Get(R) 就是答案，这个前缀和中所有的元素都是从 L 开始的区间中某种颜色第一次出现的位置，不会有某种颜色重复计数的情况。

代码

#include <iostream>#include <cstdio>#include <cstdlib>#include <cstring>#include <algorithm>#include <cmath> using namespace std; const int MaxN = 50000 + 5, MaxQ = 200000 + 5, MaxType = 1000000 + 5; int n, m, a, b;int A[MaxN], Next[MaxN], T[MaxN], Last[MaxType], Ans[MaxQ]; struct Query{    int l, r, num;} Q[MaxQ]; bool cmp(Query q1, Query q2) {    return q1.l < q2.l;} void Add(int x, int num) {    for (int i = x; i <= n; i += i & (-i))         T[i] += num; } int Get(int x) {    int ret = 0;    for (int i = x; i >= 1; i -= i & (-i))         ret += T[i];    return ret;} int main() {    scanf("%d", &n);    for (int i = 1; i <= n; i++) scanf("%d", &A[i]);    scanf("%d", &m);    for (int i = 1; i <= m; i++) {        scanf("%d%d", &a, &b);        Q[i].l = a; Q[i].r = b;        Q[i].num = i;    }    sort(Q + 1, Q + m + 1, cmp);    memset(T, 0, sizeof(T));    memset(Last, 0, sizeof(Last));    for (int i = 1; i <= n; i++) {        if (Last[A[i]] == 0) Add(i, 1);        else Next[Last[A[i]]] = i;        Last[A[i]] = i;    }    int x = 1;    for (int i = 1; i <= m; i++) {        while (x < Q[i].l) {            Add(x, -1);            if (Next[x]) Add(Next[x], 1);            ++x;        }        Ans[Q[i].num] = Get(Q[i].r);    }    for (int i = 1; i <= m; i++) printf("%d\n", Ans[i]);    return 0;}

 

[BZOJ 1878] [SDOI2009] HH的项链


联系
我们