BZOJ4552 - [Tjoi2016&Heoi2016]排序

2017/11/01

题目

在2016年,佳媛姐姐喜欢上了数字序列。因而他经常研究关于序列的一些奇奇怪怪的问题,现在他在研究一个难题 ,需要你来帮助他。这个难题是这样子的:给出一个 1 到 n 的全排列,现在对这个全排列序列进行 m 次局部排序,排 序分为两种:

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

最后询问第 q 位置上的数字。

做法

注意到只有一个询问。

我们可以二分答案,然后把原序列小于答案的换成 0, 大于等于答案的换成 1 。

对这个 01 序列排序和对原序列排序的效果相同,最后求出最小的使位置 q 为 1 的值即为答案。

而对 01 序列的排序可以通过线段树维护。

代码

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cassert>
using namespace std;
const int SIZ = 1e5 + 2007;

int N, M, P;
int S[SIZ];
struct op {
    int s, l, r;
} Q[SIZ];

int W;
void initseg(int C) {
    for(W=1;W<=C;W<<=1);
}

int sum[SIZ<<2], lzy[SIZ<<2];
#define ls(x) ((x) << 1)
#define rs(x) (ls(x) | 1)

void push_down(int x, int l) {
    if(x < W && lzy[x] != -1) {
        sum[ls(x)] = sum[rs(x)] = lzy[x] * (l>>1);
        lzy[ls(x)] = lzy[rs(x)] = lzy[x];
    }
    lzy[x] = -1;
}

int query(int ql, int qr, int l = 1, int r = W, int x = 1) {
    if(ql == l && r == qr)
        return sum[x];
    
    push_down(x, r - l + 1);
    int mid = (l + r) >> 1;
    if(qr <= mid)
        return query(ql, qr, l, mid, ls(x));
    else if(ql > mid)
        return query(ql, qr, mid+1, r, rs(x));
    else
        return query(ql, mid, l, mid, ls(x)) +
            query(mid+1, qr, mid+1, r, rs(x));
}

void change(int c, int ql, int qr, int l = 1, int r = W, int x = 1) {
    if(ql > qr) return;

    push_down(x, r - l + 1);

    if(ql == l && qr == r) {
        lzy[x] = c;
        sum[x] = c * (r - l + 1);
        return;
    }

    int mid = (l + r) >> 1;
    
    if(qr <= mid) change(c, ql, qr, l, mid, ls(x));
    else if(ql > mid) change(c, ql, qr, mid+1, r, rs(x));
    else
        change(c, ql, mid, l, mid, ls(x)),
        change(c, mid+1, qr, mid+1, r, rs(x));

    sum[x] = sum[ls(x)] + sum[rs(x)];
}

int check(int x) {
    fill(sum, sum+(SIZ<<2), 0);
    fill(lzy, lzy+(SIZ<<2),-1);

    for(int i=1;i<=N;i++) change(S[i] >= x, i, i);

    for(int i=1,t;i<=M;i++) {
        t = query(Q[i].l, Q[i].r);

        if(!Q[i].s) {
            change(0, Q[i].l, Q[i].r - t);
            change(1, Q[i].r - t + 1, Q[i].r);
        } else {
            change(1, Q[i].l, Q[i].l + t - 1);
            change(0, Q[i].l + t, Q[i].r);
        }
    }

    return query(P, P);
}

int main() {
    scanf("%d %d", &N, &M);

    for(int i=1;i<=N;i++)
        scanf("%d", &S[i]);

    for(int i=1;i<=M;i++) {
        scanf("%d %d %d", &Q[i].s, &Q[i].l, &Q[i].r);
    }

    scanf("%d", &P);

    initseg(N);

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

    printf("%d\n", ans);
}