LuoguP2824[HEOI2016/TJOI2016]排序

题目
思路就很妙啊
显然一看就是要用线段树做，但是它巧妙的地方在于把序列变成01串了，因为只要查一个数(q)，所以 (≥q) 的记成1，(<q)的记成0
然后就上线段树了，排序就很好做了，升序就是这个区间里0都放前面1都放后面，降序反过来，1都放前面0都放后面
那最后怎么统计答案呢？
~~你看标签都说二分答案了~~所以显然要二分答案啊
一边二分一边check一下mid就好了
~~虽然题很简单思路很好懂但是写起来就各种出锅在小细节们上挂了2147483647次~~
最后感谢帮蒟蒻调代码的@wsy_jim @Blueqwq

code:

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#define maxn 400010
#define ll long long
using namespace std;
template<typename T>
inline void read(T &x){
	x=0; bool flag=0; char c=getchar();
	for(;!isdigit(c);c=getchar()) if(c=='-') flag=1;
	for(;isdigit(c);c=getchar()) x=x*10+(c^48);
	if(flag) x=-x;
}

ll n,m,op[maxn],a[maxn],b[maxn],q,s[maxn];
ll t[maxn],tag[maxn],v[maxn];

void pushup(ll x){
	t[x]=t[2*x]+t[2*x+1];
}

void build(ll x,ll l,ll r){
	if(l==r){
		t[x]=v[l];
		return ;
	}
	ll mid=(l+r)/2;
	build(2*x,l,mid);
	build(2*x+1,mid+1,r);
	pushup(x);
}

void tag_(ll x,ll len,ll k){
	t[x]=len*k;
	tag[x]=k;
}

void pushdown(ll x,ll l,ll r){
	if(tag[x]!=-1){
		ll mid=(l+r)/2;
		tag_(x*2,mid-l+1,tag[x]);
		tag_(x*2+1,r-mid,tag[x]);
		tag[x]=-1;
	}
}

void change(ll x,ll l,ll r,ll cl,ll cr,ll k){
	if(cl>cr) return ;
	if(cl<=l&&r<=cr) {tag_(x,r-l+1,k); return ;}
	pushdown(x,l,r);
	ll mid=(l+r)/2;
	if(cl<=mid) change(x*2,l,mid,cl,cr,k);
	if(mid+1<=cr) change(x*2+1,mid+1,r,cl,cr,k);
	pushup(x);
}

int query(ll x,ll l,ll r,ll ql,ll qr){
	if(ql<=l&&r<=qr) return t[x];
	pushdown(x,l,r);
	ll mid=(l+r)/2;
	ll ret=0;
	if(ql<=mid) ret+=query(x*2,l,mid,ql,qr);
	if(mid+1<=qr) ret+=query(x*2+1,mid+1,r,ql,qr);
	return ret;
}

bool check(ll x){
	memset(t,0,sizeof(t));
	memset(tag,-1,sizeof(tag));
	for(int i=1;i<=n;i++){//将数字序列转化成01串  >=q的v=1,<q的v=0 
		if(s[i]>=x) v[i]=1;//是>=x 不是>=q 
		else v[i]=0;
	}
	build(1,1,n);
	for(int i=1;i<=m;i++){
		ll tmp=query(1,1,n,a[i],b[i]);//统计区间里1的个数(大于等于q的数的个数) 
		if(op[i]==0){
			change(1,1,n,a[i],b[i]-tmp,0);
			change(1,1,n,b[i]-tmp+1,b[i],1);
		}
		if(op[i]==1){
			change(1,1,n,a[i],a[i]+tmp-1,1);
			change(1,1,n,a[i]+tmp,b[i],0);
		}
	} 
	return query(1,1,n,q,q);//
}

int main(){
	read(n),read(m);
	for(int i=1;i<=n;i++) read(s[i]);
	for(int i=1;i<=m;i++){
		read(op[i]),read(a[i]),read(b[i]);
	}
	read(q);
	ll l=1,r=n,ans=0;
	while(l<=r){
		ll mid=(l+r)/2;
		if(check(mid)) l=mid+1,ans=mid;
		else r=mid-1;
//		cout<<query(1,1,n,1,n)<<endl;
	}
	cout<<ans<<endl;
	
	return 0;
}

LuoguP2824[HEOI2016/TJOI2016]排序

相关推荐