题解：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

CPP

#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;
}

题解：P5673 「SWTR-2」Picking Gifts

文章操作

AC code

相关推荐

评论

题解：P5673 「SWTR-2」Picking Gifts