HEOI2016排序-解题报告

题目描述

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

输入输出格式

输入格式：

输入数据的第一行为两个整数n和m。n表示序列的长度，m表示局部排序的次数。1≤n,m≤105 第二行为n个整数，表示1到n的一个全排列。

接下来输入m行，每一行有三个整数op, l, r, op为0代表升序排序，op为1代表降序排序, l, r 表示排序的区间。最后输入一个整数q，q表示排序完之后询问的位置, 1≤q≤n。1≤n≤105，1≤m≤105

输出格式：

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

输入输出样例

输入样例#1：

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

输出样例#1：

题目分析

由于涉及到了区间操作且数据量为 O(nlgn) 量级，不难想到用线段树维护。然而排序该如何维护呢？

假设数据只有 “小” 和 “大” 两种，可以用0、1表示数据。若对区间 [l,r] 升序排序，则不妨按以下操作：

gt=∑ri=lai,le=(r−l+1)−gt
modify(l, l+le, 0)
modify(l+le+1, r, 1)

则可以将区间排序，而这些操作可以用lazy_tag保证 O(lgn) 的摊还复杂度。

如何将多种数据转化成只有小和大两种呢？必然要枚举这个 分界点。小于等于分界点的记为0，否则记为1。不难发现，如果对于位置q，枚举出最后一个使 aq=0 的分界点，即为 aq在排序后的值。然而这个枚举又满足偏序关系：如果 x0是一个使得aq=1的分界点，则对于任何 x≤x0，总有aq=1。因而可以二分答案求解。最终的复杂度为 O(nlg2n)。

参考代码

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;

inline int min(int a, int b)
{
    return a <= b ? a : b;
}

inline int max(int a, int b)
{
    return a >= b ? a : b;
}

struct node {
    int l, r, lc, rc, dat;
    int lazy_tag;
} tree[2000005];
int top = 0, root;

inline void push_lab(int i)
{
    if (!i || tree[i].lazy_tag == -1) return;
    tree[i].dat = tree[i].lazy_tag*(tree[i].r-tree[i].l+1);
    if (tree[i].lc) tree[tree[i].lc].lazy_tag = tree[i].lazy_tag;
    if (tree[i].rc) tree[tree[i].rc].lazy_tag = tree[i].lazy_tag;
    tree[i].lazy_tag = -1;
}

inline int read()
{
    int a = 0, c;
    do c = getchar(); while (!isdigit(c));
    while (isdigit(c)) {
        a = a*10+c-'0';
        c = getchar();
    }
    return a;
}

int dat[100005], n, m;
int qopt[100005], ql[100005], qr[100005];
int q;
inline void update(int i)
{
    push_lab(i);
    push_lab(tree[i].lc); push_lab(tree[i].rc);
    tree[i].dat = tree[tree[i].lc].dat + tree[tree[i].rc].dat;
}

inline int new_node(int l, int r)
{
    tree[++top].l = l; tree[top].r = r;
    tree[top].lc = tree[top].rc = tree[top].dat = 0;
    tree[top].lazy_tag = -1;
    return top;
}

inline void build(int &nd, int l, int r, int mid)
{
    if (l > r) return;
    nd = new_node(l, r);
    if (l < r) {
        build(tree[nd].lc, l, (l+r)>>1, mid);
        build(tree[nd].rc, ((l+r)>>1)+1, r, mid);
        update(nd);
    } else tree[nd].dat = dat[l] > mid;
}

inline void change(int nd, int l, int r, int d)
{
    if (l > r || !nd) return;
    push_lab(nd);
    if (tree[nd].l == l && tree[nd].r == r) {tree[nd].lazy_tag = d;}
    else {
        change(tree[nd].lc, l, min(tree[tree[nd].lc].r, r), d);
        change(tree[nd].rc, max(tree[tree[nd].rc].l, l), r, d);
        update(nd);
    }
}

inline int query(int nd, int l, int r)
{
    if (l > r || !nd) return 0;
    push_lab(nd);
    if (tree[nd].l == l && tree[nd].r == r) return tree[nd].dat;
    return query(tree[nd].lc, l, min(tree[tree[nd].lc].r, r)) +
           query(tree[nd].rc, max(tree[tree[nd].rc].l, l), r);
}

inline void init()
{
    scanf("%d%d", &n, &m);
    for (register int i = 1; i <= n; i++)
        dat[i] = read();
    for (register int i = 1; i <= m; i++){
        qopt[i] = read();
        ql[i] = read();
        qr[i] = read();
    }
    scanf("%d", &q);
}

inline void rebuild(int mid)
{
    top = 0;
    build(root, 1, n, mid);
}

int main()
{
    init();
    register int l = 1, r = n, mid;
    while (l <= r) {
        mid = (l+r)>>1;
        rebuild(mid);
        for (register int i = 1; i <= m; i++) {
            int larger = query(root, ql[i], qr[i]);
            int less = qr[i]-ql[i]+1-larger;
            if (qopt[i] == 0) {
                change(root, ql[i], ql[i]+less-1, 0);
                change(root, ql[i]+less, qr[i], 1);
            } else {
                change(root, ql[i], ql[i]+larger-1, 1);
                change(root, ql[i]+larger, qr[i], 0);
            }
        }
        if (query(root, q, q) == 0) r = mid-1;
        else l = mid+1;
    }
    cout << r+1 << endl;
    return 0;
}