[Luogu2824] [HEOI2016/TJOI2016]排序

题目描述

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

说明

河北省选2016第一天第二题。原题的时限为6s，但是洛谷上是1s，所以洛谷的数据中，对于30%的数据，有 n,m<=1000,对于100%的数据，有 n,m<=30000

二分答案的大小mid。

大于等于mid设为1，其余的设为0.

这样可以用线段树实现$\large O(logN)$排序。

这样排序结束之后如果位置p是1，就增大l，否则减小r。

#include <iostream>

#include <cstdio>

using namespace std;

#define reg register

inline int read() {

    int res = ;char ch=getchar();

    while(!isdigit(ch)) ch=getchar();

    while(isdigit(ch)) res=(res<<)+(res<<)+(ch^), ch=getchar();

    return res;

}

#define N 100010

int n, m, p, erf;

int ans;

int a[N];

struct Que {

    int l, r, opt;

}q[N];

int cnt[N*], lazy[N*];

#define ls(o) o << 1

#define rs(o) o << 1 | 1

inline void pushup(int o)

{

    cnt[o] = cnt[ls(o)] + cnt[rs(o)];

}

void Build(int l, int r, int o)

{

    lazy[o] = -;

    if (l == r)

    {

        cnt[o] = (a[l] >= erf);

        lazy[o] = -;

        return ;

    }

    int mid = l + r >> ;

    Build(l, mid, ls(o));

    Build(mid + , r, rs(o));

    pushup(o);

}

//lazy : 1) -1 means none

// 2) 1 means change to 1

// 3) 0 means change to 0

inline void pushdown(int l, int r, int o)

{

    if (lazy[o] == -) return ;

    int mid = l + r >> ;

    if (lazy[o] == ) {

        cnt[ls(o)] = mid - l + ;

        lazy[ls(o)] = ;

        cnt[rs(o)] = r - mid;

        lazy[rs(o)] = ;

        lazy[o] = -;

    } else {

        cnt[ls(o)] = , lazy[ls(o)] = ;

        cnt[rs(o)] = , lazy[rs(o)] = ;

        lazy[o] = -;

    }

}

void change(int l, int r, int o, int ql, int qr, int c)

{

    if (l >= ql and r <= qr) {

        if (c) cnt[o] = r - l + , lazy[o] = ;

        else cnt[o] = , lazy[o] = ;

        return;

    }

    pushdown(l, r, o);

    int mid = l + r >> ;

    if (ql <= mid) change(l, mid, ls(o), ql, qr, c);

    if (qr > mid) change(mid + , r, rs(o), ql, qr, c);

    pushup(o);

}

int query(int l, int r, int o, int ql, int qr)

{

    if (l >= ql and r <= qr) return cnt[o];

    pushdown(l, r, o);

    int mid = l + r >> ;

    int res = ;

    if (mid >= ql) res += query(l, mid, ls(o), ql, qr);

    if (mid < qr) res += query(mid + , r, rs(o), ql, qr);

    return res;

}

inline bool check(int mid)

{

    erf = mid;

    Build(, n, );

//    printf("mid = %d\n", mid);

    for (reg int i =  ; i <= m ; i ++)

    {

        int L = q[i].l, R = q[i].r;

        int c = query(, n, , L, R);

        if (q[i].opt == ) { //升序

            change(, n, , R - c + , R, );

            change(, n, , L, R - c, );

        } else {

            change(, n, , L, L + c - , );

            change(, n, , L + c, R, );

        }

    }

//    printf("%d\n", query(1, n, 1, p, p));

    return query(, n, , p, p);

}

int main()

{

    n = read(), m = read();

    for (reg int i =  ; i <= n ; i ++) a[i] = read();

    for (reg int i =  ; i <= m ; i ++) q[i].opt = read(), q[i].l = read(), q[i].r = read();

    p = read();

    int l = , r = n;

    while (l <= r)

    {

        int mid = l + r >> ;

        if (check(mid)) ans = mid, l = mid + ;

        else r = mid - ;

    }

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

    return ;

}

巴特西

[Luogu2824] [HEOI2016/TJOI2016]排序

题目描述

输入输出格式

输入输出样例

说明

最新文章

热门文章