HDU 5649 DZY Loves Sorting

题目传送门

视频讲解

一、题目大意

给一个序列， 两种操作， 一种是将\([l, r]\)里所有数升序排列， 一种是降序排列。
所有操作完了之后， 问你\(a[k]\)等于多少。

二、解题过程

因为最后只询问一个位置， 所以我们二分这个位置的值。 将所有大于等于它的值赋为\(1\)， 小于的赋为\(0\). 然后现在整个序列只有\(01\)，更改什么的线段树就很好搞。
如果\(a[k]\)最后为\(1\)， 那么我们增加\(l\)， 否则减少\(r\)。

那么为什么可以这样呢。
因为二分\(mid\)的时候， 将等于\(mid\)的也赋为了\(1\)， 所以如果\(a[k]\)是\(0\)的话，代表\(mid\)比答案大， 所以减少\(r\)。
那么\(a[k]\)为\(1\)的时候有两种， 一种是\(mid\)刚好是答案， 另一种是\(mid\)比答案小， 所以我们增大\(l\)逼近答案。

三、实现代码

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
//宏定义左右儿子
#define ls u << 1
#define rs (u << 1) | 1
using namespace std;
const int N = 2e5 + 5;
int n, m, k;

struct Query {
    int op, l, r;
} q[N];

int a[N];

struct Node {
    int l, r;
    int val; // 0:升序 1：降序 -1:无操作
    int sum;
} tr[N << 2];

//线段树取管辖区间长度，适用于lazy tag统一变化时sum的快速计算
int len(int u) {
    return tr[u].r - tr[u].l + 1;
}

//向父节点更新信息，写成Node &的方式目前看来是最合理的办法
void pushup(Node &c, Node &a, Node &b) {
    c.sum = a.sum + b.sum;
}

//更新lazy tag标识
void pushdown(int u) {
    if (tr[u].val == -1) return;         //如果没有下传标识，啥也不干
    tr[ls].sum = len(ls) * tr[u].val;    //如果有下传标识，左儿子区间内所有数字都要加上tr[u].add,sum值为累加
    tr[rs].sum = len(rs) * tr[u].val;    //如果有下传标识，右儿子区间内所有数字都要加上tr[u].add,sum值为累加
    tr[ls].val = tr[rs].val = tr[u].val; //左右儿子都修改标识为val,一次只更新一层
    tr[u].val = -1;                      //标识已处理
}

//构建线段树,x:当前两分取到的值，用于建立线段树时判断每个叶子的初始值是1还是0
// a[l]>=x tr[u].sum=1
// a[l]= x; //大于等于x的都设置为1,小于x的设置为0
        return;
    }
    int mid = (l + r) >> 1;
    build(ls, l, mid, x), build(rs, mid + 1, r, x);
    //更新父节点信息
    pushup(tr[u], tr[ls], tr[rs]);
}

//查询区间内数字1的个数
int query(int u, int l, int r) {
    if (l > tr[u].r || r < tr[u].l) return 0;           //不在范围内的返回0
    if (l <= tr[u].l && r >= tr[u].r) return tr[u].sum; //命中直接返回
    // lazy tag下传
    pushdown(u);
    //计算左儿子结果+右儿子结果
    return query(ls, l, r) + query(rs, l, r);
}

//区间修改
void modify(int u, int l, int r, int v) {
    //特判边界，防止越界
    if (l > r) return;
    //如果命中区间，对区间的lazy tag和sum进行计算修改
    if (l <= tr[u].l && r >= tr[u].r) {
        tr[u].val = v;
        tr[u].sum = v * len(u);
        return;
    }
    //没有命中区间，需要递归向左右儿子传递修改消息
    pushdown(u);
    //修改左区间
    if (l <= tr[ls].r) modify(ls, l, r, v);
    //修改右区间
    if (r >= tr[rs].l) modify(rs, l, r, v);
    //因为子区间内容修改，需要向父节点更新统计信息
    pushup(tr[u], tr[ls], tr[rs]);
}

bool check(int x) {
    //每次本新构建线段树
    build(1, 1, n, x);
    //根据输入排序的次序，范围，由大到小：1 ，由小到大：0
    for (int i = 1; i <= m; i++) {
        int l = q[i].l, r = q[i].r, op = q[i].op;
        //到一个大于等于x就是1，小于x就是0的线段树中去查找
        int c = query(1, l, r); //查询l,r之间数字1的个数
        if (op == 1)            //由大到小排序,所有1在前，所有0在后
            modify(1, l, l + c - 1, 1), modify(1, l + c, r, 0);
        else //由小到大排序,所有0在前，所有1在后
            modify(1, l, r - c, 0), modify(1, r - c + 1, r, 1);
    }
    //如果这面这样折腾完，第k个位置上还是1，就说明没有出现矛盾
    return query(1, k, k) == 1;
}
int main() {
    //优化读入
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int T;
    cin >> T;
    while (T--) {
        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;

        //查询第k个位置上的数字是多少
        cin >> k;

        int l = 1, r = n; //左右边界，最小是1，最大是n
        while (l <= r) {
            //假设第k个位置上的数为mid，看看会发生什么
            int mid = (l + r) >> 1; //二分查找
            if (check(mid))         //如果mid符合条件
                l = mid + 1;        //似乎由于check是用==作为判断条件的，l不能取到mid,需要二刷时仔细思考下
            else
                r = mid - 1;
        }
        printf("%d\n", l - 1);
    }
    return 0;
}
二分答案线段树

相关

#直径，线段树#51nod 1766 树上的最远点对

「NOI2020」命运（树形DP+线段树合并）

线段树学习笔记 1

关于 线段树 的一些认识

线段树

[NOI2015]软件包管理器（巧用线段树）

P6242 【模板】线段树 3

P5494 【模板】线段树分裂

CF1557D Ezzat and Grid（线段树）

cf739 C. Alyona and towers（线段树）

可持久化线段树

Codeforces Round #625 Div1 C,二维偏序，排序+线段树

标签