疑问
查看原帖
疑问
227824
JK_LOVER楼主2020/5/5 11:05

这道题为啥不可以直接维护。。。。

#include<bits/stdc++.h>
using namespace std;
#define N 11400000
struct node{
	int l,r,Lmax,Rmax,tot,L,R;
}t[N];
int read()
{
	int x=0,f=0;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')f=1;ch=getchar();}
	while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
	return f?-x:x;
}
void update(int x)
{
	if(t[x<<1].R != t[x<<1|1].L) t[x].tot = t[x<<1].Rmax + t[x<<1|1].Lmax;
	t[x].tot = max(max(t[x<<1].tot,t[x<<1|1].tot),t[x].tot);
	t[x].L = t[x<<1].L;
	t[x].R = t[x<<1|1].R;
	if(t[x<<1].R != t[x<<1|1].L && t[x<<1].Lmax == t[x<<1].r-t[x<<1].l+1) 
	t[x].Lmax = t[x<<1].tot + t[x<<1|1].Lmax;
	else t[x].Lmax = t[x<<1].Lmax;
	if(t[x<<1].R != t[x<<1|1].L && t[x<<1|1].Rmax == t[x<<1|1].r-t[x<<1|1].l+1)
	t[x].Rmax = t[x<<1].Rmax + t[x<<1|1].tot;
	else t[x].Rmax = t[x<<1|1].Rmax;
	t[x].tot = max(t[x].Lmax,max(t[x].Rmax,t[x].tot));
}
void build(int q,int l,int r)
{
	t[q].l = l;t[q].r = r;
	if(l == r)
	{
		t[q].Lmax=t[q].Rmax=t[q].tot=t[q].L=t[q].R=1;
		return ;
	}
	int mid = l + r>>1;
	build(q<<1,l,mid);
	build(q<<1|1,mid+1,r);
	update(q);
}
void change(int q,int l,int r,int key)
{
	if(key == l && key == r)
	{
		t[q].R = t[q].L = t[q].L^1;
		return;
	}
	int mid = l+r>>1;
	if(key <= mid) change(q<<1,l,mid,key);
	if(key > mid) change(q<<1|1,mid+1,r,key);
	update(q);
}
int n,m;
signed main()
{
	n=read();m=read();
	build(1,1,n);
	for(int i = 1;i <= m;i++)
	{
		int a = read();
		change(1,1,n,a);
		printf("%d\n",t[1].tot);
	}
}
2020/5/5 11:05
加载中...