洛谷 P2824 分析（别看）

科技起源‍‍‍‍‍‍‍‍‍‍‍‍

2026-07-28 09:08:27

发布于：北京

5阅读

0回复

0点赞

原题链接

1 题目

1.1 题目所需求出内容

对于本题，最终要求：一个位置上的具体值

1.2 题目背景、允许、禁止与限制

背景：
有一个有 $n$ 个元素的排列（说明其中每种元素只有一个）
允许：
要进行 $m$ 次操作，每次操作有两种可能

将区间 $[l,r]$ 的数字按升序排序
将区间 $[l,r]$ 的数字按降序排序

最后求操作完成之后序列的第 $q$ 项

限制：

1.3 题目数据范围与猜测

$1 \le n, m \le 10^5 \longrightarrow O(n~log~n)$

1.4 一句话概括题意

有一个排列，求经过一些排序操作后某一特定位置元素值

2 题目破题推导

这题只会在若干操作完毕后求一次值！

3 模型匹配

那既然 “这题只会在若干操作完毕后求一次值”，那么
我们可以考虑 $\huge{线段树离线做法}$
简要概括步骤：

$\huge{二分答案}$ 猜排序操作完成后 $a_q=mid$
那check函数里面呢？
2.1. 把 $\ge mid$ 的数都赋值为 $1$
2.2. 把 $<mid$ 的数都赋值为 $0$
2.3. 回归 $\huge{线段树}$ ，维护区间和
2.4. 将 $[l,r]$ 升序排序
①查询区间和 $num=[l,r]\rightarrow$ 这一步等价于找其中有多少 $\ge mid$ 的数
②将 $[r-num+1,r]$ 修改为 $1\rightarrow$ 这一步等价于把所有 $\ge mid$ 的数放在 $mid$ 后面（这不就是升序排序吗？）
③将 $[l,r-num]$ 修改为 $0\rightarrow$ 这一步等价于把所有 $< mid$ 的数放在 $mid$ 前面（这不就是升序排序吗？）
2.5. 将 $[l,r]$ 降序排序
①查询区间和 $num=[l,r]\rightarrow$ 这一步等价于找其中有多少 $\ge mid$ 的数
②将 $[l,l+num-1]$ 修改为 $1\rightarrow$ 这一步等价于把所有 $< mid$ 的数放在 $mid$ 后面（这不就是降序排序吗？）
③将 $[l+num,r]$ 修改为 $0\rightarrow$ 这一步等价于把所有 $\ge mid$ 的数放在 $mid$ 前面（这不就是降序排序吗？）
2.6. 查询结果
所有升序降序操作结束之后查询区间 $k=[q,q]$
如果 $k=1$ ，则说明 $mid$ 猜小了（当然有可能是对的，因为前面是 $\ge$ ）
如果 $k=0$ ，则说明 $mid$ 猜大了

4 最终代码（禁止抄袭，仅用于参考）

#include <bits/stdc++.h>
using namespace std;
#define lson i<<1
#define rson i<<1|1

inline int read(){
    int num = 0;
    int f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9'){
        if (ch == '-'){
            f = -1;
        }
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9'){
        num = (num << 3) + (num << 1) + (ch ^ 48);
        ch = getchar();
    }
    return num * f;
}

int n, m;
const int N = 2e5 + 10;
int a[N];
int q;
struct node{
    int l, r;
    int sum;
    int tag;
}tree[N << 2];
struct Q{
    int op;
    int l, r;
}ques[N];
int temp[N];
inline void build(int i, int l, int r){
    tree[i].l = l;
    tree[i].r = r;
    tree[i].tag = -1;
    if (l == r){
        tree[i].sum = temp[l];
        return ;
    }
    int mid = (tree[i].l + tree[i].r) >> 1;
    build(lson, l, mid);
    build(rson, mid + 1, r);
    tree[i].sum = tree[lson].sum + tree[rson].sum;
}
inline void pushdown(int i){
    if (tree[i].tag != -1){
        tree[lson].tag = tree[rson].tag = tree[i].tag;
        int mid = (tree[i].l + tree[i].r) >> 1;
        int llen = (mid - tree[lson].l + 1), rlen = (tree[rson].r - mid);
        tree[lson].sum = tree[lson].tag * llen;
        tree[rson].sum = tree[rson].tag * rlen;
        tree[i].tag = -1;
    }
}
inline void change(int i, int l, int r, int val){
    if (tree[i].l > r || tree[i].r < l){
        return ;
    }
    if (tree[i].l >= l && tree[i].r <= r){
        tree[i].tag = val;
        tree[i].sum = val * (tree[i].r - tree[i].l + 1);
        return ;
    }
    pushdown(i);
    if (tree[lson].r >= l){
		change(lson, l, r, val);
	}
	if (tree[rson].l <= r){
		change(rson, l, r, val);
	}
    tree[i].sum = tree[lson].sum + tree[rson].sum;
}
inline int query(int i, int l, int r){
    if (tree[i].l > r || tree[i].r < l){
        return 0;
    }
    if (tree[i].l >= l && tree[i].r <= r){
        return tree[i].sum;
    }
    pushdown(i);
    int ret = 0;
    ret += query(lson, l, r);
    ret += query(rson, l, r);
    return ret;
}
inline int check(int mid){
    for (int i = 1;i <= n;i++){
        if (a[i] >= mid){
            temp[i] = 1;
        } else {
            temp[i] = 0;
        }
    }
    build(1, 1, n);
    for (int i = 1;i <= m;i++){
        if (ques[i].op == 0){
            int l = ques[i].l, r = ques[i].r;
            int num = query(1, l, r);
            change(1, r - num + 1, r, 1);
            change(1, l, r - num, 0);
        } else {
            int l = ques[i].l, r = ques[i].r;
            int num = query(1, l, r);
            change(1, l, l + num - 1, 1);
            change(1, l + num, r, 0);
        }
    }
    int get = query(1, q, q);
    return get;
}

int main(){

    n = read(), m = read();
    for (int i = 1;i <= n;i++){
        a[i] = read();
    }
    for (int i = 1;i <= m;i++){
        ques[i].op = read(), ques[i].l = read(), ques[i].r = read();
    }
    q = read();
    int left = 1, right = n, ans = 0;
    while(left <= right){
        int mid = (left + right) / 2;
        if (check(mid) == 1){
            ans = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    printf("%d", ans);
    
    return 0;
}