HEOI2012 采花

题目传送门

好奇怪的人物名字

和这道题的树状数组解法思想相同

我们要找区间中至少出现了两次的颜色，则区间内第一次出现的颜色没有价值，只有第二次出现的颜色才会对答案有所贡献。
先预处理出各个位置nex[i]，表示下一个该位置上的颜色出现的位置。
将询问按左端点排序，对于一个询问，从左向右枚举到左端点\(-1\)
对于当前枚举到的节点\(i\)，将它剔除，因为\(i\)被剔除，nex[i]就变成了第一次出现的位置，所以将它的贡献减去，而nex[nex[i]]变成了第二次出现的位置，需要将它的贡献加上
用树状数组维护，答案就是sum(r) - sum(l-1)

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define LL long long
#define lb (i & -i)
using namespace std;
LL read() {
    LL k = 0, f = 1; char c = getchar();
    while(c < '0' || c > '9') {
        if(c == '-') f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9')
        k = k * 10 + c - 48, c = getchar();
    return k * f;
}
int n, c, m, tree[2000010];
inline void add(int x, int k) {
    for(int i = x; i <= n; i += lb)
        tree[i] += k;
}
inline int sum(int x) {
    int ans = 0;
    for(int i = x; i; i -= lb)
        ans += tree[i];
    return ans;
}
int col[2000010], nex[2000010], pos[2000010];
struct zzz {
    int l, r, tim;
}q[2000010];
bool cmp(zzz x, zzz y) {
    return x.l < y.l;
}
int ans[2000010];
int main() {
    n = read(), c = read(), m = read();
    for(int i = 1; i <= n; ++i) col[i] = read();
    for(int i = n; i; --i)
        nex[i] = pos[col[i]], pos[col[i]] = i;
    for(int i = 1; i <= c; ++i)
        if(pos[i] && nex[pos[i]]) add(nex[pos[i]], 1);
    for(int i = 1; i <= m; ++i)
        q[i].l = read(), q[i].r = read(), q[i].tim = i;
    sort(q+1, q+m+1, cmp);
    int l = 1;
    for(int i = 1; i <= m; ++i) {
        for(; l < q[i].l; ++l) {
            if(nex[l]) add(nex[l], -1);
            if(nex[nex[l]]) add(nex[nex[l]], 1);
        }
        ans[q[i].tim] = sum(q[i].r) - sum(q[i].l-1);
    }
    for(int i = 1; i <= m; ++i) printf("%d\n", ans[i]);
    return 0;
}

HEOI2012 采花

原文：https://www.cnblogs.com/morslin/p/11855882.html