自动搬运

查看原文

来自洛谷，原作者为

	concert_B 情绪困雨天

搬运于2025-08-24 23:15:55，当前版本为作者最后更新于2025-07-17 16:23:08，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

P12485 [集训队互测 2024] PM 大师题解

tip

date:2025/7/17,DAY11

本题是模拟赛 T4，Clonoth 也是直接把他集训队的题搬来了，不过神奇的是题解就一篇，提交人数达惊人的 $10$ 个入。

本人迫不得已只能把官方题解改了一下搬来了。思路不是我的，希望 Clonoth 不会发现。

本题其实难在思考过程，如果真弄懂了代码其实不难，树状数组和线段树都比较板（特指黑题），但真的好难理解啊啊啊。存好大脑，开始了。

以下认为 $n,q$ 同阶。

做法 $1$

考虑 $O(n)$ 地由 $a$ 生成出 $b$。

按照 $i=1,2,\ldots,n$ 遍历数组 $a$，同时维护 $vis_i$ 表示 $i$ 是否已经在 $b$ 中出现过。当 $a_i\ne 0$ 时，$vis_i \gets \text{true}$ ；当 $a_i=0$ 时，$b_i$ 初始设置为上一个 $a_p=0$ 位置的 $b_p$，然后使 $b_i \gets b_i + 1$ 直到 $vis_{b_i} = \text{false}$ 。

时间复杂度 $O(n^2)$，可以通过子任务 $1$。

code

蒟蒻的考场代码。

while(q--){
	cin>>x>>k>>y; 
	a[x]=k;
	if(a[y]!=0){
		cout<<a[y]<<'\n';
		continue;
	}
	for(int j=1;j<=n;j++)
		fa[j]=j;
	for(int j=1;j<=n;j++){
		if(a[j]==-1)	continue;
		if(a[j]==0){
			int b=find(1);
			if(j==y){
				cout<<b<<'\n';
				break;
			}
			fa[find(b)]=find(b+1);
			continue;
		}
		fa[find(a[j])]=find(a[j]+1);
	}
}

并查集的作用就是 vis，已经出现过的和 $1$ 合并，暴力的比 $O(n^2)$ 优美一点悲。

做法 $2$

考虑解决子任务 $2$。

注意到存在集合 $S\subseteq \{1,2,…,n\}$ 满足对于 $a_i$ 中的第 $i$ 个 $a_x=0$，满足 $b_x$ 等于 $S$ 中的第 $i$ 小的数。

此时 $x \in S$ 等价于不存在 $a_i=x$。

使用树状数组或平衡树等数据结构维护插入、删除、求 $k$ 小值即可。 时间复杂度 $O(n \log n)$，可以通过子任务 $2$。

code

来自 HZ 巨佬的代码 orz：

void add(int x,int k){
	for(int i=x;i<=n;i+=i&-i)
		tr[i]+=k;
	return;
}
int qry(int x) {
	int res=0;
	while(x){
		res+=tr[x];
		x-=x&-x;
	}
	return res;
}
int K=n+1;
for(int i=1;i<=n;i++)
	if(a[i]==0){
		K=i;
		break;
	}
for(int i=1;i<=q;i++){
	if(a[x[i]]!=-1){
		cnt[a[x[i]]]--;
		if(!cnt[a[x[i]]])
			add(a[x[i]],-1);
	}
	if(k[i]!=-1){
		if(!cnt[k[i]])
			add(k[i],1);
		cnt[k[i]]++;
	}
	a[x[i]]=k[i];
	if(y[i]<K)	cout<<a[y[i]]<<'\n';
	else{
		int l=1,r=n;
		while(l<r){
			int mid=(l+r)>>1;
			if (mid-qry(mid)<y[i]-K+1)	l=mid+1;
			else	r=mid;
		}
		cout<<l<<'\n';
	}
}

做法 $3$

考虑解决子任务 $5$。 首先此时原问题等价于在初始全为 $0$ 的序列 $a$ 中任意插入正数。

不难注意到，满足做法 $2$ 中所述性质的集合 $S$ 在一般的情况下也存在，这启发我们动态的维护 $S$ 而不是数组 $b$。

以下我们假设 $a$ 中的正数互不相同，若存在相同仅保留第一个即可（标程的堆中 update 操作的意义）。由此，定义 $pos_i$ 表示 $i$ 出现的位置。

在任何时刻，对于 $a_i$，$a_i \notin S$ 等价于 $i$ 之前最近的 $a_p=0$ 的 $b_p<a_i$。因此，只要维护了集合 $S$，在一次 $a_x \gets k$ 的修改操作中，可以轻易得到是否需要将 $k$ 从 $S$ 中删除。

但在一次修改操作中，可能会引起需要往 $S$ 中加入一些数（由将 $k$ 从 $S$ 中删除所引起的 $b$ 的改变）。对于 $j \notin S$ 定义 $f_i=\sum_{x \in S} [x \le j]-c_{pos_j}$，其中 $c_i$ 表示 $a$ 数组中 $a_i$ 之前有多少个 $0$。容易发现 $j \notin S$ 时 $f_j \ge 0$；而一旦出现 $f_j < 0$ 则需要将 $j$ 加入到 $S$ 中。

那么每次修改对 $f_j$ 的修改即为从 $k$ 开始的一段前缀减 $1$，直到出现 $f_j=0$ 为止。 使用线段树维护 $f_j$，时间复杂度 $O(n\log n)$，可以通过子任务 $1,5$。

tip

文中 $pos$ 可以用堆维护，$f$ 可以用线段树维护，维护插入、删除、求 $k$ 小值与做法 $2$ 类似，标程用树状数组。

code

inline void insert_check(int x){
	int k=a[x];
	if(pos[k].top()!=x)
		return;
	int u=b.kth(pre[x]);
	if(u<k){
		if(!in[k]){
			if(k<n){
				int i=f.find(1,1,n,k+1,n);
				if(i){
					f.modify(1,1,n,i,inf);
					g.modify(1,1,n,i,0);
					b.add(i,1);
					in[i]=false;
					++X;
				}
				else
					i=n+1;
				if(i<=n)
					Sum+=i-k;	
				if(k+1<i)
					g.update(1,1,n,k+1,i-1,1);
			}
			b.add(k,-1);
			in[k]=1;
		}
		f.modify(1,1,n,k,b.ask(k)-pre[x]);
		g.modify(1,1,n,k,inf);
	}
	else{
		g.modify(1,1,n,k,pre[x]-b.ask(k));
		f.modify(1,1,n,k,inf);
	}
	return;
}

inline void insert(int x,int k){
	a[x]=k;
	if(k==-1)
		return;
	pos[k].insert(x);
	insert_check(x);
	return;
}

做法 $4$

首先原问题等价于在初始全为 $0$ 的序列 $a$ 中任意插入或删除正的数。

注意到在做法 $3$ 中，每次操作对 $S$ 的改变都是 $O(1)$ 的，这启发我们使用类似的方式处理删除操作。

对称的，对于 $j \in S$ 定义 $g_i=c_{pos_j}-\sum_{}x \in S [x \le j]$。此时也有 $j \in S$ 时 $g_j>0$；而一旦出现 $g_j<0$ 则需要将 $j$ 从 $S$ 中删除。

修改的形式也是类似的。但值得注意的是，在对 $f_j$（或 $g_j$）执行从 $k$ 开始的一段前缀减 $1$ 操作时，也需要在 $f_j$（或 $g_j$）中对这一段区间进行加 $1$ 的操作。

使用线段树维护 $f_j,g_j$，时间复杂度 $O(n \log n)$，可以通过所有子任务。

code

inline void erase(int x){
	int k=a[x];
	if(k==-1)
		return;
	pos[k].erase(x);
	if(!pos[k].empty()&&pos[k].top()<x)
		return;
	if(in[k]){
		if(k<n){
			int i=g.find(1,1,n,k+1,n);
			if(i){
				f.modify(1,1,n,i,0);
				g.modify(1,1,n,i,inf);
				b.add(i,-1);
				in[i]=true;
				++Y;
			}
			else
				i=n+1;
			if(i<=n)
				Sum+=i-k;
			if(k+1<i)
				f.update(1,1,n,k+1,i-1,1);
		}
		in[k]=false;
		b.add(k,1);
	}
	f.modify(1,1,n,k,inf);
	g.modify(1,1,n,k,inf);
	if(!pos[k].empty())
		insert_check(pos[k].top());
	return;
}

重构过的代码

封装好了，有需自取。

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10,inf=1e9;
int n,m;
int a[N],pre[N];
bool in[N];

struct heap{
	priority_queue<int,vector<int>,greater<int>> p,q;
	inline void insert(int x){
		p.push(x);
		return;
	}
	inline void erase(int x){
		q.push(x);
		return;
	}
	inline void update(){
		while(!p.empty()&&!q.empty()&&p.top()==q.top())
			p.pop(),q.pop();
		return;
	}
	inline bool empty(){
		update();
		return p.empty();
	}
	inline int top(){
		update();
		return p.top();
	}
	inline void clear(){
		while(!p.empty())
			p.pop();
		while(!q.empty())
			q.pop();
		return;
	}
}pos[N];

struct BIT{
	int bit[N];
	inline int lowbit(int x){
		return x&-x;
	}
	inline void add(int x,int k){
		for(int i=x;i<=n;i+=lowbit(i))
			bit[i]+=k;
		return;
	}
	inline int ask(int x){
		int ans=0;
		for(int i=x;i;i-=lowbit(i))
			ans+=bit[i];
		return ans;
	}
	inline int kth(int k){
		if(!k)	return 0;
		int i=0,s=0;
		for(int w=log2(n);w!=-1;--w){
			int j=i+(1<<w);
			if(j<=n&&s+bit[j]<k)
				s+=bit[j],i=j;
		}
		return i+1;
	}
}b;

struct segment_tree{
	static const int Size=(1<<21)+10;
	int sum[Size],tag[Size];
	inline void push_up(int p){
		sum[p]=min(sum[p<<1],sum[p<<1|1]);
		return;
	}
	inline void push_down(int p){
		if(tag[p]){
			sum[p<<1]+=tag[p];
			sum[p<<1|1]+=tag[p];
			tag[p<<1]+=tag[p];
			tag[p<<1|1]+=tag[p];
			tag[p]=0;
		}
		return;
	}
	int find(int p,int l,int r,int x,int y){
		if(r<x||l>y)	return 0;
		if(x<=l&&r<=y&&sum[p]){
			sum[p]--;
			tag[p]--;
			return 0;
		}
		if(l==r)	return l;
		push_down(p);
		int mid=l+r>>1;
		int ans=0;
		ans+=find(p<<1,l,mid,x,y);
		if(ans)	return ans;
		ans+=find(p<<1|1,mid+1,r,x,y);
		return ans;
	}
	void update(int p,int l,int r,int x,int y,int k){
		if(l>y||r<x)	return;
		if(x<=l&&r<=y){
			sum[p]+=k;
			tag[p]+=k;
			return;
		}
		push_down(p);
		int mid=l+r>>1;
		update(p<<1,l,mid,x,y,k);
		update(p<<1|1,mid+1,r,x,y,k);
		push_up(p);
		return;
	}
	void modify(int p,int l,int r,int x,int k){
		if(r<x||l>x)	return;
		if(l==r){
			sum[p]=k;
			return;
		}
		push_down(p);
		int mid=l+r>>1;
		modify(p<<1,l,mid,x,k);
		modify(p<<1|1,mid+1,r,x,k);
		push_up(p);
		return;
	}
	void build(int p,int l,int r){
		tag[p]=0;
		if(l==r){
			sum[p]=inf;
			return;
		}
		int mid=l+r>>1;
		build(p<<1,l,mid);
		build(p<<1|1,mid+1,r);
		push_up(p);
		return;
	}
}f,g;
int X,Y;
long long Sum=0;

inline void insert_check(int x){
	int k=a[x];
	if(pos[k].top()!=x)
		return;
	int u=b.kth(pre[x]);
	if(u<k){
		if(!in[k]){
			if(k<n){
				int i=f.find(1,1,n,k+1,n);
				if(i){
					f.modify(1,1,n,i,inf);
					g.modify(1,1,n,i,0);
					b.add(i,1);
					in[i]=0;
					++X;
				}
				else
					i=n+1;
				if(i<=n)
					Sum+=i-k;	
				if(k+1<i)
					g.update(1,1,n,k+1,i-1,1);
			}
			b.add(k,-1);
			in[k]=1;
		}
		f.modify(1,1,n,k,b.ask(k)-pre[x]);
		g.modify(1,1,n,k,inf);
	}
	else{
		g.modify(1,1,n,k,pre[x]-b.ask(k));
		f.modify(1,1,n,k,inf);
	}
	return;
}

inline void insert(int x,int k){
	a[x]=k;
	if(k==-1)
		return;
	pos[k].insert(x);
	insert_check(x);
	return;
}

inline void erase(int x){
	int k=a[x];
	if(k==-1)
		return;
	pos[k].erase(x);
	if(!pos[k].empty()&&pos[k].top()<x)
		return;
	if(in[k]){
		if(k<n){
			int i=g.find(1,1,n,k+1,n);
			if(i){
				f.modify(1,1,n,i,0);
				g.modify(1,1,n,i,inf);
				b.add(i,-1);
				in[i]=1;
				++Y;
			}
			else
				i=n+1;
			if(i<=n)
				Sum+=i-k;
			if(k+1<i)
				f.update(1,1,n,k+1,i-1,1);
		}
		in[k]=0;
		b.add(k,1);
	}
	f.modify(1,1,n,k,inf);
	g.modify(1,1,n,k,inf);
	if(!pos[k].empty())
		insert_check(pos[k].top());
	return;
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;++i){
		cin>>a[i];
		pre[i]=pre[i-1]+!a[i];
	}
	f.build(1,1,n);
	g.build(1,1,n);
	for(int i=1;i<=n;++i)
		b.add(i,1);
	int x,k,y;
	while(m--){
		cin>>x>>k>>y;
		erase(x);
		insert(x,k);
		if(a[y]!=0)	cout<<a[y]<<'\n';
		if(a[y]==0)	cout<<b.kth(pre[y])<<'\n';
	}
#define _ 0
	return ~~(0^_^0);
}

完结散花！！！