bzoj4552(排序 二分答案+01序列)

题目

二分答案。那么只用判断这个数是否合法即可。
设这个数为x。个序列中>x记为1,<x记为-1,=x记为0.
最后只用判断q位置上的数是不是0即可.
用线段树处理。区间覆盖。和区间-1,0,1的数字个数。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int a[N],refl[N],sum[N<<2],one[N<<2],tag[N<<2],n,m,d;
struct Operate{int typ,l,r;}q[N];
void pushup(int pos){
	sum[pos]=sum[pos<<1]+sum[pos<<1|1];
	one[pos]=one[pos<<1]+one[pos<<1|1];
}
int _get(int x,int y){
	if(x==y) return 0;
	return (x<y)?-1:1;
}
void build(int l,int r,int pos,int K){
	tag[pos]=-2;
	if(l==r){sum[pos]=_get(a[l],K),one[pos]=(!sum[pos]);return;}
	int mid=(l+r)>>1;
	build(l,mid,pos<<1,K),build(mid+1,r,pos<<1|1,K);
	pushup(pos);
}
void pushdown(int l,int r,int pos){
	if(tag[pos]==-2) return;
	int mid=(l+r)>>1;
	sum[pos<<1]=tag[pos]*(mid-l+1),sum[pos<<1|1]=tag[pos]*(r-mid);
	one[pos<<1]=(!tag[pos])*(mid-l+1),one[pos<<1|1]=(!tag[pos])*(r-mid);
	tag[pos<<1]=tag[pos<<1|1]=tag[pos];
	tag[pos]=-2;
}
struct node{
	int sum1,sum2;
	node operator+(const node &A)const{
		return (node){sum1+A.sum1,sum2+A.sum2};
	}
};
node querysum(int cl,int cr,int l,int r,int pos){
	if(cl<=l&&r<=cr) return (node){sum[pos],one[pos]};
	int mid=(l+r)>>1;
	pushdown(l,r,pos);
	if(mid<cl) return querysum(cl,cr,mid+1,r,pos<<1|1);
	if(mid>=cr) return querysum(cl,cr,l,mid,pos<<1);
	return querysum(cl,cr,l,mid,pos<<1)+querysum(cl,cr,mid+1,r,pos<<1|1);
}
void update(int f,int cl,int cr,int l,int r,int pos){
    if(cl>cr) return;
	if(cl<=l&&r<=cr){tag[pos]=f,sum[pos]=f*(r-l+1),one[pos]=(!f)*(r-l+1);return;}
	int mid=(l+r)>>1;
	pushdown(l,r,pos);
	if(cl<=mid) update(f,cl,cr,l,mid,pos<<1);
	if(cr>mid) update(f,cl,cr,mid+1,r,pos<<1|1);
	pushup(pos);
}
int query(int wh,int l,int r,int pos){
	if(l==r) return sum[pos];
	int mid=(l+r)>>1;
	pushdown(l,r,pos);
	if(wh<=mid) return query(wh,l,mid,pos<<1);
	else return query(wh,mid+1,r,pos<<1|1);
}
inline int check(int mid){
	build(1,n,1,mid);
	for(int i=1;i<=m;++i){
	 	node res=querysum(q[i].l,q[i].r,1,n,1);
	 	int sum1=res.sum1,B=res.sum2,sum3=(q[i].r-q[i].l+1);
	 	int A=(sum1+sum3-B)/2,C=(sum3-B-sum1)/2;
	 	if(q[i].typ){
		 	update(1,q[i].l,q[i].l+A-1,1,n,1);
		 	update(0,q[i].l+A,q[i].l+A+B-1,1,n,1);
		 	update(-1,q[i].l+A+B,q[i].r,1,n,1);
	  	}else{
	  		update(-1,q[i].l,q[i].l+C-1,1,n,1);
		 	update(0,q[i].l+C,q[i].l+C+B-1,1,n,1);
		 	update(1,q[i].l+C+B,q[i].r,1,n,1);
		}
	}
	return query(d,1,n,1);
}
int main(){
    //freopen("input.txt","r",stdin);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i) scanf("%d",&a[i]),refl[i]=a[i];
	for(int i=1;i<=m;++i) scanf("%d%d%d",&q[i].typ,&q[i].l,&q[i].r);
	scanf("%d",&d);
	sort(refl+1,refl+n+1);
	int low=1,high=n,mid;
	while(low<=high){
		mid=(low+high)>>1;
		int d=check(refl[mid]);
		if(!d) {printf("%d\n",refl[mid]);break;}
		if(d>0) low=mid+1;
		else high=mid-1;
	}
}