题目描述

在2016年，佳媛姐姐喜欢上了数字序列。因而他经常研究关于序列的一些奇奇怪怪的问题，现在他在研究一个难题

，需要你来帮助他。这个难题是这样子的：给出一个1到n的全排列，现在对这个全排列序列进行m次局部排序，排

序分为两种：1:(0,l,r)表示将区间[l,r]的数字升序排序2:(1,l,r)表示将区间[l,r]的数字降序排序最后询问第q

位置上的数字。

输入

输入数据的第一行为两个整数n和m。n表示序列的长度，m表示局部排序的次数。1 <= n, m <= 10^5第二行为n个整

数，表示1到n的一个全排列。接下来输入m行，每一行有三个整数op, l, r, op为0代表升序排序，op为1代表降序

排序, l, r 表示排序的区间。最后输入一个整数q，q表示排序完之后询问的位置, 1 <= q <= n。1 <= n <= 10^5

，1 <= m <= 10^5

输出

输出数据仅有一行，一个整数，表示按照顺序将全部的部分排序结束后第q位置上的数字。

样例输入

6 31 6 2 5 3 40 1 41 3 60 2 43

样例输出

5 ps：给了5s

---

这道题因为时间给的比较宽裕，所以可以用 O(nlog2n)的算法 大体思路就是二分答案X，把大于X的数当作1，小于等于的看作0 这样区间排序的问题就变成了区间求和和区间赋值~ 用一个线段树就可以了 看代码吧（哇一A了好开心o(*￣▽￣*)o）：

1 #include
      
        2 using namespace std; 3 int n,m,q,X,ans; 4 struct ask{ 5     int op,l,r; 6 }s[100005]; 7 int a[100005],sum[400005],tag[400005]; 8 void build(int x,int l,int r){ 9     if(l==r){10         sum[x]=a[l]>X;11         tag[x]=-1;12         return;13     }14     int mid=(l+r)/2;15     build(x+x,l,mid),build(x+x+1,mid+1,r);16     sum[x]=sum[x+x]+sum[x+x+1];17     tag[x]=-1;18 }19 void pushdown(int x,int l,int r){20     if(tag[x]!=-1){21         int mid=(l+r)/2;22         sum[x+x]=tag[x]*(mid-l+1);23         tag[x+x]=tag[x];24         sum[x+x+1]=tag[x]*(r-mid);25         tag[x+x+1]=tag[x];26         tag[x]=-1;27     }28 }29 int query(int x,int l,int r,int L,int R){30     if(l==L&&r==R)return sum[x];31     pushdown(x,l,r);32     int mid=(l+r)/2;33     if(R<=mid)return query(x+x,l,mid,L,R);34     else if(L>mid)return query(x+x+1,mid+1,r,L,R);35     else return query(x+x,l,mid,L,mid)+query(x+x+1,mid+1,r,mid+1,R);36 }37 void change(int x,int l,int r,int L,int R,int t){38     if(l==L&&r==R){39         tag[x]=t;40         sum[x]=t*(r-l+1);41         return;42     }43     pushdown(x,l,r);44     int mid=(l+r)/2;45     if(R<=mid)change(x+x,l,mid,L,R,t);46     else if(L>mid)change(x+x+1,mid+1,r,L,R,t);47     else change(x+x,l,mid,L,mid,t),change(x+x+1,mid+1,r,mid+1,R,t);48     sum[x]=sum[x+x]+sum[x+x+1];49 }50 bool check(){51     build(1,1,n);52     for(int i=1,tmp;i<=m;i++){53         tmp=query(1,1,n,s[i].l,s[i].r);54         change(1,1,n,s[i].l,s[i].r,0);55         if(tmp!=0){56             if(s[i].op==1)change(1,1,n,s[i].l,s[i].l+tmp-1,1);57             else change(1,1,n,s[i].r-tmp+1,s[i].r,1);58         }59     }60     return query(1,1,n,q,q)==0;61 }62 void erfen(){63     int l=1,r=n+1;64     while(r-l>1){65         X=(l+r)/2;66         if(check())ans=X,r=X;67         else l=X;68     }69     return;70 }71 int main(){72     scanf("%d%d",&n,&m);73     for(int i=1;i<=n;i++)scanf("%d",&a[i]);74     for(int i=1;i<=m;i++)scanf("%d%d%d",&s[i].op,&s[i].l,&s[i].r);75     scanf("%d",&q);76     erfen();77     printf("%d",ans);78     return 0;79 }