P5324 [BJOI2019]删数

听取大佬意见做BJOI2019

对于任意一个数列，如果能在有限次进行下列删数操作后将其删为空数列，则称这个数列可以删空。一次删数操作定义如下：

记当前数列长度为$k$ ，则删掉数列中所有等于$k$的数。

现有一个长度为 $n$ 的数列 $a$ ，有 $m$ 次修改操作，第 $i$ 次修改后你要回答：
经过 $i$ 次修改后的数列 $a$ ，至少还需要修改几个数才可删空？

每次修改操作为单点修改或数列整体加一或数列整体减一。

数据结构里的思维题233

首先我们考虑一次询问 $O(n^2)$ 因为这样是有3个点的

考虑dp, $dp[i]$ 表示满足长度为i的合法序列用的操作数是多少,一个序列是合法的当且仅当他能通过题目中的删除操作删光

那么

dp[i]=min_{j<i}(f[j]+max(0,(i-j)-num[i])

这个式子相当于如果i-j=k,k<num[i],我们就需要一些操作来填满这段区间

为什么他是对的呢?引出贪心~~猜结论~~

一个序列可以k次操作变得合法,当且仅当每个数在其值域上向左推倒后(即覆盖[i-num[i]+1,i])值域还剩下k个空余位置

证明:如果存在k个空白位置,那么一定存在k个重复覆盖的位置,把那些位置上的数修改到空白就可以了

所以根据这个贪心不难发现可以优化dp

数据结构!

用一颗在值域上的线段树,维护区间最小值,最小值出现次数,0的次数,加法标记

每次单点修改就对应某种数的推到所能覆盖大小的变化,询问就是0个数,整体移动就是线段树值域上"0"位置的移动,同时要把边界减去或者加上

具体看代码

code:

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define ll long long
const int MAXN=4e5+5e4+7;
namespace fastIO {
#define BUF_SIZE (1<<19)
	static char buf[BUF_SIZE],*p1=BUF_SIZE+buf,*pend=BUF_SIZE+buf;
	inline char nc() {
		if(p1==pend) {
			p1=buf;
			pend=buf+fread(buf,1,BUF_SIZE,stdin);
		}
		return *p1++;
	}
	inline int read() {
		int x=0,f=1;
		register char s=nc();
		for(; !isdigit(s); s=nc())if(s=='-')f=-1;
		for(; isdigit(s); s=nc())x=(x<<1)+(x<<3)+s-'0';
		return x*f;
	}
}
using namespace fastIO;
int k,n,m;
#define mid ((x+y)>>1)
#define ls (k<<1)
#define rs (k<<1|1)

struct Node {
	int mi,cnt,ans,ad;
} t[MAXN*15];
int a[MAXN],buc[MAXN];
int st,lim;
void pushup(int k) {
	t[k].mi=min(t[ls].mi,t[rs].mi);
	//min
	t[k].cnt=(t[ls].mi==t[k].mi?t[ls].cnt:0)+(t[rs].mi==t[k].mi?t[rs].cnt:0);
	//cnt是最小值出现次数
	t[k].ans=t[ls].ans+t[rs].ans;
	//ans是0的sum
	//向上合并
}
void tag(int x,int c) {
	t[x].mi+=c;
	//最小值区间加
	t[x].ans=(t[x].mi==0)?t[x].cnt:0;
	//如果有0,就统计一下答案,维护0的次数吗
	t[x].ad+=c;
	// ad是加法标记
}

void pushdown(int k) {
	if(t[k].ad) {
		tag(ls,t[k].ad);
		tag(rs,t[k].ad);
		t[k].ad=0;
	}
}

void built(int k,int x,int y) {
	if(x==y) {
		t[k].cnt=1;
		t[k].ans=1;//一开始都是0
		return ;
	}
	built(ls,x,mid);
	built(rs,mid+1,y);
	pushup(k);
}

void update(int k,int x,int y,int l,int r,int c) {
	if(x>=l&&y<=r) {
		tag(k,c);
		return ;
	}
	pushdown(k);
	if(l<=mid)update(ls,x,mid,l,r,c);
	if(mid<r)update(rs,mid+1,y,l,r,c);
	pushup(k);
}

inline int query(int k,int x,int y,int l,int r) {
	if(x>=l&&y<=r) {
		return t[k].ans;
	}
	pushdown(k);
	if(r<=mid)return query(ls,x,mid,l,r);
	if(mid<l)return query(rs,mid+1,y,l,r);
	return query(ls,x,mid,l,r)+query(rs,mid+1,y,l,r);
}

void chan(int x,int c) {
	int k=x-buc[x]+1-(c>0);//算出推倒后区间左端点 
	update(1,1,lim,k,k,c);//扩展一下 
	buc[x]+=c;//加上这数量
}

int main() {
	//freopen("test.in","r",stdin);
	n=read();
	m=read();
	st=1e5+5e4+2,lim=450000+7;
	built(1,1,lim);
	for(register int i=1; i<=n; ++i) {
		a[i]=read();
		a[i]+=st;//平移
		chan(a[i],1);
		//	printf("%d?\n",a[i]);
	}
	int p,x;
	while(m--) {
		p=read();
		x=read();
		if(p>0) {
			if(a[p]<=st+n) {//单点修
				chan(a[p],-1);
			} else {//判断<=st+n?st是basic
				--buc[a[p]];
				//能用的货又少一个/kk
			}
			a[p]=st+x;
			if(a[p]<=st+n) {
				chan(a[p],1);
			} else {
				++buc[a[p]];//又多一个w
			}
		} else if(x>0) {
			int pos=st+n;
			//直接移动基准
			if(buc[pos])update(1,1,lim,pos-buc[pos]+1,pos,-1);
			//如果在哪个位置有数,那么他们都累赘了,清了吧
			--st;
		} else {
			++st;
			int pos=st+n;
			if(buc[pos])update(1,1,lim,pos-buc[pos]+1,pos,1);//他们生效了
		}
		printf("%d\n",query(1,1,lim,st+1,st+n));//所有0就是自闭
	}
	return 0;
}

夏晓光(loveJY)的博客

数据结构!

P1399 [NOI2013]快餐店