【洛谷-P2839】[国家集训队]middle • TonyYin's Blog

题意#

中位数：给定一个长度为 $n$ ，下标从 $0$ 开始的序列 $a$ ，设其排序之后为 $b$ ，那么中位数为 $b_{\lfloor\frac{n}{2}\rfloor}$ .

给定一个长度为 $n$ 的，下标从 $0$ 开始的序列 $s$ ，回答 $Q$ 次形如 $(a, b, c, d)$ 的询问，表示：

在 $s$ 上取子区间 $[l, r]$，满足 $l\in[a, b]$，$r\in [c, d]$，要让子区间内的中位数最大，回答这个最大值

保证 $a_i<b_i<c_i<d_i$ ，多测，强制在线。

$1\leq n\leq 20000$ ， $1\leq Q\leq 25000$ .

分析#

由于中位数的定义中，下标从 $0$ 开始，一些细节问题需要特别考虑。

对于一个 $x$ ，把 $>=x$ 的元素赋值为 $1$ ，否则赋值为 $-1$ 。则区间元素和 $>=0$ ，当且仅当中位数 $\operatorname{mid}>=x$ .

考虑对每次询问二分。

在处理询问之前，对于每个 $x$ 预处理出一颗线段树，维护区间内的最大前缀、最大后缀、区间元素和。

在询问 $(a,b,c,d)$ 中， $[b+1,c]$ 这段是必须选的，再加上 $[a, b]$ 中的最大后缀，和 $[c,d]$ 中的最大前缀即可。

注意到离散化后，每当 $x$ 的值增加 $1$ 时，只会影响序列中的一个值，因此建立可持久化线段树。

$x$ 每增加 $1$ ，线段树只会多加一条链，空间复杂度为 $\mathcal{O}(Q\log n)$ 级别。

代码#

不难实现。

const int MAXN = 20010, inf = 0x3f3f3f3f3f3f3f3f;
int n;
struct Node{
	int v, pos;
} a[MAXN];
bool cmp(Node A, Node B) { return A.v < B.v; }
struct Point{ //可持久化线段树
	int lv, rv, sum; //区间内最大前缀和，最大后缀和，区间元素和
	int lc, rc; //左右儿子编号
} t[MAXN << 5];
int root[MAXN], p_cnt = 0;
#define ls(x) (t[x].lc)
#define rs(x) (t[x].rc)
void push_up(int rt) {
	t[rt].sum = t[ls(rt)].sum + t[rs(rt)].sum;
	t[rt].lv = max(t[ls(rt)].lv, t[ls(rt)].sum + t[rs(rt)].lv);
	t[rt].rv = max(t[rs(rt)].rv, t[rs(rt)].sum + t[ls(rt)].rv);
}
void build(int &rt, int l, int r) {
	rt = ++p_cnt;
	if(l == r) {
		//初始的 x = 0，所以每个点权值都是 1
		t[rt].lv = t[rt].rv = t[rt].sum = 1;
		return;
	}
	int mid = (l + r) >> 1;
	build(ls(rt), l, mid);
	build(rs(rt), mid + 1, r);
	push_up(rt);
}
void update(int &rt, int his, int l, int r, int x, int v) {
	//以 his 为基础进行修改，把 x -> v
	rt = ++p_cnt; t[rt] = t[his];
	if(l == r) {
		t[rt].lv = t[rt].rv = t[rt].sum = v;
		return;
	}
	int mid = (l + r) >> 1;
	if(x <= mid) update(ls(rt), ls(his), l, mid, x, v);
	else update(rs(rt), rs(his), mid + 1, r, x, v);
	push_up(rt);
}
int query_s(int rt, int l, int r, int x, int y) {
	//询问区间[x ,y]的和
	if(x <= l && r <= y) return t[rt].sum;
	int mid = (l + r) >> 1, ret = 0;
	if(x <= mid) ret += query_s(ls(rt), l, mid, x, y);
	if(y > mid) ret += query_s(rs(rt), mid + 1, r, x, y);
	return ret;
}
int query_l(int rt, int l, int r, int x, int y) {
	//询问区间[x, y]最大的前缀和
	if(x <= l && r <= y) return t[rt].lv;
	int mid = (l + r) >> 1;
	if(y <= mid) return query_l(ls(rt), l, mid, x, y); //注意要分类讨论
	else if(x > mid) return query_l(rs(rt), mid + 1, r, x, y);
	else return max(
        query_l(ls(rt), l, mid, x, mid), 
        query_s(ls(rt), l, mid, x, mid) + query_l(rs(rt), mid + 1, r, mid + 1, y)
    );
}
int query_r(int rt, int l, int r, int x, int y) {
	//询问区间[x, y]最大的后缀和
	if(x <= l && r <= y) return t[rt].rv;
	int mid = (l + r) >> 1;
	if(y <= mid) return query_r(ls(rt), l, mid, x, y);
	else if(x > mid) return query_r(rs(rt), mid + 1, r, x, y);
	else return max(
        query_r(rs(rt), mid + 1, r, mid + 1, y), 
        query_s(rs(rt), mid + 1, r, mid + 1, y) + query_r(ls(rt), l, mid, x, mid)
    );
}
bool check(int x, int a, int b, int c, int d) {
	//是否存在端点 a<=l<=b, c<=r<=d 满足 [l, r] 的元素和 >= 0
	int sum = 0;
	if(c >= b + 2) { //b, c中间有一段一定要选
		sum += query_s(root[x], 1, n, b + 1, c - 1);
	}
	sum += query_r(root[x], 1, n, a, b); //后缀 最大连续段
	sum += query_l(root[x], 1, n, c, d); //前缀 最大连续段
	return (sum >= 0);
}
signed main() {
	n = read();
	for(int i = 1; i <= n; i++) a[i].v = read(), a[i].pos = i;
	sort(a + 1, a + n + 1, cmp); //离散化
	build(root[1], 1, n);
	for(int i = 2; i <= n + 1; i++) {
		update(root[i], root[i - 1], 1, n, a[i - 1].pos, -1);
	}
	int Q = read(), lstans = 0;
	while(Q--) {
		int q[4];
		q[0] = (read() + lstans) % n + 1;
		q[1] = (read() + lstans) % n + 1;
		q[2] = (read() + lstans) % n + 1;
		q[3] = (read() + lstans) % n + 1;
		sort(q, q + 4);
		int l = 1, r = n, mid, ans = -1;
		while(l <= r) {
			mid = (l + r) >> 1;
			if(check(mid, q[0], q[1], q[2], q[3])) {
				l = mid + 1;
				ans = mid;
			} else r = mid - 1;
		}
		printf("%lld\n", a[ans].v); lstans = a[ans].v;
	}
	return 0;
}

cpp