P2824 排序

问题

P2824 [HEOI2016/TJOI2016] 排序
给定一个排列，依次对若干下标区间做升序或降序排序，最后只询问全部操作结束后位置 $q$ 上的数。

数据规模：$n,m\le 10^5$。

我最开始的想法，就是直接在每次查询的区间手动跑一个快排，然后最后查询不就好了吗？

But，这是一道蓝题， $n,m\le 10^5$ 时，这只是把题意照做，最坏复杂度无法通过。

对于一个普通序列排序，需要 $\mathcal{O}(n\log n)$ 的时间；如果只对一个 01 序列排序，就只需统计区间内 1 的数量，再做至多两次区间覆盖。用线段树模拟一次排序的复杂度为 $\mathcal{O}(\log n)$。

即某一段区间的 $1$ 的个数是 $cnt1$，如果是改成升序排序，那么就将 $[r - cnt1 + 1, r]$ 改成 $1$，$[l, r - cnt1]$ 改成 $0$，降序反之。

所以在 $01$ 序列上，我们就可以把排序问题转化为了区间查询和区间修改问题。

回到题目的询问，由于只需要知道全部操作完后位置 $q$ 上的数是什么。也就是说，我们其实并不需要知道整个序列变成了什么样子。

于是我们可以二分答案，枚举位置 $q$ 上的值是多少，如果在若干次操作后 $q$ 的值是 $1$ 那就说明当前答案是满足的，反之如果是 $0$，就说明若干次操作后位置 $q$ 并没有得到我们想要的 mid。

接着我们还能发现这个答案是具有单调性的，OK，二分答案启动，注这是一个类离线的操作，而且它完全可以沿用 区间翻转与覆盖 的 01 线段树框架，非常简单。

注：这种二值化的思想可以扩展，而且本题也不是很标准的二分答案。

▶

P2824

struct SegTree {
/* ================================================== */
struct Node { 
    int l, r; 
    int one, tag; 
} tr[maxn << 2];

int len( int u ) { 
    return tr[u].r - tr[u].l + 1; 
}

void push_up( int u ) {
    tr[u].one = tr[ls].one + tr[rs].one;
}

void apply( int u, int val ) {
    tr[u].one = len( u ) * val;
    tr[u].tag = val;
}

void push_down( int u ) {
    if( tr[u].tag == -1 ) return ;
    apply( ls, tr[u].tag );
    apply( rs, tr[u].tag );
    tr[u].tag = -1;
}

void build( int u, int l, int r, int val[] ) {
    tr[u] = { l, r, 0, -1 };
    if( l == r ) {
        tr[u].one = val[l];
        return ;
    }
    int mid = ( l + r ) >> 1;
    build( ls, l, mid, val );
    build( rs, mid + 1, r, val );
    push_up( u );
}

void upd( int u, int l, int r, int val ) {
    if( l > r ) return;
    if( l <= tr[u].l && tr[u].r <= r ) {
        apply( u, val );
        return ;
    }
    push_down( u );
    int mid = ( tr[u].l + tr[u].r ) >> 1;
    if( l <= mid ) upd( ls, l, r, val );
    if( mid < r ) upd( rs, l, r, val );
    push_up( u );
}

int ask( int u, int l, int r ) {
    if( l <= tr[u].l && tr[u].r <= r ) return tr[u].one;
    push_down( u );
    int mid = ( tr[u].l + tr[u].r ) >> 1;
    int res = 0;
    if( l <= mid ) res += ask( ls, l, r );
    if( mid < r ) res += ask( rs, l, r );
    return res;
}
/* ================================================== */
} seg;

struct Query {
    int opt, l, r;
} qs[maxn];

int n, m, q;
int a[maxn];
int c[maxn];

bool check( int mid ) {
    for( int i = 1; i <= n; ++ i ) {
        c[i] = a[i] >= mid ? 1 : 0;
    }
    seg.build( 1, 1, n, c );
    for( int i = 1; i <= m; ++ i ) {
        auto [ opt, l, r ] = qs[i];
        int cnt = seg.ask( 1, l, r );
        if( opt == 0 ) {
            seg.upd( 1, l, r - cnt, 0 );
            seg.upd( 1, r - cnt + 1, r, 1 );
        } else {
            seg.upd( 1, l, l + cnt - 1, 1 );
            seg.upd( 1, l + cnt, r, 0 );
        }
    }
    return seg.ask( 1, q, q );
}

void solve( ) {
    n = read( ), m = read( );

    for( int i = 1; i <= n; ++ i ) {
        a[i] = read( );
    }

    for( int i = 1; i <= m; ++ i ) {
        int opt = read( );
        int l = read( ), r = read( );
        qs[i] = { opt, l, r };
    }
    q = read( );

    int l = 1, r = n, ans = 1;
    while( l <= r ) {
        int mid = ( l + r ) >> 1;
        if( check( mid ) ) ans = mid, l = mid + 1;
        else r = mid - 1;
    }

    cout << ans << '\n';
}

记录

• 归属：浅谈二分答案、浅谈线段树懒标记。
• 新增：只询问一个最终位置时，可以按阈值二值化，用类别数量代替维护完整排序结果。
• 分类：待定。