CF101234A Hacker Cups and Balls【二分+线段树】

发布时间 2023-06-01 18:35:38作者: DTTTTTTT-

Description

给一个长度为 n 的排列,对它做 m 次操作,每次对 [l, r] 区间内进行升序/降序排序。

问最后的序列处于最中心的数是多少(n为奇数)。

Solution

是一类没有写过的题,参考题解

二分答案,对于当前的 mid ,将大于等于 mid 的数设置为 1,小于 mid 的数设置为 0。这样一来,叶结点的值只有 0/1,区间操作时也可以直接对部分区间赋值为 1,部分区间赋值为0。最后单点查询中间值是否为1即可。

具体来说,对于一次升序的区间操作 [l,r],先建树,并且查询其中1的数目sum。将[r-sum+1, r]的区间赋值为 1 ,[l, r-sum] 赋值为0。注意判断区间的合法性(\(l\leq r\))。降序操作类似。

所以,我们需要支持的线段树操作只有区间求和、区间修改(改为0/1)。

关于 tag 的设置:为了方便,tag = 0 代表该区间需要全部覆盖为0,tag = 1代表该区间需要全部覆盖为1,tag = -1表示无需pushdown。

Code

// By DTTTTTTT 2023/6/1 六一快乐!
/*
* dtt每次都写错的线段树易错点小结:
* 1. 计算mid的时候只有build中是直接使用 l+r>>1,update和query中都是 t[p].l+t[p].r>>1;
* 2. update的末尾记得 t[p].sum=t[lc].sum+t[rc].sum
* 3. update和query的 l 与 r 是不需要改变/收缩范围的,如果改变需要讨论,会很容易错
* 4. pushdown中记得写直接return的两种情况(叶结点、没有tag)
* 
* 小结一下线段树的各个操作流程:
* 1. build(int p,int l,int r):
	建树,需要初始化node的l/r/tag,叶结点直接赋sum并返回,非叶结点继续向下建树,建完后累加sum。
* 2. query(int p,int l,int r):
	若p结点的区间完全被涵盖在[l,r]区间中,直接返回其sum;
	否则需要向下计算,先pushdown,然后分别看左右两个子区间是否与[l,r]有重合,有则需计算。
	int ret=0, mid=t[p].l+t[p].r>>1;
	if(l<=mid) ret+=query(p<<1,l,r); //这里的l与r无需改变
	if(r>mid) ret+=query(p<<1|1,l,r); 
	return ret;
* 3. update(int p,int l,int r,int val)://这里以将[l,r]区间内所有数变为val这个更新操作为例
	若p结点的区间完全被涵盖在[l,r]区间中,直接更新sum并标记tag;
	否则需要向下更新,先pushdown,然后分别看左右两个子区间是否与[l,r]有重合,有则需更新。
	最后一定记得更新当前结点的sum。
	int mid=t[p].l+t[p].r>>1;
	if(l<=mid) update(p<<1,l,r,val);
	if(r>mid) update(p<<1|1,l,r,val);
	t[p].sum=t[p<<1].sum+t[p<<1|1].sum;
* 4. pushdown(int p):只需pushdown一层,无需递归操作
	首先判断无需pushdown的情况:叶结点或者没有打lazy_tag
	判断完毕后更新两个子区间的sum和tag
	最后一定记得将自己的tag取消
	t[p<<1].sum =..... ,t[p<<1|1].sum=...,t[p<<1].tag=t[p<<1|1].tag=t[p].tag;
	t[p].tag = -1; //假设这里-1代表没有

	其实觉得query和update的操作特别像,都是若全都包含在内则直接处理并返回,不然就要向下走。
	特别注意的是update向下更新完毕后记得更新自己的sum。
*/
#include<iostream>
#define lc (p<<1)
#define rc (p<<1|1)
using namespace std;
const int N = 1e5 + 5;
int n, m, a[N], b[N];
struct interval {
	int l, r, op;
}inte[N];
struct node {
	int l, r, sum, tag;
}t[N << 2];
void build(int p, int l, int r) {
	t[p].l = l, t[p].r = r, t[p].tag = -1;
	if (l == r) {
		t[p].sum = b[l];
		return;
	}
	int mid = l + r >> 1;
	build(lc, l, mid);
	build(rc, mid + 1, r);
	t[p].sum = t[lc].sum + t[rc].sum;
}
void pushdown(int p) {
	if (t[p].l == t[p].r || t[p].tag == -1) //无需pushdown的两种情况
		return;
	t[lc].tag = t[rc].tag = t[p].tag;
	t[lc].sum = (t[lc].r - t[lc].l + 1) * t[p].tag;
	t[rc].sum = (t[rc].r - t[rc].l + 1) * t[p].tag;
	//t[p].sum = t[lc].sum + t[rc].sum; 这里可以没有
	t[p].tag = -1;
}
int query(int p, int l, int r) {
	if (t[p].l >= l && t[p].r <= r)
		return t[p].sum;
	pushdown(p);
	int mid = t[p].l + t[p].r >> 1, ret = 0;
	//永远都会写错成 mid=l+r>>1 啊啊啊!!!!!!!rem!!!
	if (l <= mid)
		ret += query(lc, l, r); //这里的l与r无需改变
	if (r > mid)
		ret += query(rc, l, r);
	return ret;
}
void update(int p, int l, int r, int val) {
	if (l > r)
		return;
	if (t[p].l >= l && t[p].r <= r) {
		t[p].sum = (t[p].r - t[p].l + 1) * val;
		t[p].tag = val;
		return;
	}
	pushdown(p);
	int mid = t[p].l + t[p].r >> 1;
	if (l <= mid)
		update(lc, l, r, val);
	if (r > mid)
		update(rc, l, r, val);
	t[p].sum = t[lc].sum + t[rc].sum; //这里不能落
}
bool check(int mid) {
	for (int i = 1;i <= n;++i)
		b[i] = (a[i] >= mid);
	build(1, 1, n);
	for (int i = 1;i <= m;++i) {
		int l = inte[i].l, r = inte[i].r, op = inte[i].op;
		int sum = query(1, l, r);
		if (op == 1) //升序
			update(1, l, r - sum, 0), update(1, r - sum + 1, r, 1);
		else
			update(1, l, l + sum - 1, 1), update(1, l + sum, r, 0);
	}
	return query(1, n / 2 + 1, n / 2 + 1);
}
int main() {
	ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);

	cin >> n >> m;
	for (int i = 1;i <= n;++i) cin >> a[i];
	for (int i = 1;i <= m;++i) {
		cin >> inte[i].l >> inte[i].r;
		if (inte[i].l > inte[i].r)
			swap(inte[i].l, inte[i].r), inte[i].op = 2; //降序
		else
			inte[i].op = 1; //升序
	}

	int l = 1, r = n, mid, ans = -1;
	while (l <= r) {
		mid = l + r >> 1;
		if (check(mid)) 
			ans = mid, l = mid + 1;
		else 
			r = mid - 1;
	}

	cout << ans << endl;

	return 0;
}