Description

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

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

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

位置上的数字。

Input

输入数据的第一行为两个整数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

Output

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

Sample Input

6 3

1 6 2 5 3 4

0 1 4

1 3 6

0 2 4

3

Sample Output

5

 

---

 

这道题有个比较妙的写法就是二分答案+线段树01排序（网上题解一般都这么写），目测1w多ms能过。

当然这种模型其实是线段树的分裂与合并，不过这里只有一次询问，而这种做法可以解决动态查询的情况。

外层的平衡树（这里用set）维护每段序列是在哪棵线段树上，线段树则存这段序列中有哪些值，这样就做到这段序列是有序的。

因为这里有升序和降序两种情况，所以我们可以先全部按照升序来建线段树，同时给线段树打上是升序还是降序的标记。

刚开始每个位置都是一棵线段树，之后每次把要排序的一段区间合并成一棵，表示此区间已有序。

因为要合并的一段区间有可能是一棵线段树的一部分，所以要考虑线段树分裂的操作。

特别的，当要求排序的一段区间完全在一棵线段树内，如果此线段树的升降序与此次要求相同，则不需做任何操作；

否则，需要把线段树最多分裂成左、中、右三棵（ps.如果先分裂左边，要注意分裂完右边要分裂的端点在线段树中的位置可能左移）。

每次排序后都要把不需要的线段树从set中删除，再把新的线段树插入平衡树中。

查询的时候先在set中查出该位置位于哪一棵线段树中，在到那棵线段树中去找就行了（注意此线段树是升序还是降序）。

注意可以垃圾回收的地方：因为涉及到点的删除和增加，因此我们可以开个栈来储存线段树的节点编号，每次从栈顶取元素作为当前节点的编号。

因为叶子节点总数永远为n，所以节点数不会大于nlog(n)。

复杂度：(n+m)*log(n)

在bzoj上不加fread跑了1732ms，说明还是比第一种做法要优很多的。

1 #include
       
          2 #include
        
           3 #include
         
            4 const int N=1e5+10;  5 struct node{  6     int l,r,id;  7     bool operator <(const node&p)const{
     return p.l>l;}  8 };  9 typedef std::multiset
          
           me; 10 typedef me::iterator IT; 11 int n,m,st[N*20],q,a[N],op,L,R,t=0,L0,R0; 12 me se; 13 struct point{
     int l,r,lson,rson,ok,sz;}e[25*N]; 14 int read(){ 15     int ans=0,f=1;char c=getchar(); 16     while(c<'0'||c>'9'){
     if(c=='-')f=-1;c=getchar();} 17     while(c>='0'&&c<='9'){ans=ans*10+c-48;c=getchar();} 18     return ans*f; 19 } 20 void erase(int id){e[id].lson=e[id].rson=e[id].sz=e[id].ok=0;st[++t]=id;} 21 void build(int &rt,int l,int r,int x){ 22     rt=st[t--];e[rt].ok=0;e[rt].l=l;e[rt].r=r;e[rt].sz=1;e[rt].lson=e[rt].rson=0; 23     if(l==r)return; 24     int mid=(l+r)>>1; 25     if(mid>=x)build(e[rt].lson,l,mid,x); 26     else build(e[rt].rson,mid+1,r,x); 27 } 28 void spilt(int&rt,int last,int p,int x){ 29     rt=st[t--];e[rt].l=e[last].l;e[rt].r=e[last].r;e[rt].lson=e[rt].rson=0; 30     int ls=e[last].lson,rs=e[last].rson; 31     if(p){ 32         if(ls&&e[ls].sz>x)spilt(e[rt].lson,ls,p,x); 33         else { 34             e[rt].lson=ls;e[last].lson=0; 35             if(rs&&x!=e[ls].sz)spilt(e[rt].rson,rs,p,x-e[ls].sz); 36         } 37     } 38     else{ 39         if(ls&&e[ls].sz+1>=x){ 40             e[rt].rson=rs;e[last].rson=0; 41             if(x!=e[ls].sz+1)spilt(e[rt].lson,ls,p,x); 42         } 43         else if(rs)spilt(e[rt].rson,rs,p,x-e[ls].sz); 44     } 45     int ll=e[rt].lson,rr=e[rt].rson,ss=0; 46     if(ll)ss+=e[ll].sz;if(rr)ss+=e[rr].sz; 47     if(ss)e[rt].sz=ss,e[last].sz-=ss; 48 } 49 void merge(int rt,int rt0){ 50     int ll=0; 51     if(e[rt0].lson) 52         if(!e[rt].lson)e[rt].lson=e[rt0].lson; 53         else merge(e[rt].lson,e[rt0].lson); 54     if(e[rt0].rson) 55         if(!e[rt].rson)e[rt].rson=e[rt0].rson; 56         else merge(e[rt].rson,e[rt0].rson); 57     int l=e[rt].lson,r=e[rt].rson; 58     if(l)ll+=e[l].sz;if(r)ll+=e[r].sz; 59     e[rt].sz=ll; 60     erase(rt0); 61 } 62 int find(int rt,int k){ 63     if(e[rt].l==e[rt].r)return e[rt].l; 64     int l=e[rt].lson,r=e[rt].rson; 65     if(l&&e[l].sz>=k)return find(l,k); 66     else return find(r,k-e[l].sz); 67 } 68 int main(){ 69     n=read();m=read();int mid=(1+n)>>1; 70     for(int i=0;i<=19*N;i++)st[++t]=i; 71     for(int i=1;i<=n;i++){ 72         a[i]=read();int sum=st[t--]; 73         se.insert((node){i,i,sum});e[sum].l=1;e[sum].r=n;e[sum].ok=0;e[sum].lson=e[sum].rson=0;e[sum].sz=1; 74         if(a[i]<=mid)build(e[sum].lson,1,mid,a[i]); 75         else build(e[sum].rson,mid+1,n,a[i]); 76     } 77     while(m--){ 78         node pp;IT it1;bool flag=1; 79         op=read();L=read();R=read();L0=L;R0=R; 80         IT it=se.upper_bound((node){L,0,0}); 81         it--;int rt=it->id,rt0; 82         if(L==R)continue;if(L>R)std::swap(L,R); 83         if(L==it->l&&R==it->r){e[it->id].ok=op;continue;} 84         int p=0;if(e[it->id].ok)p=1,L=it->r-L+1;else L=L-it->l+1; 85         IT it0=se.upper_bound((node){R,0,0}); 86         it0--;rt0=it0->id; 87         if(e[it0->id].ok)R=it0->r-R+1;else R=R-it0->l+1; 88         if(L0>=it->l&&R0<=it->r){ 89             if(op==e[it->id].ok)continue; 90             L=L0-it->l;R=R0-it->l+2;if(e[it->id].ok)L=e[it->id].sz-L+1,R=e[it->id].sz-R+1; 91             if(L0!=it->l)spilt(rt,it->id,!p,L),e[rt].ok=!op,se.insert((node){it->l,L0-1,rt}); 92             if(L
           
            r)spilt(rt0,it->id,p,R),e[rt0].ok=!op,se.insert((node){R0+1,it->r,rt0}); 94             node pp=*it;e[pp.id].ok=op;pp=(node){L0,R0,it->id}; 95             se.erase(it);se.insert(pp); 96             continue; 97         } 98         if(it->l
            
             id,p,L);100 pp=*it;pp.r=L0-1;se.erase(it);101 it=se.insert(pp);102 }103 else flag=0;p=1;if(e[it0->id].ok)p=0;104 if(it0->r>R0){105 spilt(rt0,it0->id,p,R);pp=*it0;it1=--it0;it0++;pp.l=R0+1;se.erase(it0);se.insert(pp);it0=it1;106 }107 else it1=it0,it0--,se.erase(it1);108 merge(rt,rt0);109 while(it0!=se.begin()&&it!=it0){110 it1=it0;111 merge(rt,it1->id);112 it0--;se.erase(it1);113 }114 e[rt].ok=op;if(!flag)se.erase(it);115 se.insert((node){L0,R0,rt});116 117 }118 q=read();119 IT it=se.upper_bound((node){q,0,0});it--;120 q=q-it->l+1;121 if(e[it->id].ok)q=e[it->id].sz-q+1;122 printf("%d",find(it->id,q));123 return 0;124 }