sol
显然对于n个不同的数不好处理排序吧。
那什么情况下方便处理呢？只有0或1？
二分一个答案\(mid\)，把所有小于等于\(mid\)的数全部设为1，大于\(mid\)的数全部设为0。
然后就只要按要求排序就行了。用线段树维护01序列的排序，相信大家都会。
最后只要判断\(q\)位置上的数是不是1就行了。
复杂度\(O(m\log{n})\)
code
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int gi()
{
int x=0,w=1;char ch=getchar();
while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
if (ch=='-') w=0,ch=getchar();
while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return w?x:-x;
}
const int N = 1e5+5;
struct node{int op,l,r;}q[N];
int n,m,a[N],P,L,R,MID,tag[N<<2],sum[N<<2];
void pushup(int x)
{
sum[x]=sum[x<<1]+sum[x<<1|1];
}
void cover(int x,int l,int r,int opt)
{
if (opt) sum[x]=r-l+1,tag[x]=1;
else sum[x]=0,tag[x]=0;
}
void pushdown(int x,int l,int r)
{
if (tag[x]==-1) return;
int mid=l+r>>1;
cover(x<<1,l,mid,tag[x]);cover(x<<1|1,mid+1,r,tag[x]);
tag[x]=-1;
}
void build(int x,int l,int r)
{
tag[x]=-1;
if (l==r) {sum[x]=(a[l]<=MID);return;}
int mid=l+r>>1;
build(x<<1,l,mid);build(x<<1|1,mid+1,r);
pushup(x);
}
void modify(int x,int l,int r,int ql,int qr,int opt)
{
if (l>=ql&&r<=qr) {cover(x,l,r,opt);return;}
pushdown(x,l,r);int mid=l+r>>1;
if (ql<=mid) modify(x<<1,l,mid,ql,qr,opt);
if (qr>mid) modify(x<<1|1,mid+1,r,ql,qr,opt);
pushup(x);
}
int query(int x,int l,int r,int ql,int qr)
{
if (l>=ql&&r<=qr) return sum[x];
pushdown(x,l,r);int mid=l+r>>1,s=0;
if (ql<=mid) s+=query(x<<1,l,mid,ql,qr);
if (qr>mid) s+=query(x<<1|1,mid+1,r,ql,qr);
return s;
}
bool check()
{
build(1,1,n);
for (int i=1;i<=m;++i)
{
int tmp=query(1,1,n,q[i].l,q[i].r);
if (tmp==0||tmp==q[i].r-q[i].l+1) continue;
if (!q[i].op)
{
modify(1,1,n,q[i].l,q[i].l+tmp-1,1);
modify(1,1,n,q[i].l+tmp,q[i].r,0);
}
else
{
modify(1,1,n,q[i].l,q[i].r-tmp,0);
modify(1,1,n,q[i].r-tmp+1,q[i].r,1);
}
}
return query(1,1,n,P,P);
}
int main()
{
n=gi();m=gi();
for (int i=1;i<=n;++i) a[i]=gi();
for (int i=1;i<=m;++i) q[i]=(node){gi(),gi(),gi()};
P=gi();L=1;R=n;
while (L<R)
{
MID=L+R>>1;
if (check()) R=MID;
else L=MID+1;
}
printf("%d\n",L);
return 0;
}