出题人题解 | #最长区间#

原题解链接：https://ac.nowcoder.com/discuss/149978

定义数组 $b_{\mathrm{1..}n-1}b\_\{1\; .\; .\; n-1\}$ ，其中 . 当 时， $b_i=1b\_\{i\}=1$ ；否则 $b_i=0)\backslash left.b\_\{i\}=0\backslash right)$ 。

则所求 $=b=b$ 中最长的连续的 1 的长度 $+1+1$。

对于 $a_{x}a\_\{x\}$ 的修改相当于对于 $b_{x-1}b\_\{x-1\}$ 和 $b_{x}b\_\{x\}$ 的修改，所以下面只用考虑对 $b_{x}b\_\{x\}$ 的修改。

定义数组 $cn{t}_{\mathrm{0..99}}c\; n\; t\_\{0\; .\; .99\}$ ，其中 $cn{t}_{i}c\; n\; t\_\{i\}$ 表示 $bb$ 中有多少段极长的连续的 1 的长度为 $ii$ ，特别的， $cn{t}_0=infc\; n\; t\_\{0\}=i\; n\; f$ 。

求答案时只要找到满足 $cn{t}_i>0c\; n\; t\_\{i\}>0$ 的 $\max i\backslash max\; i$ 即可。

考虑当 $b_{x}b\_\{x\}$ 从 0 改成 1 时如何维护 $cntc\; n\; t$。

求出从 $x-1x-1$ 起向左的极长的连续的 1 的长度 left_len 和从 $x+1x+1$ 起向右的极长的连续的 1 的长度 right_len，

-- cnt[left_len]; --cnt_[right_len]; ++cnt[left_len+right_len }+1];

即可。

当$b_{x}b\_x$从$11$改成$00$时同理，只是把减换成加，加换成减。

时间复杂度$O(n+m\times 100)O(n+m\; \backslash times\; 100)$

#include<bits/stdc++.h>
using namespace std;

#define rep(i,l,r) for(int i=l;i<=r;++i)
#define per(i,r,l) for(int i=r;i>=l;--i)
const int N=1e5+5;
int n,a[N];

bool b[N];
int cnt[100];
void modify_b(int x)
{
	if(b[x]==(a[x]<a[x+1]))return ;
	b[x]^=1;
	
	int l=x;
	while(b[l-1])--l;
	int r=x+1;
	while(b[r])++r;
	if(b[x])
	{
		++cnt[r-l];--cnt[x-l];--cnt[r-(x+1)];
	}
	else
	{
		--cnt[r-l];++cnt[x-l];++cnt[r-(x+1)];
	}
}
void modify_a(int x,int y)
{
	a[x]=y;
	if(x!=1)modify_b(x-1);
	if(x!=n)modify_b(x);
}
int query()
{
	int i=99;
	while(!cnt[i])--i;
	return i+1;
}

int main()
{
//	freopen("1.in","r",stdin);
	int m;
	cin>>n>>m;
	cnt[0]=1e9;
	rep(i,1,n)
	{
		int x;
		scanf("%d",&x);
		modify_a(i,x);
	}
	printf("%d\n",query());
	while(m--)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		modify_a(x,y);
		printf("%d\n",query());
	}
}