【题解】[BJOI2019]删数

Problem

\(\text{Solution:}\)

记 \(cnt_x\) 表示数 \(x\) 的出现次数。

那么,一个数 \(x\) 能删去的范围应该是: \([x-cnt_x+1,x].\)

考虑一个序列能被删去,当且仅当它的范围被完全覆盖到。

所以最小修改次数就是 没有被覆盖的区间的长度 。

那么我们可以把每一个数抽象成一条线段,进行区间加减 \(1\) 以及求区间 \(0\) 的个数即可。

考虑一个数 \(x\) 大于数列的长度会发生什么。

它覆盖的区间 \([x-cnt_x+1,x]\) 实际上由于 \(x\) 本身大于 \(len\) ,它是无法被删掉的。

所以我们需要动态加入维护线段。

这个时候我们注意到全局修改操作的特性:相当于全体值域平移一个单位。

值域不好做,我们可以将询问区间进行反向平移。为了避免出现负数,开始的时候就向右平移 \(\max \left\{n,m\right\}\) 个单位即可。

平移后,对应的值也改变,我们需要记录一个 \(\Delta\) 来表示值域的位移程度,后续修改的时候需要根据 \(\Delta\) 来修改对应的值 \(x\) 来保证修改的值是对的。

这样,原本看似是全局询问的题目*变成了一道区间询问。

这个东西:维护大于等于 \(1\) 的数的个数,看着很像扫描线对吧。我们维护值域被覆盖的次数以及被覆盖的长度即可。

但是因为这题是区间查询而不是全局,所以这样维护的信息是有冗余的,是错误的。

考虑另一种做法,扫描线题解中也提到过:维护区间最小值以及它的出现次数。

这样,如果最小值是 \(0\) 我们查询的就是区间长度减去最小值个数,否则返回区间长度。

实际上是变相维护了一个区间 \(0\) 的个数。

而区间最小值个数是很好维护的。也可以满足区间查询的要求。

于是这个题就在 \(O(n\log n)\) 的时间复杂度下解决了。

代码实现细节很多。

平移询问的时候需要动态加入或删除不需要的线段,但左端点不用管。因为每一个值的线段区间是向左延伸的。

单点修改的时候也要注意修改的值是不是超过的查询区间右端点。、

平移询问加入线段的时候也要注意这个右端点的值是不是出现过,只有出现过才是有意义的,否则修改区间 \([queryR+1,queryR]\) 会出现错误。

代码思维难度和实现难度均较大。

#include<bits/stdc++.h>
using namespace std;
const int MAXN=9e5+10;
int ls[MAXN],rs[MAXN],rt;
int L[MAXN],R[MAXN],node;
int cnt[MAXN],a[MAXN];
int n,m,tag,vis[MAXN];
int ct[MAXN],tg[MAXN];
int minn[MAXN];
int ql,qr,dt;
inline int read(){
	int s=0,w=1;
	char ch=getchar();
	while(!isdigit(ch)){
		if(ch=='-')w=-1;
		ch=getchar();
	}
	while(isdigit(ch)){
		s=s*10-48+ch;
		ch=getchar();
	}
	return s*w;
}
inline int Min(int x,int y){return x<y?x:y;}
inline void pushup(int x){
	minn[x]=Min(minn[ls[x]],minn[rs[x]]);
	if(minn[ls[x]]<minn[rs[x]])ct[x]=ct[ls[x]];
	else if(minn[ls[x]]>minn[rs[x]])ct[x]=ct[rs[x]];
	else ct[x]=ct[ls[x]]+ct[rs[x]];
}
inline void pushdown(int x){
	if(tg[x]){
		int &p=tg[x];
		tg[ls[x]]+=p;
		tg[rs[x]]+=p;
		minn[ls[x]]+=p;
		minn[rs[x]]+=p;
		p=0;
	}
}
void build(int &x,int l,int r){
	x=++node;
	L[x]=l;R[x]=r;
	if(l==r){ct[x]=1;return;}
	int mid=(l+r)>>1;
	build(ls[x],l,mid);
	build(rs[x],mid+1,r);
	pushup(x);
}
void change(int x,int l,int r,int v){
	if(L[x]>=l&&R[x]<=r){
		minn[x]+=v;
		tg[x]+=v;
		return;
	}
	pushdown(x);
	int mid=(L[x]+R[x])>>1;
	if(l<=mid)change(ls[x],l,r,v);
	if(mid<r)change(rs[x],l,r,v);
	pushup(x);
}
int query(int x,int l,int r){
	if(L[x]>=l&&R[x]<=r){
		if(minn[x]!=0)return R[x]-L[x]+1;
		else return R[x]-L[x]+1-ct[x];
	}
	pushdown(x);
	int mid=(L[x]+R[x])>>1;
	int val=0;
	if(l<=mid)val=query(ls[x],l,r);
	if(mid<r)val+=query(rs[x],l,r);
	pushup(x);
	return val;
}
inline int Max(int x,int y){return x>y?x:y;}
int main(){
	n=read(),m=read();tag=Max(n,m);ql=tag+1,qr=tag+n;
	for(int i=1;i<=n;++i)scanf("%d",&a[i]),cnt[a[i]+tag]++,vis[a[i]+tag]=1;
	build(rt,1,tag+tag+tag);
	for(int i=1;i<=n;++i){
		if(!vis[a[i]+tag])continue;
		vis[a[i]+tag]=0;
		int lpos=a[i]+tag-cnt[a[i]+tag]+1;
		int rpos=a[i]+tag;
		change(rt,lpos,rpos,1);
	}
	for(int i=1;i<=m;++i){
		int p,x;
		scanf("%d%d",&p,&x);
		if(p>0){
			x-=dt;
			int val=a[p]+tag;
			a[p]=x;
			int pos=val-cnt[val]+1;
			cnt[val]--;
			if(val<=qr)change(rt,pos,pos,-1);
			cnt[x+tag]++;
			pos=x+tag-cnt[x+tag]+1;
			if(x+tag<=qr)change(rt,pos,pos,1);
			int ans=query(rt,ql,qr);
			printf("%d\n",n-ans);
		}
		else{
			dt+=x;
			if(x<0){
				qr++;ql++;
				int lpos=qr-cnt[qr]+1;
				int rpos=qr;
				if(cnt[qr]>0)change(rt,lpos,rpos,1);
			}
			else{
				int lpos=qr-cnt[qr]+1;
				int rpos=qr;
				if(cnt[qr]>0)change(rt,lpos,rpos,-1);
				qr--;ql--;
			}
			int ans=query(rt,ql,qr);
			printf("%d\n",n-ans);
		}
	}
	return 0;
}
上一篇:DBUtils笔录


下一篇:【zbar源码分析】确定探测图形中心点数量