Luogu P2824 [HEOI2016/TJOI2016]排序

传送门

给出一个1到n的全排列，求经过m次局部升/降序排序后，第q位上的数字。（n.m≤1e5）

正解是：二分答案+线段树

（？？？？WTF)

因为n很小，所以可以用二分答案枚举第q位上的数字。

把比二分的这个数mid小的数字全部改为0，其他的改为1，然后对01序列进行计数排序——即统计1的个数，然后对区间进行修改。

完成m次排序后，检查第q位是不是1；如果不是，说明0太多了，二分的数太大，将答案减小；反之亦然。

计数排序、检查第q位分别对应了线段树中的区间查询、区间覆盖、单点查询。

注意：

全为0的区间的lazy标记需要打成-1而不是0，否则会和没有标记的区间混淆。

如果查询一段区间内全是1或者全是0，则不用排序，直接continue（因为这个RE了好久）。

代码如下

#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#define MogeKo qwq
using namespace std;
const int maxn = 1e5+10;
int n,m,q,ans,a[maxn];
int l[maxn<<2],r[maxn<<2];
int sum[maxn<<2],lazy[maxn<<2];
int op[maxn],ll[maxn],rr[maxn];

void build(int L,int R,int now,int k) {
    l[now] = L, r[now] = R;
    lazy[now] = 0;
    if(L == R) {
        if(a[L] >= k) sum[now] = 1;
        else sum[now] = 0;
        return;
    }
    int mid = (L+R)>>1;
    build(L,mid,now<<1,k);
    build(mid+1,R,now<<1|1,k);
    sum[now] = sum[now<<1] + sum[now<<1|1];
}

void pushdown(int now) {
    if(lazy[now] == 0) return;
    lazy[now<<1] = lazy[now<<1|1] = lazy[now];
    sum[now<<1] = (r[now<<1]-l[now<<1]+1) * (lazy[now]==1?1:0);
    sum[now<<1|1] = (r[now<<1|1]-l[now<<1|1]+1) * (lazy[now]==1?1:0);
    lazy[now] = 0;
}

void modify(int L,int R,int now,int c) {
    if(L == l[now] && R == r[now]) {
        sum[now] = c*(R-L+1);
        lazy[now] = (c?1:-1);
        return;
    }
    pushdown(now);
    int mid = (l[now]+r[now])>>1;
    if(R <= mid) modify(L,R,now<<1,c);
    else if(L >= mid+1) modify(L,R,now<<1|1,c);
    else {
        modify(L,mid,now<<1,c);
        modify(mid+1,R,now<<1|1,c);
    }
    sum[now] = sum[now<<1] + sum[now<<1|1];
}

int query(int L,int R,int now) {
    if(L == l[now] && R == r[now]) {
        return sum[now];
    }
    pushdown(now);
    int mid = (l[now]+r[now])>>1;
    if(R <= mid) return query(L,R,now<<1);
    else if(L >= mid+1) return query(L,R,now<<1|1);
    else return query(L,mid,now<<1) + query(mid+1,R,now<<1|1);
}

bool check(int k) {
    build(1,n,1,k);
    for(int i = 1; i <= m; i++) {
        int L = ll[i];
        int R = rr[i];
        int num = query(L,R,1);
        if(num >= (R-L+1) || num <= 0) continue;
        if(op[i] == 0) {
            modify(L,R-num,1,0);
            modify(R-num+1,R,1,1);
        } else {
            modify(L,L+num-1,1,1);
            modify(L+num,R,1,0);
        }
    }
    if(query(q,q,1) == 1)return true;
    return false;
}

int main() {
    scanf("%d%d",&n,&m);
    for(int i = 1; i <= n; i++)
        scanf("%d",&a[i]);
    for(int i = 1; i <= m; i++)
        scanf("%d%d%d",&op[i],&ll[i],&rr[i]);
    scanf("%d",&q);
    int L = 1,R = n;
    while(L <= R) {
        int mid = (L+R)>>1;
        if(check(mid)) {
            ans = mid;
            L = mid+1;
        } else R = mid-1;
    }
    printf("%d",ans);
    return 0;
}