bzoj 4552: [Tjoi2016&Heoi2016]排序【二分+线段树】

二分值mid，然后把>=mid的赋值为1，其他赋值为0，每次排序就是算出区间内01的个数，然后分别把0和1放到连续的一段内，这些都可以用线段树来维护

二分的判断条件是操作完之后q位置上是否为1

#include<iostream>

#include<cstdio>

using namespace std;

const int N=100005;

int n,m,q,a[N],o[N],l[N],r[N];

struct xds

{

	int l,r,s[2],lz;

}t[N<<2];

struct qwe

{

	int s[2];

	qwe(int s0=0,int s1=1)

	{

		s[0]=s0,s[1]=s1;

	}

	qwe operator + (const qwe &b) const

	{

		return qwe(s[0]+b.s[0],s[1]+b.s[1]);

	}

};

int read()

{

	int r=0,f=1;

	char p=getchar();

	while(p>'9'||p<'0')

	{

		if(p=='-')

			f=-1;

		p=getchar();

	}

	while(p>='0'&&p<='9')

	{

		r=r*10+p-48;

		p=getchar();

	}

	return r*f;

}

void ud(int ro)

{

	t[ro].s[0]=t[ro<<1].s[0]+t[ro<<1|1].s[0];

	t[ro].s[1]=t[ro<<1].s[1]+t[ro<<1|1].s[1];

}

void pd(int ro)

{

	if(t[ro].lz!=-1)

	{

		t[ro<<1].s[t[ro].lz]=t[ro<<1].r-t[ro<<1].l+1;

		t[ro<<1].s[t[ro].lz^1]=0;

		t[ro<<1].lz=t[ro].lz;

		t[ro<<1|1].s[t[ro].lz]=t[ro<<1|1].r-t[ro<<1|1].l+1;

		t[ro<<1|1].s[t[ro].lz^1]=0;

		t[ro<<1|1].lz=t[ro].lz;

		t[ro].lz=-1;

	}

}

void build(int ro,int l,int r,int w)

{

	t[ro].l=l,t[ro].r=r,t[ro].lz=-1;

	if(l==r)

	{

		t[ro].s[a[l]>=w]=1;

		t[ro].s[a[l]<w]=0;

		return;

	}

	int mid=(l+r)>>1;

	build(ro<<1,l,mid,w);

	build(ro<<1|1,mid+1,r,w);

	ud(ro);

}

void update(int ro,int l,int r,int v)

{

	if(l>r)

		return;

	if(t[ro].l==l&&t[ro].r==r)

	{

		t[ro].s[v]=t[ro].r-t[ro].l+1;

		t[ro].s[v^1]=0;

		t[ro].lz=v;

		return;

	}

	pd(ro);

	int mid=(t[ro].l+t[ro].r)>>1;

	if(r<=mid)

		update(ro<<1,l,r,v);

	else if(l>mid)

		update(ro<<1|1,l,r,v);

	else

		update(ro<<1,l,mid,v),update(ro<<1|1,mid+1,r,v);

	ud(ro);

}

qwe ques(int ro,int l,int r)

{

	if(t[ro].l==l&&t[ro].r==r)

		return qwe(t[ro].s[0],t[ro].s[1]);

	pd(ro);

	int mid=(t[ro].l+t[ro].r)>>1;

	if(r<=mid)

		return ques(ro<<1,l,r);

	else if(l>mid)

		return ques(ro<<1|1,l,r);

	else

		return ques(ro<<1,l,mid)+ques(ro<<1|1,mid+1,r);

}

bool ok(int w)

{

	build(1,1,n,w);

	for(int i=1;i<=m;i++)

	{

		qwe u=ques(1,l[i],r[i]);//cerr<<"OK"<<endl;

		if(o[i]==0)

			update(1,l[i],l[i]+u.s[0]-1,0),update(1,l[i]+u.s[0],r[i],1);

		else

			update(1,l[i],l[i]+u.s[1]-1,1),update(1,l[i]+u.s[1],r[i],0);

	}

	return ques(1,q,q).s[1];

}

int main()

{

	n=read(),m=read();

	for(int i=1;i<=n;i++)

		a[i]=read();

	for(int i=1;i<=m;i++)

		o[i]=read(),l[i]=read(),r[i]=read();

	q=read();

	int l=1,r=n,ans=1;

	while(l<=r)

	{

		int mid=(l+r)>>1;//cerr<<mid<<endl;

		if(ok(mid))

			l=mid+1,ans=mid;

		else

			r=mid-1;

	}

	printf("%d\n",ans);

	return 0;

}

巴特西

bzoj 4552: [Tjoi2016&Heoi2016]排序【二分+线段树】

最新文章

热门文章