Codeforces 题目传送门 & 洛谷题目传送门

首先需发现一个性质，那就是每一个连通块所对应的是一个区间。换句话说 \(\forall l<r\)，若 \(l,r\) 在同一连通块中，那 \(\forall x\in(l,r)\)，\(x\) 也在 \(l,r\) 所在的连通块中。

简单证明一下罢：

• 若 \(a_l<a_r\)，那么 \(\forall x\in(l,r)\)，若 \(a_x<a_r\)，那么 \(x\) 与 \(r\) 连通；若 \(a_x\ge a_r\)，则 \(a_x>a_l\)，\(x\) 与 \(l\) 连通，符合题意。
• 若 \(a_l\ge a_r\)，由于 \(l,r\) 连通，必定存在 \(x<l\) 满足 \(a_x<a_l,a_x<a_r\)；或者存在 \(x>r\) 满足 \(a_x>a_l,a_x>a_r\)。若是第一种情况，可将 \(x\) 看作新的 \(l\)，这样可归约到 \(a_l<a_r\) 的情况；若是第二种情况，可将 \(x\) 看作新的 \(r\)，这样也可归约到 \(a_l<a_r\) 的情况。

u1s1 我连这个性质都没看出来，可见我要脑子每脑子，要智商没智商/wq/wq

接下来考虑怎样判定 \(i,i+1\) 是否属于同一个连通块，根据上面的推论，\(i,i+1\) 不属于同一连通块当且仅当 \([1,i]\) 与 \([i+1,n]\) 之间没有边相连，即 \(\min\limits_{j=1}^ia_j>\max\limits_{j=i+1}^na_j\)。我们考虑枚举 \(\max\limits_{j=i+1}^na_j=w\)，并将序列中 \(>w\) 的数设为 \(1\)，\(\le w\) 的数设为 \(0\)，那么 \(w\) 满足条件当且仅当得到的序列为 \(111\dots11000\dots00\) 的形式。又显然 \(w\) 必定在 \(a\) 序列中出现过，故我们的目标是统计有多少个数 \(x\) 在 \(a\) 序列中出现过，并且满足将 \(>x\) 的数设为 \(1\)，\(\le x\) 的数设为 \(0\) 之后，得到的序列为 \(111\dots1000\dots00\) 的形式。这个东西怎么维护呢？我们设 \(f_w\) 为当 \(x=w\) 时序列中 \(10\) 段的个数，那我们只需统计 \(f_w=1\) 的 \(w\) 个数即可。我们以值为下标建一棵线段树，下标为 \(i\) 的位置为 \(f_i\) 的值。对于 \(i\in[0,n]\)，我们令 \([\min(a_i,a_{i+1}),\max(a_i,a_{i+1}))\) 的 \(f_w\) 加 \(1\)，表示当 \(w\in[\min(a_i,a_{i+1}),\max(a_i,a_{i+1}))\) 时 \(i,i+1\) 会产生一对 \(10\)。其中 \(a_0=\infty,a_{n+1}=0\)，表示我们强制令第 \(0\) 位对应的 \(01\) 值为 \(1\)，第 \(n+1\) 位对应的 \(01\) 值为 \(0\)，然后这边又是个套路，由于对于 \(\forall w\) 必有 \(f_w>0\)，故我们只需统计全局最小值个数，就是 \(f_w=1\) 的个数即可。

时间复杂度线性对数。

#include <bits/stdc++.h>

using namespace std;

#define fi first

#define se second

#define fill0(a) memset(a,0,sizeof(a))

#define fill1(a) memset(a,-1,sizeof(a))

#define fillbig(a) memset(a,63,sizeof(a))

#define pb push_back

#define ppb pop_back

#define mp make_pair

template<typename T1,typename T2> void chkmin(T1 &x,T2 y){if(x>y) x=y;}

template<typename T1,typename T2> void chkmax(T1 &x,T2 y){if(x<y) x=y;}

typedef pair<int,int> pii;

typedef long long ll;

typedef unsigned int u32;

typedef unsigned long long u64;

namespace fastio{

	#define FILE_SIZE 1<<23

	char rbuf[FILE_SIZE],*p1=rbuf,*p2=rbuf,wbuf[FILE_SIZE],*p3=wbuf;

	inline char getc(){return p1==p2&&(p2=(p1=rbuf)+fread(rbuf,1,FILE_SIZE,stdin),p1==p2)?-1:*p1++;}

	inline void putc(char x){(*p3++=x);}

	template<typename T> void read(T &x){

		x=0;char c=getchar();T neg=0;

		while(!isdigit(c)) neg|=!(c^'-'),c=getchar();

		while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=getchar();

		if(neg) x=(~x)+1;

	}

	template<typename T> void recursive_print(T x){if(!x) return;recursive_print(x/10);putc(x%10^48);}

	template<typename T> void print(T x){if(!x) putc('0');if(x<0) putc('-'),x=~x+1;recursive_print(x);}

	void print_final(){fwrite(wbuf,1,p3-wbuf,stdout);}

}

const int MAXN=5e5;

const int MAXV=1e6;

int n,qu,a[MAXN+5];

struct node{int l,r,mn,mnc,lz;} s[MAXV*4+5];

void pushup(int k){

	s[k].mn=min(s[k<<1].mn,s[k<<1|1].mn);s[k].mnc=0;

	if(s[k].mn==s[k<<1].mn) s[k].mnc+=s[k<<1].mnc;

	if(s[k].mn==s[k<<1|1].mn) s[k].mnc+=s[k<<1|1].mnc;

}

void build(int k,int l,int r){

	s[k].l=l;s[k].r=r;if(l==r) return;

	int mid=l+r>>1;build(k<<1,l,mid);build(k<<1|1,mid+1,r);

}

void pushdown(int k){

	if(s[k].lz){

		s[k<<1].mn+=s[k].lz;s[k<<1].lz+=s[k].lz;

		s[k<<1|1].mn+=s[k].lz;s[k<<1|1].lz+=s[k].lz;

		s[k].lz=0;

	}

}

void modify_mnc(int k,int p,int x){

	if(s[k].l==s[k].r){s[k].mnc+=x;return;}

	pushdown(k);int mid=s[k].l+s[k].r>>1;

	if(p<=mid) modify_mnc(k<<1,p,x);

	else modify_mnc(k<<1|1,p,x);

	pushup(k);

}

void modify(int k,int l,int r,int x){

	if(l>r) return;

	if(l<=s[k].l&&s[k].r<=r){s[k].lz+=x;s[k].mn+=x;return;}

	pushdown(k);int mid=s[k].l+s[k].r>>1;

	if(r<=mid) modify(k<<1,l,r,x);

	else if(l>mid) modify(k<<1|1,l,r,x);

	else modify(k<<1,l,mid,x),modify(k<<1|1,mid+1,r,x);

	pushup(k);

}

void update(int x,int v){modify(1,min(a[x],a[x+1]),max(a[x],a[x+1])-1,v);}

int main(){

	scanf("%d%d",&n,&qu);multiset<int> st;a[0]=MAXV+1;a[n+1]=0;

	for(int i=1;i<=n;i++) scanf("%d",&a[i]),st.insert(a[i]);build(1,0,MAXV);

	for(int i=1;i<=n;i++) modify_mnc(1,a[i],1);

	for(int i=0;i<=n;i++) update(i,1);

	while(qu--){

		int x,v;scanf("%d%d",&x,&v);st.erase(st.find(a[x]));

		update(x-1,-1);update(x,-1);modify_mnc(1,a[x],-1);

		a[x]=v;st.insert(v);

		update(x-1,1);update(x,1);modify_mnc(1,a[x],1);

		printf("%d\n",s[1].mnc);

	}

	return 0;

}