线段树+具有技巧的二分答案。
这道题我一遍过了！！！！！
这道题目十分的神奇：首先我们会发现两个做题的基石：
1、这道题查询只有一个，所以说我们可以考虑离线处理。
2、我们动态维护排序是十分困难的，但是我们可以想到线段树可以高效的对01串进行排序（通过维护区间内1的个数）；
然后我们就想，如果我们只关心要查询的点是否大于某个数，那么是不是就可以二分答案了？check也十分好实现，二分一个值mid，大于等于mid的数设为1，反之为0.那么我们可以用线段树高效的模拟m次操作，最后查询一下那个数是否为1，是就return1；
code：
#include<iostream>
#include<cstdio>
#include<queue>
#include<algorithm>
#include<cstring>
#include<ctime>
#define half (l+r)>>1
using namespace std;
const int maxn=300006;
int fina,num[maxn],uql[maxn],uqr[maxn],dql[maxn],dqr[maxn],n,m;
struct hzw
{
int lc,rc,val,tag;
}t[maxn*2];
int real[maxn],tot;
inline void build(int s,int l,int r)
{
t[s].tag=-1;
if (l==r)
{
t[s].val=real[l];
return ;
}
int mid=half;
t[s].lc=++tot;
build(t[s].lc,l,mid);
t[s].rc=++tot;
build(t[s].rc,mid+1,r);
t[s].val=t[t[s].lc].val+t[t[s].rc].val;
}
inline void pushdown(int s,int l,int r)
{
int ll=t[s].lc,rr=t[s].rc;
int mid=half;
t[ll].val=(mid-l+1)*t[s].tag,t[ll].tag=t[s].tag;
t[rr].val=(r-mid)*t[s].tag,t[rr].tag=t[s].tag;
t[s].tag=-1;
}
inline void update(int s,int l,int r,int cl,int cr,int p)
{
if (cr<cl) return;
if (cl==l&&cr==r)
{
t[s].val=(r-l+1)*p;
t[s].tag=p;
return ;
}
int mid=half;
if (~t[s].tag) pushdown(s,l,r);
if (cr<=mid) update(t[s].lc,l,mid,cl,cr,p);
else if (cl>mid) update(t[s].rc,mid+1,r,cl,cr,p);
else
{
update(t[s].lc,l,mid,cl,mid,p);
update(t[s].rc,mid+1,r,mid+1,cr,p);
}
t[s].val=t[t[s].lc].val+t[t[s].rc].val;
}
inline int query(int s,int l,int r,int cl,int cr)
{
if (l==cl&&r==cr)
{
return t[s].val;
}
int mid=half;
if (~t[s].tag) pushdown(s,l,r);
if (cr<=mid) return query(t[s].lc,l,mid,cl,cr);
else if (cl>mid) return query(t[s].rc,mid+1,r,cl,cr);
else
{
return query(t[s].lc,l,mid,cl,mid)+query(t[s].rc,mid+1,r,mid+1,cr);
}
}
inline void usolve(int l,int r)
{
int tmp=query(1,1,n,l,r);
update(1,1,n,r-tmp+1,r,1);
update(1,1,n,l,r-tmp,0);
}
inline void dsolve(int l,int r)
{
int tmp=query(1,1,n,l,r);
update(1,1,n,l,l+tmp-1,1);
update(1,1,n,l+tmp,r,0);
}
inline bool check(int k)
{
for (int i=1;i<=n;++i) real[i]=num[i]>=k?1:0;
tot=1;
memset(t,0,sizeof(t));
build (1,1,n);
for (int i=1;i<=m;++i)
{
if (uql[i]) usolve(uql[i],uqr[i]);
else dsolve(dql[i],dqr[i]);
}
return query(1,1,n,fina,fina)==1;
}
int main()
{
cin>>n>>m;
for (int i=1;i<=n;++i) scanf("%d",&num[i]);
for (int i=1,a;i<=m;++i)
{
scanf("%d",&a);
if (a==0)scanf("%d%d",&uql[i],&uqr[i]);
else scanf("%d%d",&dql[i],&dqr[i]);
}
cin>>fina;
int l=1,r=n,ans=0;
while (l<=r)
{
int mid=half;
if (check(mid)) l=mid+1,ans=max(ans,mid);
else r=mid-1;
}
cout<<ans;
return 0;
}
收获：
如果要确定一个数，有时候可以只考虑一个数是否大于某个值，这样就可以二分了。关于多次排序的问题可以联想线段树可以高效的进行01串排序。