CF1270H Number of Components 做题记录

给定一个长 $n$ 的元素两两不同的序列 $a$，$\forall 1\le i<j\le n$，若 $a_i<a_j$，则让 $i$ 向 $j$ 连一条无向边。

$q$ 次修改数组某个位置的值，每次修改后输出图中连通块个数。

$1\le n,q\le 5\times 10^5$，$1\le a_i\le 10^6$，保证任意时刻数组中元素两两不同。

首先有个结论：

若 $i$ 和 $j$ 满足 $a_i<a_j$，则 $\forall i\le k\le j$，$k$ 与 $i$、$j$ 连通。

证明是显然的。

根据这个结论，每个连通块一定是一个连续段。

那么注意到 $\forall 2\le i\le n$，$i-1$ 和 $i$ 不在同一个连通块中当且仅当 $\min\limits_{j=1}^{i-1} a_j>\max\limits_{j=i}^n a_j$。而由于每个连通块都是连续段，所以连通块个数就是这样的 $i$ 的个数 $+1$。

定义 $x$ 的前驱 $\text{pre}(x)$ 为满足 $0\le i\le n,a_i<x$ 且 $a_i$ 最大的 $i$，令 $b_i=\sum\limits_{j=1}^n [\text{pre}(a_j)+1\le i\le j]$，则一定有：

• $b_1=0$；
• $b$ 中 $0$ 的个数就是连通块个数，因为每个 $b_i=0$ 的 $i$ 显然都满足 $\min\limits_{j=1}^{i-1} a_j>\max\limits_{j=i}^n a_j$；

那么用 set 维护前驱后继、线段树维护 $b$ 中最小值以及最小值个数即可。

代码如下：

#include <iostream>
#include <cstdio>
#include <set>

using namespace std;

const int S=500005;

int n,q,a[S];
int tag[S<<2],mn[S<<2],mnc[S<<2];
set<pair<int,int>> st;

inline void upda(int u)
{
	int ls=u<<1,rs=u<<1|1;
	mnc[u]=0;
	mn[u]=min(mn[ls],mn[rs]);
	if(mn[ls]==mn[u]) mnc[u]+=mnc[ls];
	if(mn[rs]==mn[u]) mnc[u]+=mnc[rs];
}

inline void addtag(int u,int val)
{
	tag[u]+=val;
	mn[u]+=val;
}

inline void dwntag(int u)
{
	if(tag[u]==0) return;
	addtag(u<<1,tag[u]),addtag(u<<1|1,tag[u]);
	tag[u]=0;
}

void build(int u,int l,int r)
{
	if(l==r) return tag[u]=0,mn[u]=0,mnc[u]=1,void();
	int mid=l+r>>1;
	build(u<<1,l,mid),build(u<<1|1,mid+1,r);
	upda(u);
}

void upd(int u,int l,int r,int L,int R,int val)
{
	if(l>R||r<L) return;
	if(l>=L&&r<=R) return addtag(u,val);
	dwntag(u);
	int mid=l+r>>1;
	if(L<=mid) upd(u<<1,l,mid,L,R,val);
	if(R>=mid+1) upd(u<<1|1,mid+1,r,L,R,val);
	upda(u);
}

inline void updd(int l,int r,int x)
{
	if(l==0||r==n+1) return;
	r=min(r,n);
	if(l+1>r) return;
	upd(1,1,n,l+1,r,x);
}

inline void ins(int p,int x)
{
	st.insert(make_pair(x,p));
	auto lb=st.lower_bound(make_pair(x,p));
	auto rb=st.lower_bound(make_pair(x,p));
	lb--,rb++;
	updd(lb->second,rb->second,-1);
	updd(lb->second,p,1);
	updd(p,rb->second,1);
}

inline void del(int p,int x)
{
	auto lb=st.lower_bound(make_pair(x,p));
	auto rb=st.lower_bound(make_pair(x,p));
	lb--,rb++;
	updd(lb->second,p,-1);
	updd(p,rb->second,-1);
	updd(lb->second,rb->second,1);
	st.erase(make_pair(x,p));
}

int main()
{
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	build(1,1,n);
	st.insert(make_pair(-1e9,0)),st.insert(make_pair(1e9,n+1));
	for(int i=1;i<=n;i++) ins(i,a[i]);
	while(q-->0)
	{
		int p,x;
		scanf("%d%d",&p,&x);
		del(p,a[p]);
		a[p]=x;
		ins(p,a[p]);
		printf("%d\n",mnc[1]);
	}
	return 0;
}