题解：P5673 「SWTR-2」Picking Gifts

· · 题解

当我们用树状数组维护且下标表示当前位置的贡献时，那么如果两组询问的右端点相同且 l_1 < l_2，则如果当前树状数组满足询问 [l_1,r] 的情形，那么则一定满足 [l_2,r] 的情形，因此可以考虑将询问离线并按右端点排序。

为了便于操作，并使树状数组上只保留每个出现的种类最多 k-1 个物品的价值，我们可以当右端点右移时先将新加的数加入树状数组，并统计出现次数，如果次数大于等于 k 则将最早出现的那个物品的价值删除。

至于如何找到这个物品，我们可以提前记录每种物品第 i 次出现的位置，这样每次只需要将第 t-k+1 个物品删除即可，t 表示这个物品出现的次数。

AC code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+5;
int n,m,k,c[N],p[N],v[N],vis[N];
vector<int> s[N];
struct str{int l,r,id;}q[N];
void add(int x,int y){for(;x<=n;x+=x&-x) c[x]+=y;}
int ask(int x){
    int y = 0;
    for(;x;x-=x&-x) y+=c[x];
    return y;
}
int ans[N];
bool cmp(str x,str y){return x.r<y.r;} 
signed main(){
    scanf("%lld%lld%lld",&n,&m,&k);
    for(int i = 1;i<=n;i++) scanf("%lld",&p[i]),s[p[i]].push_back(i);
    for(int i = 1;i<=n;i++) scanf("%lld",&v[i]);
    for(int i = 1;i<=m;i++){
        scanf("%lld%lld",&q[i].l,&q[i].r);
        q[i].id=i;
    }
    sort(q+1,q+1+m,cmp);
    int pos=1;
    for(int i = 1;i<=m;i++){
        while(pos<=q[i].r){
            vis[p[pos]]++;
            add(pos,v[pos]);
            if(vis[p[pos]]>=k){
                int tmp=s[p[pos]][vis[p[pos]]-k];
                add(tmp,-v[tmp]);
            }
            pos++;
        }
        ans[q[i].id]=ask(q[i].r)-ask(q[i].l-1);
    }
    for(int i = 1;i<=m;i++)
    printf("%lld\n",ans[i]);
    return 0;
}