题解 | #颜色与幸运数字#

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pi = pair<ll, ll>;
using ld = long double;
const int N = 1e6+ 10;
int mod = 1e9 + 7;
ll n,m;
ll a[N];
ll tree[N];
void add(int x, int val) {
    for(int i = x; i <= n; i += (i &(-i))) {
        tree[i] += val;
    }
}
ll query(int x) {
    ll ret = 0;
    for(int i = x; i; i -= (i & (-i))) ret += tree[i];
    return ret;
}
vector<int> g[N];
void solve()
{
    int k;
    cin >> n >> m >> k;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    vector<pi> qr[N];
    vector<ll> res(m+5, 0);
    for(int i = 1; i <= m; i++) {
        int l, r;
        cin >> l >> r;
        qr[r].push_back({l, i});
    }
    for(int i = 1; i <= n; i++) {
        g[a[i]].push_back(i);
        int len = g[a[i]].size();
        if(len >= k) {
            add(g[a[i]][len - k], a[i]);
            if(len > k) {
                add(g[a[i]][len - k - 1], -a[i]);
            }
            len--;
            if(len >= k) { // 把上一次a[i]出现k次的痕迹消掉
                add(g[a[i]][len - k], -a[i]);
                if(len > k) {
                    add(g[a[i]][len - k - 1], a[i]);
                }
            }
        }
        for(auto p: qr[i]) {
            res[p.second] = query(i) - query(p.first - 1);
        }
    }
    for(int i = 1; i <= m; i++) cout << res[i] <<'\n';
}
int main()
{
  // 请在此输入您的代码
    ios::sync_with_stdio(0);
    cin.tie(0);
    int _ = 1;
//     cin >> _;
    while(_--) solve();
}