想了一会怎么处理区间排序。

但是发现很难实现,但是区间覆盖还是比较拿手的。

貌似二分答案,然后排序转覆盖就可以了?

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<ctime>
#include<vector>
#include<algorithm>
#define gc getchar()
#define ll long long
#define eps 1e-8
#define ld long double 
#define ull unsigned long long
using namespace std;
const int N=1e5+5,M=12e5+5;
template<class o>
inline void qr(o &x)
{
    x=0;char c=gc;int f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
template<class o>
void qw(o x)
{
    if(x<0)putchar('-'),x=-x;
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
int bz,a[N];
struct SGT{bool ex;int lz,s,l,r;}t[N<<3];
inline void update(int p){t[p].ex=t[p<<1].ex|t[p<<1|1].ex;t[p].s=t[p<<1].s+t[p<<1|1].s;}
inline void pushdown(int p)
{
    if(t[p].lz!=-1)
    {
        t[p<<1].ex=t[p<<1].lz=t[p].lz;
        t[p<<1].s=(t[p<<1].r-t[p<<1].l+1)*t[p].lz;
        t[p<<1|1].ex=t[p<<1|1].lz=t[p].lz;
        t[p<<1|1].s=(t[p<<1|1].r-t[p<<1|1].l+1)*t[p].lz;
        t[p].lz=-1;
    }
}
void build(int p,int l,int r)
{
    t[p].l=l,t[p].r=r;t[p].lz=-1;
    if(l==r){t[p].s=t[p].ex=a[l]>=bz;return ;}
    int mid=l+r>>1;
    build(p<<1,l,mid);build(p<<1|1,mid+1,r);
    update(p);
}
void change(int p,int l,int r,int L,int R,int lz)
{
    if(L>R)return ;
    if(L<=l&&R>=r){t[p].lz=lz;t[p].ex=lz;t[p].s=(r-l+1)*lz;return ;}
    int mid=l+r>>1;pushdown(p);
    if(L<=mid)change(p<<1,l,mid,L,R,lz);
    if(R>mid)change(p<<1|1,mid+1,r,L,R,lz);
    update(p);
}
int query(int p,int l,int r,int L,int R)
{
    if(L<=l&&R>=r)return t[p].s;
    int mid=l+r>>1,val=0;pushdown(p);
    if(L<=mid)val+=query(p<<1,l,mid,L,R);
    if(R>mid)val+=query(p<<1|1,mid+1,r,L,R);
    return val;
}
bool query(int p,int l,int r,int pos)
{
    if(!t[p].ex)return 0;
    if(l==r)return t[p].ex;
    int mid=l+r>>1;pushdown(p);
    if(pos<=mid)return query(p<<1,l,mid,pos);
    return query(p<<1|1,mid+1,r,pos);
}
int n,m,q;
struct Query{int l,r,op;}Q[N];
bool check(int mid)
{
    bz=mid;
    build(1,1,n);
    for(int i=1;i<=m;i++)
    {
        int l=Q[i].l,r=Q[i].r,sum=query(1,1,n,l,r);
        if(Q[i].op)change(1,1,n,l,l+sum-1,1),change(1,1,n,l+sum,r,0);
        else change(1,1,n,l,r-sum,0),change(1,1,n,r-sum+1,r,1);
    }
    return query(1,1,n,q);
}
int main()
{
    qr(n);qr(m);
    for(int i=1;i<=n;i++)qr(a[i]);
    for(int i=1;i<=m;i++)qr(Q[i].op),qr(Q[i].l),qr(Q[i].r);
    qr(q);
    int l=1,r=n;
    while(l<r)
    {
        int mid=l+r+1>>1;
        if(check(mid))l=mid;
        else r=mid-1;
    }
    qw(l);puts("");
    return 0;
}