自动搬运

查看原文

来自洛谷，原作者为

	kind_Ygg 这个家伙很懒，什么也没有留下

搬运于2025-08-24 22:13:14，当前版本为作者最后更新于2024-08-12 15:39:25，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P5673 「SWTR-2」Picking Gifts 题解

声明：在写代码前未看题解。
这是一道单点修改和区间查询的树状数组好题，跟 P1972 十分相似（Alex_Wei 已指出），所以我们先去看一下 那题。
大意为：给定1个长度为 $n$ 序列 $a$，并给定 $q$ 个询问。对于每个询问给定 $l$ 和 $r$，求区间 $[l,r]$ 中有多少个不同的数。
嗯，一眼就可以看出用树状数组做。但具体怎么做呢，我们来手打一个样例：

2 3 2 5 2 1

可以发现，对于每个 $r$ 为 $3$ 的区间,下标为 $1$ 的那个 $2$ 就显得有些多余了。$r$ 为 $5$ 时同理，前面的两个 $2$ 也就多余了。那么我们就可以将 $r$ 从小到大排序（$l$ 先后次序不管）。来照样例模拟一下试试（初始化全部为 $0$）。
$i=1$：1 0 0 0 0 0//2第一次出现。
$i=2$：1 1 0 0 0 0//3第一次出现。
$i=3$：0 1 1 0 0 0//2第二次出现，将前面一个2更改为0。
$i=4$：0 1 1 1 0 0//5第一次出现。
$i=5$：0 1 0 1 1 0//2第三次出现，将前面一个2更改为0。
$i=6$：0 1 0 1 1 1//1第一次出现。
假设求区间 $[2,5]$，那么就在 $i=5$ 的时候求 $sum(5)-sum(2-1)$。

Code

#include<bits/stdc++.h>
#define int long long 
#define lowbit(x) (x&-x)
#define rank kkk
using namespace std;
const int N=1e6+5;
int n,q;
int a[N],v[N];
int tree[N];
int c[N];
int now[N];//now[i]存储数前一个i最后出现的位置
void update(int x,int k){
	while(x<=n){
		tree[x]+=k;
		x+=lowbit(x);
	}
}
int sum(int x){
	int ans=0;
	while(x){
		ans+=tree[x];
		x-=lowbit(x);
	}
	return ans;
}
struct node{
	int l,r,id;
}qus[N];
int ans[N];
bool cmp(node a,node b){
	return a.r<b.r;
}
bool cmp2(node a,node b){
	return a.id<b.id;
}
signed main()
{
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		v[i]=a[i];
	}
	sort(v+1,v+n+1);
	int k=unique(v+1,v+n+1)-v-1;
	for(int i=1;i<=n;i++)
		a[i]=lower_bound(v+1,v+k+1,a[i])-v;
	cin>>q;
	for(int i=1;i<=q;i++)
		cin>>qus[i].l>>qus[i].r,qus[i].id=i;
	sort(qus+1,qus+q+1,cmp);
	int qe=1;
	for(int i=1;i<=q;i++){//枚举question
		for(;qe<=qus[i].r;qe++){//枚举
			if(now[a[qe]])
				update(now[a[qe]],-1)/*,c[now[a[qe]]]--*/;
			update(qe,1);
			now[a[qe]]=qe;
			/*c[qe]++;*/
		}
		ans[qus[i].id]=sum(qus[i].r)-sum(qus[i].l-1);
//		for(int i=1;i<=n;i++)
//			cout<<c[i]<<" ";
//		cout<<'\n';
	}
	for(int i=1;i<=q;i++)
		cout<<ans[i]<<'\n';
	return 0;
}

回归正题，来看看两道题的差距：

1. 从只保留 $1$ 个变为保留 $k$ 个（顺序还是从右往左）。
2. 增添了价值（也就是价值从 $1$ 变为 $v_i$）。

第二个还是很好处理的，重点是第一个。之前可以用 $now_i$ 来存储种类为 $i$ 的物品的之前的位置，然后再将 $now_i$ 更改为目前位置。那现在怎么处理呢，不妨我们用 vector 存种类为 $i$ 的物品的各个位置。

vector<int> now[N];//种类i的物品出现的各个位置

再开一个 $vis$ 数组存当前种类为 $i$ 的物品出现的次数，那 update 就变成了这样：

int num=now[a[e].p][vis[a[e].p]-k];//a[e].p就为题目中的p[i]
update(e,a[e].v);
update(num,-a[num].v);

Code

#include<bits/stdc++.h>
#define int long long 
#define lowbit(x) (x&-x)
using namespace std;
const int N=1e6+5;
struct node{
	int p,v;
}a[N];
int pp[N];
struct node2{
	int l,r,id;
}qu[N];
bool cmp(node2 a,node2 b){
	return a.r<b.r;
}
int n,m,k,tree[N];
int ans[N];//答案
int vis[N]={0};//来记录当前种类i出现的次数
vector<int> now[N];//种类i的物品出现的各个位置
void update(int x,int k){
	while(x<=n){
		tree[x]+=k;
		x+=lowbit(x);
	}
}
int sum(int x){
	int ans=0;
	while(x){
		ans+=tree[x];
		x-=lowbit(x);
	}
	return ans;
}
signed main(){
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++){
		cin>>a[i].p;
		pp[i]=a[i].p;
	}
	for(int i=1;i<=n;i++)
		cin>>a[i].v;
	sort(pp+1,pp+n+1);
	int vs=unique(pp+1,pp+n+1)-pp-1;
	for(int i=1;i<=n;i++){
		a[i].p=lower_bound(pp+1,pp+vs+1,a[i].p)-pp;
		now[a[i].p].push_back(i);
	}
	//离散化（可有可无）
	for(int i=1;i<=m;i++){
		cin>>qu[i].l>>qu[i].r;
		qu[i].id=i;
	}
	sort(qu+1,qu+m+1,cmp);
	int e=1;
	for(int i=1;i<=m;i++){
		for(;e<=qu[i].r;e++){
			vis[a[e].p]++;
			if(vis[a[e].p]<k)
				update(e,a[e].v);
			else{
				int num=now[a[e].p][vis[a[e].p]-k];
				update(e,a[e].v);
				update(num,-a[num].v);
			}
		}
		ans[qu[i].id]=sum(qu[i].r)-sum(qu[i].l-1);
	}
	for(int i=1;i<=m;i++)
		cout<<ans[i]<<'\n';
	return 0;
}

希望大家多点赞，这是蒟蒻的第一篇蓝题题解。