[BZOJ4552]排序

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

二分答案后转化为01序列，用线段树维护，算是很常见的套路了

代码：

 #include<iostream>

 #include<cstdio>

 #include<algorithm>

 #define M 100010

 #define ls node<<1

 #define rs node<<1|1

 using namespace std;

 int n,m,ans,l,r,k;

 int a[M],b[M],opt[M],L[M],R[M],val[M<<],tag[M<<];

 void update(int node) {val[node]=val[ls]+val[rs];}

 void push(int node,int l,int r)

 {

     if(tag[node]!=-)

     {

         int mid=(l+r)/,v=tag[node];

         val[ls]=v*(mid-l+);

         val[rs]=v*(r-mid);

         tag[ls]=tag[rs]=v;

         tag[node]=-;

     }

 }

 void build(int node,int l,int r)

 {

     tag[node]=-;

     if(l==r) {val[node]=b[l];return;}

     int mid=(l+r)/;

     build(ls,l,mid); build(rs,mid+,r);

     update(node);

 }

 void change(int node,int l,int r,int l1,int r1,int v)

 {

     if(l1<=l&&r1>=r)

     {

         tag[node]=v;

         val[node]=(r-l+)*v;

         return;

     }

     if(l1>r||r1<l) return;

     int mid=(l+r)/; push(node,l,r);

     change(ls,l,mid,l1,r1,v); change(rs,mid+,r,l1,r1,v);

     update(node);

 }

 int query(int node,int l,int r,int l1,int r1)

 {

     if(l1<=l&&r1>=r) return val[node];

     if(l1>r||r1<l) return ;

     int mid=(l+r)/; push(node,l,r);

     return query(ls,l,mid,l1,r1)+query(rs,mid+,r,l1,r1);

 }

 bool check(int mid)

 {

     for(int i=;i<=n;i++)

         b[i]=a[i]>=mid?:;

     build(,,n);

     for(int i=;i<=m;i++)

     {

         if(opt[i]==)

         {

             int num=query(,,n,L[i],R[i]);

             change(,,n,R[i]-num+,R[i],);

             change(,,n,L[i],R[i]-num,);

         }

         else

         {

             int num=query(,,n,L[i],R[i]);

             change(,,n,L[i],L[i]+num-,);

             change(,,n,L[i]+num,R[i],);

         }

     }

     return query(,,n,k,k);

 }

 int main()

 {

     scanf("%d%d",&n,&m);

     for(int i=;i<=n;i++) scanf("%d",&a[i]);

     for(int i=;i<=m;i++) scanf("%d%d%d",&opt[i],&L[i],&R[i]);

     scanf("%d",&k);l=,r=n;

     while(l<=r)

     {

         int mid=(l+r)/;

         if(check(mid)) l=mid+,ans=mid;

         else r=mid-;

     }

     printf("%d",ans);

     return ;

 }

巴特西