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;
}