题意：

给你一个序列，它是1～n的全排列，现在进行两种操作：

0 l r：把[l,r]从小到大排列；

1 l r：把[l,r]从大到小排列。

做完这些操作以后，请输出下标为k的数。

思路：

这道题挺巧妙的。

考虑到这只有一次查询操作，而且它是全排列的，所以可考虑二分，为什么可以二分呢？二分有什么用呢？我们后面来讲。

首先二分一个数mid（1～n），然后对于序列中小于它的数记为0，大于等于它的数记为1。

然后开始模拟操作了，这里用线段树实现：

对于升序操作：首先查询这个区间有多少个1，假设为x，然后把区间的前面部分修改为0，后面x个修改为1。

对于降序操作：首先查询这个区间有多少个1，假设为x，然后把区间的前面x个修改为1，后面部分修改为0。

做完这些操作以后，查询第k个位置是否是1，如果是1的话，说明第k个位置的数肯定是属于[mid,r]的，如果不是1的话，说明第k个位置的数是属于[1,mid-1]的，然后进行二分调整就可以了。

所以这棵线段树维护的是区间1的个数（即区间和）。

那么为什么可以二分呢？

这个二分更像是一种缩小范围的方式，我前面解释的时候就已经体现出来了，而且因为这个下标为k的数肯定是唯一的，所以肯定是可以找得到的。

再感叹一句，真的巧妙啊。

代码：

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<math.h>
#include<time.h>
#include<stdlib.h>
#include<queue>
#include<stack>
#include<set>
#include<bitset>
#include<map>
#include<vector>
#include<algorithm>
#define MOD 1000000007
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
int n,m,num,ans;
int a[100010];
struct node
{
    int left,right;
    int val;//区间1的数量
    int f;
}node[100010<<2];
int op[100000][3];
void build(int l,int r,int id,int x)
{
    node[id].left=l;
    node[id].right=r;
    node[id].f=-1;
    if(l==r)
    {
        if(a[num]>=x)node[id].val=1;
        else node[id].val=0;
        //printf("%d ",node[id].val);
        num++;
        return;
    }
    int m=(l+r)>>1;
    build(l,m,id<<1,x);
    build(m+1,r,id<<1|1,x);
    node[id].val=node[id<<1].val+node[id<<1|1].val;
}
void down(int id)
{
    int l1=node[id<<1].left;
    int r1=node[id<<1].right;
    int l2=node[id<<1|1].left;
    int r2=node[id<<1|1].right;
    node[id<<1].f=node[id].f;
    node[id<<1].val=(r1-l1+1)*node[id].f;
    node[id<<1|1].f=node[id].f;
    node[id<<1|1].val=(r2-l2+1)*node[id].f;
    node[id].f=-1;
}
void query(int L,int R,int id)
{
    int l=node[id].left;
    int r=node[id].right;
    if(l>=L&&r<=R)
    {
        ans+=node[id].val;
        //printf("%d\n",node[id].val);
        //if(L==2&&R==4)printf("[%d,%d]\n",l,r);
        return;
    }
    if(node[id].f!=-1)down(id);
    int m=(l+r)>>1;
    if(L<=m)query(L,R,id<<1);
    if(R>m)query(L,R,id<<1|1);
}
void update(int L,int R,int id,int x)
{
    int l=node[id].left;
    int r=node[id].right;
    if(l>=L&&r<=R)
    {
        node[id].val=(r-l+1)*x;
        node[id].f=x;
        return;
    }
    if(node[id].f!=-1)down(id);
    int m=(l+r)/2;
    if(L<=m)update(L,R,id<<1,x);
    if(R>m)update(L,R,id<<1|1,x);
    node[id].val=node[id<<1].val+node[id<<1|1].val;
}
int judge(int x,int k)
{
    num=1;
    build(1,n,1,x);
    //printf("\n");
    for(int i=1;i<=m;i++)
    {
        if(op[i][0]==0)//升序
        {
            ans=0;
            query(op[i][1],op[i][2],1);
            //printf("q%d:%d\n",i,ans);
            update(op[i][1],op[i][2]-ans,1,0);
            //printf("(%d,%d)\n",op[i][1],op[i][2]-ans);
            update(op[i][2]-ans+1,op[i][2],1,1);
            //printf("(%d,%d)\n",op[i][2]-ans+1,op[i][2]);
        }
        else if(op[i][0]==1)
        {
            ans=0;
            query(op[i][1],op[i][2],1);
            //printf("q%d:%d\n",i,ans);
            update(op[i][1],op[i][1]+ans-1,1,1);
            //printf("(%d,%d)\n",op[i][1],op[i][1]+ans-1);
            update(op[i][1]+ans,op[i][2],1,0);
            //printf("(%d,%d)\n",op[i][1]+ans,op[i][2]);
        }
    }
    ans=0;
    query(k,k,1);
    //printf("ans=%d\n",ans);
    return ans;
}
int main()
{
    int t,k;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        for(int i=1;i<=m;i++)
            scanf("%d%d%d",&op[i][0],&op[i][1],&op[i][2]);
        scanf("%d",&k);
        int l=1,r=n;
        while(l<=r)
        {
            int mid=(l+r)>>1;
            //printf("mid=%d\n",mid);
            if(judge(mid,k))l=mid+1;
            else r=mid-1;
        }
        printf("%d\n",l-1);
    }
    return 0;
}