题目大意
给定一个长度为n的序列，有m个操作，操作包括两种：
(0 l r)区间[l,r]的数字升序排序
(1 l r)区间[l,r]的数字降序排序
最后询问在q位置上的数是多少？
其中(n le 100000,mle 100000)
QWQ这个题是看了题解才会的，感觉思路很不错
我们考虑，这个题的询问其实只有一组，所以我们可以 二分一个最终在q的数是多少（或者说在原来的排名是多少）
每次将大于等于(mid)的数变为1，小于的为0。
那么对于升序排序，假设这个区间有(tot)个1，
我们就可以将([r-tot+1,r])赋值为1，将剩余区间赋值为0
而降序排序呢，我们就可以将([l,l+tot-1])赋值为1，其余为0
这样就将“排序“ ---->“区间赋值”：
那么，我们不难想到！！！线段树！！！
只需要最后我们看一下第q个数是不是1就可以，如果是1，我们可以稍微加大mid，不然就减少mid
上代码
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<map>
#include<queue>
#include<vector>
using namespace std;
inline int read()
{
int x=0,f=1;char ch=getchar();
while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return x*f;
}
const int maxn = 100100;
int f[4*maxn];
int add[4*maxn];
int n,m,a[maxn];
int x[maxn],y[maxn],z[maxn];
int c[maxn];
int l,r;
int ques;
void up(int root)
{
f[root]=f[2*root]+f[2*root+1];
}
void pushdown(int root,int l,int r)
{
int mid = (l+r) >> 1;
if (add[root]!=-1)
{
add[2*root]=add[root];
add[2*root+1]=add[root];
f[2*root]=(mid-l+1)*add[root];
f[2*root+1]=(r-mid)*add[root];
add[root]=-1;
}
}
void build(int root,int l,int r)
{
add[root]=-1;
if (l==r)
{
f[root]=a[l];
return;
}
int mid =(l+r) >> 1;
build(2*root,l,mid);
build(2*root+1,mid+1,r);
up(root);
}
void update(int root,int l,int r,int x,int y,int p)
{
if (l>r || x>y) return;
if (x<=l && r<=y)
{
add[root]=p;
f[root]=(r-l+1)*add[root];
return;
}
pushdown(root,l,r);
int mid = (l+r) >> 1;
if (x<=mid) update(2*root,l,mid,x,y,p);
if (y>mid) update(2*root+1,mid+1,r,x,y,p);
up(root);
}
int query(int root,int l,int r,int x,int y)
{
if (l>r || x>y) return 0;
if (x<=l && r<=y)
{
return f[root];
}
pushdown(root,l,r);
int mid = (l+r) >> 1;
int ans=0;
if (x<=mid) ans=ans+query(2*root,l,mid,x,y);
if (y>mid) ans=ans+query(2*root+1,mid+1,r,x,y);
return ans;
}
bool check(int mid)
{
memset(a,-1,sizeof(a));
for (int i=1;i<=n;i++)
if (c[i]>=mid) a[i]=1;
else a[i]=0;
build(1,1,n);
for (int i=1;i<=m;i++)
{
int tot=query(1,1,n,x[i],y[i]);
if (z[i]==0)
{
update(1,1,n,y[i]-tot+1,y[i],1);
update(1,1,n,x[i],y[i]-tot,0);
}
else
{
update(1,1,n,x[i],x[i]+tot-1,1);
update(1,1,n,x[i]+tot,y[i],0);
}
}
if (query(1,1,n,ques,ques)==1) return true;
else false;
}
int ans;
int main()
{
scanf("%d%d",&n,&m);
l=1;
r=n;
for (int i=1;i<=n;i++) c[i]=read();
for (int i=1;i<=m;i++)
{
z[i]=read();
x[i]=read();
y[i]=read();
}
ques=read();
//二分这个位置上的数是多少
while (l<=r)
{
int mid = (l+r) >> 1;
if (check(mid)) l=mid+1,ans=mid;
else r=mid-1;
}
cout<<ans;
return 0;
}