Luogu4113 HEOI2012 采花

题意：

求一段区间内，出现次数至少为2的数的个数。

可以考虑转化成像HH的项链一样的模型。

扫描线+树状数组。

考虑左端弹出一个数会造成什么影响，设弹出的数为x，那么一直到x的下一次出现位置的这个区间不受任何影响（因为x只出现了0次或一次，不计入答案），然而对于x的下一次出现位置，到下下一次出现位置之间的答案会减一，因为x本来在这些地方出现了两次，但是我们刚刚把他删了，所以就剩下一次了，对于更靠右的地方，答案不变，因为那些地方x至少出现了三次。

#include <algorithm>
#include <cstdio>
#include <iostream>

using int_t = int;
using std::cin;
using std::cout;
using std::endl;

const int_t LARGE = 2e6 + 10;

struct Operation {
    int_t left, right;
    int_t result;
    int_t id;
    bool operator<(const Operation& x) const { return left < x.left; }
} opts[LARGE + 1];
int_t n, c, m;
int_t arr[LARGE + 1];
int_t next[LARGE + 1];
int_t prev[LARGE + 1];
//颜色k最后一次出现的位置
int_t last[LARGE + 1];
int_t colors[LARGE + 1];
inline int_t lowbit(int_t x) { return x & (-x); }
void add(int_t pos, int_t val) {
    while (pos <= n) {
        arr[pos] += val;
        pos += lowbit(pos);
    }
}
int_t query(int_t pos) {
    int_t result = 0;
    while (pos >= 1) {
        result += arr[pos];
        pos -= lowbit(pos);
    }
    return result;
}
int main() {
    scanf("%d%d%d", &n, &c, &m);
    for (int_t i = 1; i <= n; i++) scanf("%d", &colors[i]);
    for (int_t i = 1; i <= m; i++) {
        auto& thiz = opts[i];
        scanf("%d%d", &thiz.left, &thiz.right);
        thiz.id = i;
    }
    std::sort(opts + 1, opts + 1 + m);
    for (int_t i = 1; i <= n; i++) {
        int_t color = colors[i];
        if (last[color] == 0) {
            last[color] = i;
            prev[color] = -1;
        } else {
            next[last[color]] = i;
            prev[i] = last[color];
            last[color] = i;
        }
    }
    static int_t count[LARGE + 1];
    int_t curr = 0;
    for (int_t i = 1; i <= n; i++) {
        if (next[i] == 0) next[i] = n + 1;
        count[colors[i]] += 1;
        if (count[colors[i]] == 2) {
#ifdef DEBUG
            cout << "color " << i << " = " << colors[i]
                 << " count = " << count[colors[i]] << endl;
#endif
            curr += 1;
        }
        add(i, curr);
        add(i + 1, -curr);
    }
    int_t pos = 1;
    for (int_t i = 1; i <= m; i++) {
        auto& curr = opts[i];
        while (pos < curr.left) {
            int_t next0 = next[pos];
            if (next0 <= n) {
                int_t next1 = next[next0];
                add(next0, -1);
                add(next1, 1);
            }
            pos++;
        }
        curr.result = query(curr.right);
    }
    std::sort(opts + 1, opts + 1 + m,
              [](const Operation& a, const Operation& b) -> bool {
                  return a.id < b.id;
              });
    for (int_t i = 1; i <= m; i++) {
        printf("%d\n", opts[i].result);
    }
    return 0;
}