来自FallDream的博客，未经允许，请勿转载，谢谢。

---

在2016年，佳媛姐姐喜欢上了数字序列。因而他经常研究关于序列的一些奇奇怪怪的问题，现在他在研究一个难题，需要你来帮助他。这个难题是这样子的：给出一个1到n的全排列，现在对这个全排列序列进行m次局部排序，排序分为两种：1:(0,l,r)表示将区间[l,r]的数字升序排序2:(1,l,r)表示将区间[l,r]的数字降序排序最后询问第q位置上的数字。

n,m<=10^5

 

一道十分巧妙的题    虽然被ditoly秒切了(orz集训队大爷)

考虑二分答案，然后大于的设成1，小等于设成0，用线段树维护。

每次排序就是把0和1其中一个全部丢到前面，另一个丢到后面，也就是区间赋值

复杂度nlog^2n

#include
      
       #include
       
        #define MN 100000using namespace std;inline int read(){    int x=0;char ch=getchar();    while(ch<'0'||ch>'9')ch=getchar();    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();    return x;}int a[MN+5],n,m,Mid,Res,Pos;struct op{
    int kind,l,r;}q[MN+5];struct Tree{
    int l,r,tag,val,x;}T[MN*4+5];void build(int x,int l,int r){    T[x].tag=0;    if((T[x].l=l)==(T[x].r=r)){T[x].x=(a[l]<=Mid);return;}    int mid=l+r>>1;    build(x<<1,l,mid);build(x<<1|1,mid+1,r);    T[x].x=T[x<<1].x+T[x<<1|1].x;}inline void Mark(int x,int v){    T[x].tag=1;T[x].val=v;    T[x].x=(v?0:T[x].r-T[x].l+1);}inline void pushdown(int x){    Mark(x<<1,T[x].val);    Mark(x<<1|1,T[x].val);    T[x].tag=0;}void Modify(int x,int l,int r,int ad){    if(l>r) return;    if(T[x].l==l&&T[x].r==r){Mark(x,ad);return;}    if(T[x].tag) pushdown(x);    int mid=T[x].l+T[x].r>>1;    if(r<=mid) Modify(x<<1,l,r,ad);    else if(l>mid) Modify(x<<1|1,l,r,ad);    else Modify(x<<1,l,mid,ad),Modify(x<<1|1,mid+1,r,ad);    T[x].x=T[x<<1].x+T[x<<1|1].x;}int Query(int x,int l,int r){    if(T[x].l==l&&T[x].r==r) return T[x].x;    if(T[x].tag) pushdown(x);    int mid=T[x].l+T[x].r>>1;    if(r<=mid) return Query(x<<1,l,r);    else if(l>mid) return Query(x<<1|1,l,r);    else return Query(x<<1,l,mid)+Query(x<<1|1,mid+1,r);}int main(){    n=read();m=read();    for(int i=1;i<=n;++i) a[i]=read();    for(int i=1;i<=m;++i) q[i].kind=read(),q[i].l=read(),q[i].r=read();    Pos=read();int l=1,r=n;    while(l<=r)    {        Mid=l+r>>1;        build(1,1,n);        for(int i=1;i<=m;++i)        {            int x=Query(1,q[i].l,q[i].r);            if(q[i].kind) Modify(1,q[i].l,q[i].r-x,1),Modify(1,q[i].r-x+1,q[i].r,0);            else Modify(1,q[i].l,q[i].l+x-1,0),Modify(1,q[i].l+x,q[i].r,1);        }        if(Query(1,Pos,Pos)) Res=Mid,r=Mid-1;        else l=Mid+1;    }    printf("%d\n",Res);    return 0;}