排序（bzoj 4552）

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

/*

    题解很神奇。

    二分答案k，那么就是要判断a[p]与k的大小关系。

    我们把序列变成0/1序列，0代表该位置的数小于k，1代表大于等于k，对于升降序操作，

    用线段树维护就可以了，最后判断一下。

*/

#include<iostream>

#include<cstdio>

#include<cstring>

#define N 30010

using namespace std;

int a[N],b[N][],n,m,p;

int sum[N*],tag[N*];

void push_up(int k){

    sum[k]=sum[k*]+sum[k*+];

}

void push_down(int k,int l,int r){

    if(tag[k]==-) return;

    int mid=l+r>>;

    tag[k*]=tag[k*+]=tag[k];

    sum[k*]=(mid-l+)*tag[k];

    sum[k*+]=(r-mid)*tag[k];

    tag[k]=-;

}

void change(int k,int l,int r,int x,int y,int val){

    if(x>y) return;

    if(l>=x&&r<=y){

        sum[k]=(r-l+)*val;

        tag[k]=val;

        return;

    }

    push_down(k,l,r);

    int mid=l+r>>;

    if(x<=mid) change(k*,l,mid,x,y,val);

    if(y>mid) change(k*+,mid+,r,x,y,val);

    push_up(k);

}

int query(int k,int l,int r,int x,int y){

    if(l>=x&&r<=y) return sum[k];

    push_down(k,l,r);

    int mid=l+r>>,tot=;

    if(x<=mid) tot+=query(k*,l,mid,x,y);

    if(y>mid) tot+=query(k*+,mid+,r,x,y);

    return tot;

}

bool check(int mid){

    memset(tag,-,sizeof(tag));

    memset(sum,,sizeof(sum));

    for(int i=;i<=n;i++) change(,,n,i,i,a[i]>=mid);

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

        int t=query(,,n,b[i][],b[i][]);

        if(!b[i][]){

            change(,,n,b[i][],b[i][]-t,);

            change(,,n,b[i][]-t+,b[i][],);

        }

        else {

            change(,,n,b[i][],b[i][]+t-,);

            change(,,n,b[i][]+t,b[i][],);

        }

    }

    int t=query(,,n,p,p);

    return t;

}

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",&b[i][],&b[i][],&b[i][]);

    scanf("%d",&p);

    int l=,r=n,ans;

    while(l<=r){

        int mid=l+r>>;

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

        else r=mid-;

    }

    printf("%d",ans);

    return ;

}

巴特西