牛客练习赛73 D 离别

我们发现，对于一个固定的右端点r而言，合法的左端点l一定是一个连续的区间，从某个数第一次出现k次开始合法，到某个数第一次出现k+1次开始不合法。因为我们对询问按右端点离线，对于每扫描一个右端点时将合法的左区间加入到线段树中，然后统计即可O(nlog(n))。

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;

#define lson rt * 2
#define rson rt * 2 + 1

typedef long long ll;

const int N = 3e5 + 100;

ll tree[N * 4], laz[N * 4];

void insert(int rl, int rr, int l, int r, int rt) {
    if (rl == l && rr == r) {
        laz[rt]++;
        tree[rt] += (rr - rl + 1);
        return;
    }
    int m = (l + r) / 2;
    if (rr <= m) insert(rl, rr, l, m, lson);
    else if (m < rl) insert(rl, rr, m + 1, r, rson);
    else {
        insert(rl, m, l, m, lson);
        insert(m + 1, rr, m + 1, r, rson);
    }
    tree[rt] = tree[lson] + tree[rson] + (r - l + 1) * laz[rt];
}

ll query(int rl, int rr, int l, int r, int rt) {
    if (rl == l && rr == r) return tree[rt];
    ll d = (rr - rl + 1) * laz[rt];
    int m = (l + r) / 2;
    if (rr <= m) return d + query(rl, rr, l, m, lson);
    else if (m < rl) return d + query(rl, rr, m + 1, r, rson);
    else return d + query(rl, m, l, m, lson) + query(m + 1, rr, m + 1, r, rson);
}

int n, q, k, tp;
int sa[N], has[N], dp[N], tl[N], tr[N], ql[N], qr[N];
ll ans[N];
queue<int> Q[N];
vector<int> V[N];

int main() {
    //freopen("0.txt", "r", stdin);
    int a, b;
    scanf("%d%d%d", &n, &q, &k);
    for (int i = 1; i <= n; i++) {
        scanf("%d", sa + i);
        has[i] = sa[i];
    }
    sort(has + 1, has + n + 1);
    tp = unique(has + 1, has + n + 1) - has;
    for (int i = 1; i <= n; i++) sa[i] = lower_bound(has + 1, has + tp, sa[i]) - has;
    int ban = 0, d = 0;
    for (int i = 1; i <= n; i++) {
        Q[sa[i]].push(i);
        if (Q[sa[i]].size() > k) {
            ban = max(ban, Q[sa[i]].front());
            Q[sa[i]].pop();
        }
        if (Q[sa[i]].size() == k) {
            int id = Q[sa[i]].front();
            d = max(d, Q[sa[i]].front());
        }
        if (d > 0) {
            tl[i] = ban + 1, tr[i] = d;
        }
    }
    for (int i = 1; i <= q; i++) {
        scanf("%d%d", &ql[i], &qr[i]);
        V[qr[i]].push_back(i);
    }
    for (int i = 1; i <= n; i++) {
        if (tr[i]) insert(tl[i], tr[i], 1, n, 1);
        for (int id : V[i]) {
            ans[id] = query(ql[id], qr[id], 1, n, 1);
        }
    }
    for (int i = 1; i <= q; i++) printf("%lld\n", ans[i]);
    return 0;
}