线段树好题！ P2824 [HEOI2016/TJOI2016]排序 题解

· · 个人记录

更好的阅读体验

题目传送门

前言

线段树好题！！！！ 咕咕了挺久的一道题目，很早之前就想写了，今天终于找了个时间A掉了。

题意

给定一个 1 到 n 的排列，有 m 次操作，分两种类型。

1.0 l r表示将下标在 [l, r] 区间中的数升序排序。

2.1 l r表示将下标在 [l, r] 区间中的数降序排序。 给定一个数 q 询问最后 q 位置上的数。

Solution

看到数据范围，发现前 30 分是可以暴力的，这里不多赘述。

注意到 n,m\leqslant 10^5 ,优先考虑 O(nlogn) 或 O(n \sqrt n) 做法。对一个序列进行操作，自然想到，线段树，但是线段树不支持区间排序那怎么办呢。

考虑对一段 01 串做排序，显然排完序后会变成 00011 或 11100 这种形式，可以用线段树的区间推平和求和操作来完成。

但是原序列不是 01 串，我们就要把它转换成 01 串。

可以选取一个基准数，让原序列大于等于这个数的都变成 1 ，其他的都是 0 就能解决这个问题了。

如果操作完之后 q 上的是 1 ，说明答案至少是大于等于这个基准数的，所以二分就行了。

总复杂度 O(n log^2n)。

code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5, INF = 0x3f3f3f3f;
const ll mod = 1e9 + 7;
int n, m, pos;
int a[N];
struct question
{
    int op, l, r;
} Q[N];
struct segment_tree
{
    int l, r, val, tag;
    #define l(x) tr[x].l
    #define r(x) tr[x].r
    #define val(x) tr[x].val
    #define tag(x) tr[x].tag
} tr[N << 2];
void pushup(int x)
{
    val(x) = val(x << 1) + val(x << 1 | 1);
}
void pushdown(int x)
{
    if(tag(x) == -1) return;
    val(x << 1) = (r(x << 1) - l(x << 1) + 1) * tag(x);
    tag(x << 1) = tag(x);
    val(x << 1 | 1) = (r(x << 1 | 1) - l(x << 1 | 1) + 1) * tag(x);
    tag(x << 1 | 1) = tag(x);
    tag(x) = -1;
}
void build(int l, int r, int x, int v)
{
    l(x) = l, r(x) = r, tag(x) = -1, val(x) = 0;
    if(l == r)
    {
        val(x) = (a[l] >= v);
        return;
    }
    int mid = l + r >> 1;
    build(l, mid, x << 1, v), build(mid + 1, r, x << 1 | 1, v);
    pushup(x);
}
void update(int l, int r, int x, int v)
{
    if(l <= l(x) && r(x) <= r)
    {
        tag(x) = v;
        val(x) = (r(x) - l(x) + 1) * v;
        return;
    }
    pushdown(x);
    int mid = l(x) + r(x) >> 1;
    if(l <= mid) update(l, r, x << 1, v);
    if(r > mid) update(l, r, x << 1 | 1, v);
    pushup(x);
}
int query(int l, int r, int x)
{
    if(l <= l(x) && r(x) <= r) return val(x);
    pushdown(x);
    int mid = l(x) + r(x) >> 1, res = 0;
    if(l <= mid) res += query(l, r, x << 1);
    if(r > mid) res += query(l, r, x << 1 | 1);
    return res;
}
int check(int v)
{
    build(1, n, 1, v);
    for(int i = 1;i <= m;i ++)
    {
        int l = Q[i].l, r = Q[i].r, op = Q[i].op;
        int sum = query(l, r, 1);
        if(sum == 0) continue;
        update(l, r, 1, 0);
        if(op == 0) update(r - sum + 1, r, 1, 1);
        else update(l, l + sum - 1, 1, 1);
    }
    return query(pos, pos, 1);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    for(int i = 1;i <= n;i ++) cin >> a[i];
    for(int i = 1;i <= m;i ++) cin >> Q[i].op >> Q[i].l >> Q[i].r;
    cin >> pos;
    int l = 1, r = n, res;
    while(l <= r)
    {
        int mid = l + r >> 1;
        if(check(mid)) l = mid + 1, res = mid;
        else r = mid - 1;
    }
    cout << res << '\n';
    return 0;
}