题解：P5673 「SWTR-2」Picking Gifts
kind_Ygg
·
·
题解
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=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;
}
```
希望大家多点赞，这是蒟蒻的第一篇蓝题题解。