AT_abc237_g [ABC237G] Range Sort Query

思路

将小于等于 $x$ 的元素赋为 $1$，其余的赋为 $0$。那么一个区间内小于等于 $x$ 的数量就是区间中 $1$ 的数量。

那么，将区间升序排列就是将 $1$ 先堆在前面，将 $0$ 堆到后面；降序排列同理。

考虑动态维护 $x$ 的位置，记其位置为 $t$。如果 $l \leq t \leq r$，则 $t$ 可能会改变；否则不会改变。

在升序排列中，$t$ 将会改变到最后一个 $1$ 的位置；在降序排序中，$t$ 将会改变到第一个 $1$ 的位置。然后维护 $0/1$ 可以用线段树维护。

Code

#include <bits/stdc++.h>
#define re register

using namespace std;

const int N = 2e5 + 10;
int n,q,k,x;
int arr[N];

inline int read(){
    int r = 0,w = 1;
    char c = getchar();
    while (c < '0' || c > '9'){
        if (c == '-') w = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9'){
        r = (r << 3) + (r << 1) + (c ^ 48);
        c = getchar();
    }
    return r * w;
}

struct seg{
    #define ls(u) (u << 1)
    #define rs(u) (u << 1 | 1)

    struct node{
        int l,r;
        int sum,tag;
    }tr[N << 2];
    
    inline void calc(int u,int k){
        tr[u].sum = (tr[u].r - tr[u].l + 1) * k;
        tr[u].tag = k;
    }

    inline void pushup(int u){
        tr[u].sum = tr[ls(u)].sum + tr[rs(u)].sum;
    }

    inline void pushdown(int u){
        if (~tr[u].tag){
            calc(ls(u),tr[u].tag); calc(rs(u),tr[u].tag);
            tr[u].tag = -1;
        }
    }

    inline void build(int u,int l,int r){
        tr[u] = {l,r,0,-1};
        if (l == r) return tr[u].sum = (arr[l] <= k),void();
        int mid = l + r >> 1;
        build(ls(u),l,mid); build(rs(u),mid + 1,r);
        pushup(u);
    }
    
    inline void modify(int u,int l,int r,int k){
        if (l > r) return;
        if (l <= tr[u].l && tr[u].r <= r) return calc(u,k);
        pushdown(u);
        int mid = tr[u].l + tr[u].r >> 1;
        if (l <= mid) modify(ls(u),l,r,k);
        if (r > mid) modify(rs(u),l,r,k);
        pushup(u);
    }

    inline int query(int u,int l,int r){
        if (l <= tr[u].l && tr[u].r <= r) return tr[u].sum;
        pushdown(u);
        int res = 0;
        int mid = tr[u].l + tr[u].r >> 1;
        if (l <= mid) res += query(ls(u),l,r);
        if (r > mid) res += query(rs(u),l,r);
        return res;
    }

    #undef ls
    #undef rs
}T;

int main(){
    n = read(),q = read(),k = read();
    for (re int i = 1;i <= n;i++){
        arr[i] = read();
        if (arr[i] == k) x = i;
    }
    T.build(1,1,n);
    while (q--){
        int op,l,r;
        op = read(),l = read(),r = read();
        if (op == 1){
            int a = T.query(1,l,r);
            if (l <= x && x <= r) x = l + a - 1;
            T.modify(1,l,l + a - 1,1); T.modify(1,l + a,r,0);
        }
        else{
            int a = (r - l + 1) - T.query(1,l,r);
            if (l <= x && x <= r) x = l + a;
            T.modify(1,l,l + a - 1,0); T.modify(1,l + a,r,1);
        }
    }
    printf("%d",x);
    return 0;
}