#2055. 「TJOI / HEOI2016」排序

题目描述

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

这个难题是这样子的：给出一个 1 11 到 n nn 的全排列，现在对这个全排列序列进行 m mm 次局部排序，排序分为两种：

(0,l,r) (0, l, r)(0,l,r) 表示将区间 [l,r] [l, r][l,r] 的数字升序排序
(1,l,r) (1, l ,r)(1,l,r) 表示将区间 [l,r] [l, r][l,r] 的数字降序排序

排序后询问第 q qq 位置上的数字。

输入格式

输入数据的第一行为两个整数 n nn 和 m mm。n nn 表示序列的长度，m mm 表示局部排序的次数 (1≤n,m≤1051 \leq n, m \leq 10^51≤n,m≤105)。
第二行为 n nn 个整数，表示 1 11 到 n nn 的一个全排列。
接下来输入 m mm 行，每一行有三个整数 op,l,r\text{op}, l, rop,l,r， op\text{op}op 为 0 代表升序排序，op\text{op}op 为 1 代表降序排序, l,rl, rl,r 表示排序的区间。
最后输入一个整数 qqq，qqq 表示排序完之后询问的位置，1≤q≤n1 \leq q \leq n1≤q≤n。

输出格式

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

样例

样例输入

6 3

1 6 2 5 3 4

0 1 4

1 3 6

0 2 4

3

样例输出

二分p位置上的值

小于p的为0，大于p的为1

线段树支持区间修改，查询区间0的个数

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define maxn 100010

using namespace std;

int a[maxn],n,m;

bool cmp(int x,int y){return x>y;}

int main(){

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

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

    int op,l,r;

    while(m--){

        scanf("%d%d%d",&op,&l,&r);

        if(op==) sort(a+l,a+r+,cmp);

        if(op==) sort(a+l,a+r+);

    }

    int q;scanf("%d",&q);

    cout<<a[q];

}

80分暴力

#include<iostream>

#include<cstdio>

#include<cstring>

#define maxn 100010

using namespace std;

int a[maxn],sum[maxn*],set[maxn*],ask[maxn][];

bool bz[maxn*];

int t,n,m,p;

void mark(int k,int l,int r,int v){

    sum[k]=(v?:r-l+);

    set[k]=v;

    bz[k]=;

}

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

    int mid=(l+r)>>;

    if(bz[k]){

        mark(k<<,l,mid,set[k]);

        mark(k<<|,mid+,r,set[k]);

        bz[k]=;

    }

}

void modify(int k,int l,int r,int opl,int opr,int v){

    if(opl>opr)return;

    if(l==opl&&r==opr){mark(k,l,r,v);return;}

    pushdown(k,l,r);

    int mid=(l+r)>>;

    if(opr<=mid)modify(k<<,l,mid,opl,opr,v);

    else if(opl>mid)modify(k<<|,mid+,r,opl,opr,v);

    else modify(k<<,l,mid,opl,mid,v),modify(k<<|,mid+,r,mid+,opr,v);

    sum[k]=sum[k<<]+sum[k<<|];

}

int query(int k,int l,int r,int opl,int opr){

    if(l>=opl&&r<=opr)return sum[k];

    pushdown(k,l,r);

    int mid=(l+r)>>,res=;

    if(opl<=mid)res+=query(k<<,l,mid,opl,opr);

    if(opr>mid)res+=query(k<<|,mid+,r,opl,opr);

    return res;

}

bool check(int x){

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

        if(a[i]<x)modify(,,n,i,i,);

        else modify(,,n,i,i,);

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

        t=query(,,n,ask[i][],ask[i][]);

        if(ask[i][]){

            modify(,,n,ask[i][],ask[i][]-t,);

            modify(,,n,ask[i][]-t+,ask[i][],);

        }

        else {

            modify(,,n,ask[i][],ask[i][]+t-,);

            modify(,,n,ask[i][]+t,ask[i][],);

        }

    }

    return !query(,,n,p,p);

}

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

}

100分线段树+二分答案

巴特西

loj #2055. 「TJOI / HEOI2016」排序