题目地址：洛谷：【P2824】[HEOI2016/TJOI2016]排序 – 洛谷、BZOJ：Problem 4552. — [Tjoi2016&Heoi2016]排序

题目描述

在2016年，佳媛姐姐喜欢上了数字序列。因而他经常研究关于序列的一些奇奇怪怪的问题，现在他在研究一个难题，需要你来帮助他。这个难题是这样子的：给出一个1到n的全排列，现在对这个全排列序列进行m次局部排序，排序分为两种：1:(0,l,r)表示将区间[l,r]的数字升序排序2:(1,l,r)表示将区间[l,r]的数字降序排序最后询问第q位置上的数字。

题意简述

给一个1到n的排列，有两种操作：

1. 区间升序排序
2. 区间降序排序

最后一个查询，查询操作完成后第q个位置的值。

输入输出格式

输入格式：
输入数据的第一行为两个整数n和m。n表示序列的长度，m表示局部排序的次数。1 <= n, m <= 10^5第二行为n个整数，表示1到n的一个全排列。接下来输入m行，每一行有三个整数op, l, r, op为0代表升序排序，op为1代表降序排序, l, r 表示排序的区间。最后输入一个整数q，q表示排序完之后询问的位置, 1 <= q <= n。1 <= n <= 10^5，1 <= m <= 10^5

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

输入输出样例

输入样例#1：

6 3
1 6 2 5 3 4
0 1 4
1 3 6
0 2 4
3

输出样例#1：

5

题解

只有一个询问，我们考虑二分询问位置的值。暴力排序的复杂度无法比O(n)更低，那么我们考虑转化成一个01序列的排序。我们用线段树来维护这样一个01序列，原序列中不大于二分值的数设置为0，大于的设置为1。对于一个区间内，我们处理出有多少1，升序即前面一段为0后面一段为1，降序就反过来。线段树操作的复杂度都是O(\log n)的，成功降低了复杂度。在这个二分的过程中，如果该位置的值为1表示二分值不大于答案，l=mid，反之亦然。这样做的总复杂度是O(n \log^2 n)的。
有一个坑点是如果序列中不含1，那么要特殊处理，避免线段树操作出现l>r的情况。

代码

// Code by KSkun, 2018/5
#include <cstdio>
#include <cctype>  
#include <cstring>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) 
        ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    register char c = fgc();
    while(!isdigit(c)) {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(isdigit(c)) {
        res = (res << 1) + (res << 3) + c - '0';
        c = fgc();
    }
    return res * neg;
}

const int MAXN = 100005;

#define lch o << 1
#define rch o << 1 | 1

int sum[MAXN << 2], tag[MAXN << 2];

inline void pushdown(int o, int l, int r) {
    int mid = (l + r) >> 1;
    if(tag[o] != -1) {
        sum[lch] = tag[o] * (mid - l + 1);
        tag[lch] = tag[o];
        sum[rch] = tag[o] * (r - mid);
        tag[rch] = tag[o];
        tag[o] = -1;
    }
}

inline void modify(int o, int l, int r, int ll, int rr, int v) {
    if(l >= ll && r <= rr) {
        sum[o] = v * (r - l + 1);
        tag[o] = v;
        return;
    }
    pushdown(o, l, r);
    int mid = (l + r) >> 1;
    if(ll <= mid) modify(lch, l, mid, ll, rr, v);
    if(rr > mid) modify(rch, mid + 1, r, ll, rr, v);
    sum[o] = sum[lch] + sum[rch];
}

inline int query(int o, int l, int r, int ll, int rr) {
    if(l >= ll && r <= rr) {
        return sum[o];
    }
    pushdown(o, l, r);
    int res = 0;
    int mid = (l + r) >> 1;
    if(ll <= mid) res += query(lch, l, mid, ll, rr);
    if(rr > mid) res += query(rch, mid + 1, r, ll, rr);
    return res;
}

int n, m, a[MAXN], op[MAXN], l[MAXN], r[MAXN], q;

inline bool check(int x) {
    modify(1, 1, n, 1, n, 0);
    for(int i = 1; i <= n; i++) {
        if(a[i] > x) modify(1, 1, n, i, i, 1);
    }
    for(int i = 1; i <= m; i++) {
        int res = query(1, 1, n, l[i], r[i]);
        if(op[i] == 0) {
            modify(1, 1, n, l[i], r[i] - res, 0);
            if(res) modify(1, 1, n, r[i] - res + 1, r[i], 1);
        } else {
            if(res) modify(1, 1, n, l[i], l[i] + res - 1, 1);
            modify(1, 1, n, l[i] + res, r[i], 0);
        }
    }
    return query(1, 1, n, q, q);
}

int main() {
    memset(tag, -1, sizeof(tag));
    n = readint(); m = readint();
    for(int i = 1; i <= n; i++) {
        a[i] = readint();
    }
    for(int i = 1; i <= m; i++) {
        op[i] = readint(); l[i] = readint(); r[i] = readint();
    }
    q = readint();
    int l = 0, r = n, mid; 
    while(r - l > 1) {
        mid = (l + r) >> 1;
        if(check(mid)) l = mid; else r = mid;
    }
    printf("%d", r);
    return 0;
}