题解-学习心得

ymhh

2026-10-19 09:29:53

发布于：广东

5阅读

0回复

0点赞

P2824 [HEOI2016/TJOI2016] 排序

一、题意

自行理解。

二、思路

1、观察

题目没有要求输出整个序列，而是询问单点，猜想可能不用知道整个序列即可。
可以转换二分。二分需要一个判定，设最终 $q$ 位置的真实值为 $v$ ，令 $\text{check}(x)$ 表示 $q$ 位置上的值是否 $\ge x$ 。当 $x\le v$ 时， $v\ge x$ ， $\text{check}(x)$ 为真；当 $x>v$ 时， $v<x$ ， $\text{check}(x)$ 为假。所以可行 $x$ 的集合是前缀 $[1,v]$ ，具有单调性， $\color{#6BCB77}{\text{考虑如何判定}}$ 。
可以令 $\text{check}(x)$ 表示 $q$ 位置上的值是否 $\ge x$ ，接下来要解决的是 $\color{#4DD0E1}{\text{这个判定怎么快速算}}$ 。
既然判定只依赖元素和 $x$ 的大小关系，而排序又难以直接维护，不如把序列按阈值 $x$ 二值化，也就是 $\color{#6BCB77}{\text{01 转化}}$ ： $a_i\ge x$ 记 $1$ ，否则记 $0$ 。这样排序就变得简单了。

2、细节

整个 $01$ 数组是这样求出的：令 $a_i< x$ 为 $0$ ，否则为 $1$ ；这样后续判断 $q$ 位置是否为 $1$ 即可。

$01$ 序列排序只需 $\color{#4DD0E1}{\text{数区间内 } 1 \text{ 的个数 } cnt}$ ：升序把 $[l,r-cnt]$ 赋 $0$ 、 $[r-cnt+1,r]$ 赋 $1$ ；降序把 $[l,l+cnt-1]$ 赋 $1$ 、 $[l+cnt,r]$ 赋 $0$ 。 $\color{#6BCB77}{\text{一次排序变成一次区间查询加两次区间赋值}}$ ，线段树维护区间和与区间覆盖即可。

二分时 $\text{check}(x)$ 为真则 $l=\text{mid}+1$ ， $\color{#FF6B6B}{\text{找最大可行 } x}$ ，它就是 $v$ 。

3、时间复杂度

每次 $\text{check}(x)$ 为 $O(n+m\log n)$ ，二分 $O(\log n)$ 次，总复杂度为 $\mathcal{O}((n+m)\log^2 n)$ ，可以通过。

4、易错点

$\color{#FF9F43}{\text{二分方向}}$ ： $\text{check}$ 为真时 $l=\text{mid}+1$ ，找最大可行 $x$ 。
$\color{#FF9F43}{\text{懒标记}}$ 要区分“无标记”和“赋 $0$ ”，建议用 $-1$ 表示无标记。
$\color{#FF9F43}{\text{推平前判区间非空}}$ ，避免 $l>r$ 时越界。

三、代码

#include<iostream>
#define ls 2*u
#define rs 2*u+1
using namespace std;
const int N = 1e5;
struct option{int op,l,r;}box[N+5];
int n,num,q,a[N+5],sol[N+5];

struct Seg_tree
{
	int sum[N*4],tag[N*4];
	
	void seg_sol(int u)
	{
		sum[u] = sum[ls]+sum[rs];
	}
	
	void build(int u,int l,int r)
	{
		tag[u] = -1;
		
		if(l==r) 
		{
			sum[u] = sol[l];
			return ;
		}
		
		int mid = (l+r)>>1;
		build(ls,l,mid);
		build(rs,mid+1,r);
		seg_sol(u);
	}
	
	void apply(int u,int l,int r,int val)
	{
		tag[u] = val;
		sum[u] = (r-l+1)*val;
	}
	
	void pushdown(int u,int l,int r)
	{
		if(tag[u]==-1) return ;
		
		int mid = (l+r)>>1;
		
		apply(ls,l,mid,tag[u]);
		apply(rs,mid+1,r,tag[u]);
		
		tag[u] = -1;
	}
	
	void update(int u,int l,int r,int ql,int qr,int val)
	{
		if(r<ql||l>qr) return ;
		if(ql<=l&&r<=qr)
		{
			apply(u,l,r,val);
			return ;
		}
		
		int mid = (l+r)>>1;
	
		pushdown(u,l,r);
		update(ls,l,mid,ql,qr,val);
		update(rs,mid+1,r,ql,qr,val);
		
		seg_sol(u);
	}
	
	int query(int u,int l,int r,int ql,int qr)
	{
		if(r<ql||l>qr) return 0;
		if(ql<=l&&r<=qr) return sum[u];
		
		int mid = (l+r)>>1;
		
		pushdown(u,l,r);
		return query(ls,l,mid,ql,qr)+query(rs,mid+1,r,ql,qr);
	}
}xt;

bool check(int mid)
{
	for(int i=1;i<=n;i++)
	{
		if(a[i]>=mid) sol[i] = 1;
		else sol[i] = 0;
	}
	
	xt.build(1,1,n);
	for(int i=1;i<=num;i++)
	{
		int op = box[i].op,l = box[i].l,r = box[i].r;
		int cnt = xt.query(1,1,n,l,r);
		
		if(l>r) continue;
		
		if(op==0)
		{
			xt.update(1,1,n,l,r-cnt,0);
			xt.update(1,1,n,r-cnt+1,r,1);
		}
		else
		{
			xt.update(1,1,n,l,l+cnt-1,1);
			xt.update(1,1,n,l+cnt,r,0);
		}
	}
	
	return xt.query(1,1,n,q,q)==1;
}

int main()
{
	cin>>n>>num;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=num;i++)
	{
		int op,l,r;
		cin>>op>>l>>r;
		
		box[i] = {op,l,r};
	}
	cin>>q;
	
	int l = 1;
	int r = n+1;
	while(r-l>1)
	{
		int mid = (l+r)>>1;
		
		if(check(mid)) l = mid;
		else r = mid;
	}
	
	cout<<l;
	return 0;
}