2017.10.28 排序 思考记录

这个题有一种套路，就是大小关系转化成01串，这样就变成了二分检验问题，，

就是把排序变成区间修改，然后单点查询。。

把所有比他小的赋成0，比他大的赋成1

然后判断要求位是0还是1来判断答案与当前值的大小

码：

#include<iostream>
#include<cstdio>
using namespace std;
#define zuo o<<1,l,mid
#define you o<<1|1,mid+1,r
#define N 100005
int bj[N<<2],sz[N<<2],op,wen,a,b,c,n,m,ans,ll[N],rr[N],aa[N],qq[N],i;
void down(int o,int l,int r)
{
	int ll=o<<1,rr=o<<1|1,mid=(r+l)>>1;
	if(bj[o]==1)
	{
		bj[o]=0;
		bj[ll]=1;
		bj[rr]=1;
		sz[ll]=0;
		sz[rr]=0;		
	}
	if(bj[o]==2)
	{
		bj[o]=0;
        bj[ll]=2;
        bj[rr]=2;
        sz[ll]=(mid-l+1);
		sz[rr]=(r-mid);	
	}
}
void up(int o)
{
 int ll=o<<1,rr=o<<1|1;
 sz[o]=sz[ll]+sz[rr];	
}
void gai(int o,int l,int r)
{
	if(a<=l&&r<=b)
	{
		if(op==0)
		{
		sz[o]=c*(r-l+1);
		bj[o]=c+1;
	    }else 
	    {
	    c+=sz[o];    	
	    }
		return;
	}
	down(o,l,r);
	int mid=(l+r)>>1;
	if(a<=mid)gai(zuo);
	if(b>mid)gai(you);	
	up(o);
}
int main()
{
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++)
	{
		scanf("%d",&aa[i]);		
	}
	for(i=1;i<=m;i++)
	{
		scanf("%d%d%d",&qq[i],&ll[i],&rr[i]);
	}
	scanf("%d",&wen);
	int l=1,r=n+1;
	while(l<r)
	{
		int mid=(l+r)>>1;		
		for(i=1;i<=n;i++)
		if(aa[i]<=mid)
		{
			a=i;
			b=i;
			c=0;
			op=0;
			gai(1,1,n);			
		}else
		{
			a=i;
			b=i;
			c=1;
			op=0;
			gai(1,1,n);	
		}
		for(i=1;i<=m;i++)
		{
			c=0;
			op=1;
			a=ll[i],b=rr[i];
			gai(1,1,n);int lin=c;
			op=0;
			if(qq[i]==0)
			{
			c=1;	
			a=rr[i]-lin+1;
			b=rr[i];
			if(a<=b)gai(1,1,n);
			c=0;	
			a=ll[i];
			b=rr[i]-lin;
			if(a<=b)gai(1,1,n);				
			}else
			{
			c=1;	
			a=ll[i];
			b=ll[i]+lin-1;
			if(a<=b)gai(1,1,n);		
			c=0;	
			a=ll[i]+lin;
			b=rr[i];
			if(a<=b)gai(1,1,n);	
		
			}		
		}
		op=1;
		c=0;
		a=b=wen;
		gai(1,1,n);
		if(c==0){ans=mid,r=mid;}
		else l=mid+1;
	}
printf("%d",ans);
}