CF1705E Mark and Professor Koro 题解
Chancylaser
·
·
题解
此篇题解既作为题目总结，也作为我对线段树二分的梳理。
首先，我们先把一开始读入的数组进行题目所描述的，能合并就尽量合并。这样的话，容易发现处理后的数组中每个数字出现的次数不大于 1 次。我们把一开始的数组设为 a 数组，把处理后的数组设为 cnt 数组。
然后我们考虑修改操作，每次修改的实质是删除一个数，再添加一个数。我们设删除的数为 del，添加的数为 l。
我们首先先删除 del，分为两种情况。
$2.$ 在目前的 $cnt$ 数组中，出现了 $0$ 次。因为题目所给出的删除一定是合法的，所以在原数组中 $del$ 一定是合并到比它大的数里去了。所以我们找出 $del$ 后第一个 $cnt[res]$ 为 $1$ 的 $res$，并把 $del \sim res-1$ 的 $cnt$ 值全部赋值为 $1$ 即可，同时把 $res$ 位置的 $cnt$ 值赋值为 $0$。
**我们再添加 $l$，同理分为两种情况**。
$1.$ 在目前的 $cnt$ 数组中，出现了 $0$ 次。这种情况下，容易发现直接在 $cnt[del]$ 处赋值为 $1$ 即可。因为即使我们添加这个数，也不会对其它的合并有影响。
$2.$ 在目前的 $cnt$ 数组中，出现了 $1$ 次。这时候我们找出 $del$ 后第一个 $cnt[res]$ 为 $0$ 的 $res$，显然 $del \sim res-1$ 都可以一直合并，直到 $res$，所以将 $del \sim res-1$ 全部赋值为 $0$，同时把 $res$ 位置的 $cnt$ 值赋值为 $1$。
**查询答案的时候**，只要找出最大的 $res$，使得 $cnt[res]=1$ 即可。
----------------------
此时我们如果暴力覆盖，设 $M$ 为最大可能合并到的数字，时间复杂度则是 $O(Mq)$，$q$ 的意义同题面，此时无法通过此题。
发现可以使用线段树来维护 $cnt$ 数组，此时有两种实现方式，主要是对于上面 $res$ 的寻找方式不同，时间复杂度也不同，但均能通过此题。
$1.$ 二分套线段树，发现 $cnt$ 数组的前缀和满足单调性，所以可以使用二分查找到我们需要的 $res$，每次查询 $1$ 到目前 $res$ 的 $1$（或者是 $0$）的个数。时间复杂度 $O(q\log^2 M)$。
$2.$ 线段树二分，注意这与 $1.$ 做法并不相同。我们发现线段树本身就有二分的性质，所以快速从根节点往下跳找到我们需要的 $res$。由于默认读者会此技巧，这里便不再详细赘述。如果读者不详知此技巧，请选择更简单的线段树二分题目来进行练习，再来做此题会更加便利。此时间复杂度为 $O(q \log M)$。
------------
这里我给出第二种实现方式的全部代码。我认为写得还是比较通俗易懂的，另外，我代码里的 $dl$ 即是上面所说的 $del$，其余的思路完全符合上面的讲述。
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=4e5+5,MAX=4e5;
int n,q;
int a[N],sum[N];
struct qwq{
int l,r,sum;
int fg;
qwq(){
l=r=sum=0;
fg=N;
}
void fugai(int k){
sum=(r-l+1)*k;
fg=k;
}
}t[N<<2];
void pushup(int p){
t[p].sum=t[p<<1].sum+t[p<<1|1].sum;
}
void pushdown(int p){
if(t[p].fg!=N){
t[p<<1].fugai(t[p].fg);
t[p<<1|1].fugai(t[p].fg);
t[p].fg=N;
}
}
void build(int p,int l,int r){
t[p].l=l; t[p].r=r;
if(l==r){
t[p].sum=sum[l];
return;
}
int mid=(l+r)>>1;
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
pushup(p);
}
void copy(int p,int l,int r,int val){
if(t[p].l>=l && t[p].r<=r){
t[p].fugai(val);
return;
}
pushdown(p);
int mid=(t[p].l+t[p].r)>>1;
if(l<=mid) copy(p<<1,l,r,val);
if(r>mid) copy(p<<1|1,l,r,val);
pushup(p);
}
int getsum(int p,int l,int r){
if(t[p].l>=l && t[p].r<=r) return t[p].sum;
pushdown(p);
int mid=(t[p].l+t[p].r)>>1;
int ans=0;
if(l<=mid) ans+=getsum(p<<1,l,r);
if(r>mid) ans+=getsum(p<<1|1,l,r);
return ans;
}
int getpos(int p,int k){
if(t[p].l==t[p].r) return t[p].l;
pushdown(p);
int nw=t[p<<1].sum;
if(nw>=k) return getpos(p<<1,k);
else return getpos(p<<1|1,k-nw);
}
int getpos2(int p,int k){
if(t[p].l==t[p].r) return t[p].l;
pushdown(p);
int nw=(t[p<<1].r-t[p<<1].l+1) - t[p<<1].sum;
if(nw>=k) return getpos2(p<<1,k);
else return getpos2(p<<1|1,k-nw);
}
int getmax(int p){
if(t[p].l==t[p].r) return t[p].l;
pushdown(p);
if(t[p<<1|1].sum) return getmax(p<<1|1);
else return getmax(p<<1);
}
int main(){
scanf("%d%d",&n,&q);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
sum[a[i]]++;
}
for(int i=1;i<=MAX;i++){
sum[i+1]+=sum[i]/2;
sum[i]%=2;
}
build(1,1,MAX);
int k,l;
for(int i=1;i<=q;i++){
scanf("%d%d",&k,&l);
int dl=a[k],lsum=0;
int res;
a[k]=l;
if(getsum(1,dl,dl)) copy(1,dl,dl,0);
else{
lsum=getsum(1,1,dl);
res=getpos(1,lsum+1);
copy(1,dl,res-1,1);
copy(1,res,res,0);
}
if(!getsum(1,l,l)) copy(1,l,l,1);
else{
lsum=l-getsum(1,1,l);
res=getpos2(1,lsum+1);
copy(1,l,res-1,0);
copy(1,res,res,1);
}
printf("%d\n",getmax(1));
}
return 0;
}
```