题解：P5673 「SWTR-2」Picking Gifts

fush · 2024-12-04 15:40:47 · 题解

我们先看一道弱化版：P1972。

在 P1972 中，我们将询问离线，每个颜色当前的最后一位才有贡献。

在这道题，我们每个颜色有了不同的贡献，从保留一位变成保留 k 个。

我们先对当前位置单点加。
如果超出 k 个，就把最前面的数减去。
答案就是当前的区间和。

用树状数组做单点修改、区间查询，用 vector 访问前面的数。

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
#define FL(a, b, c) for(int a = (b), a##end = (c); a <= a##end; a++)
#define FR(a, b, c) for(int a = (b), a##end = (c); a >= a##end; a--)
#define lowbit(x) ((x) & -(x))
constexpr int N = 1e6 + 10;
int w[N], n, p[N], v[N], vis[N], ans[N];
vector<int>d[N];
void add(int x, int v){while(x <= n)w[x] += v, x += lowbit(x);}
int query(int l, int r, int ans = 0){
    while(r > l)ans += w[r], r -= lowbit(r);
    while(l > r)ans -= w[l], l -= lowbit(l);
    return ans;
}
struct A{int l, r, id;}c[N];
int32_t main(){
    cin.tie(0)->sync_with_stdio(0);
    int q, k;
    cin >> n >> q >> k;
    FL(i, 1, n)cin >> p[i], d[p[i]].emplace_back(i);
    FL(i, 1, n)cin >> v[i];
    FL(i, 1, q)cin >> c[i].l >> c[i].r, c[i].id = i;
    sort(c + 1, c + 1 + q, [](A&i, A&j){return i.r < j.r;});
    int j = 1, z;
    FL(i, 1, n){
        vis[p[i]]++, add(i, v[i]);
        if(vis[p[i]] >= k){
            z = d[p[i]][vis[p[i]] - k];
            add(z, -v[z]);
        }
        while(c[j].r == i)
        ans[c[j].id] = query(c[j].l - 1, c[j].r), j++;
        if(j > q)break;
    }
    FL(i, 1, q)
    cout << ans[i] << endl;
    return 0;
}