题意
给你一个长度 n 的数列 a[]，然后再给你 q 个询问（强制在线），每个询问给出 a, b, c, d 四个正整数，让你求 l 在 [a, b] 之间、r 在 [c, d] 的子序列 [l, r] 中的最大中位数（中位数向下取整）。
题目链接：洛谷
思路
这道题有点无从下手，先离散化 a，假设 [l, r] 是确定的，设区间总长度为 m，那我们先二分一个中位数 mid 吧。然后我们就查询在 [l, r] 中小于 mid 的数的数量 k，如果 $k \leq \frac{1}{2}m$，那么 mid 可以继续增大，则往右边二分；否则就往左边二分。
如果区间是固定的，那么这道题就很好做，但是它可变的，这就意味着即使 mid 不变，$k \leq \frac{1}{2}m$ 的情况可能随着 [l, r] 的改变而改变，这时我们只要找到一个 [l, r] 使 $k \leq \frac{1}{2}m$ 为 true，就说明 mid 使合法的，可以往右边二分。
一个比较朴素的办法就是枚举 [l, r]，但是这样会 TLE。
我们可以换个思路，如果 $k \leq \frac{1}{2}m$，就说明 $k \leq m-k$，所以我们只要判断是否存在一个 [l, r]，使得 $k \leq m-k$，即小于 mid 的数的数量小于等于比 mid 大或等于的数的数量。
我们继续假设 [l, r] 是固定的，然后稍微修改我们的线段树，在第 i 个版本时，如果 $a[j] < i$，那么第 j 位就为 -1，否则为 1。这样的话，我们查询 [l, r] 区间的和 sum，如果 $sum \geq 0$，就说明 $k \leq m-k$。
如果 [l, r] 是可变的，那么我们要在 [l, r] 中取一个和最大的区间，如果 $sum \geq 0$，那么就说明存在一个区间使 $k \leq m-k$ 为 true，所以 mid 为合法的。
要求最大和，我们可以可以按 a, b, c, d 把它分成 3 个区间，其中中间的一段肯定要取的，然后第 1 个区间就去最大后缀和，第 3 个区间就去最大前缀和，然后三个和的和就是 sum 的最大值。
最大前缀和 & 后缀和
这部分内容是写给像我这种不会求最大前缀和 & 后缀和的人的，如果你会，则可以跳过该节内容。
最大前缀和可以用线段树做，正好于上面的可持久化线段树相融，不用新增代码。
我们在每一个节点保存它的最大前缀和 prefix 和它自身的和 sum。
线段树肯定是从下往上合并的，并且最下层的节点的最大前缀和为 max(value, 0)，对于上面的节点，最大前缀和为左孩的最大前缀和与左孩和加上右孩的最大前缀和的最大值，即 max(lc.prefix, lc.sum + rc.prefix)。
对于查询，如图，我们就把一个区间分解成若干个完整的区间。然后就从左到右像上面那样把它们合并起来就可以了。
void Maintain(const int root) {
node[root].sum = node[node[root].lc].sum + node[node[root].rc].sum;
node[root].pre = max(node[node[root].lc].pre, node[node[root].lc].sum + node[node[root].rc].pre);
node[root].suf = max(node[node[root].rc].suf, node[node[root].rc].sum + node[node[root].lc].suf);
}
struct ANS { int fix, sum; };
ANS queryPrefix(const int rt, const int s, const int t, const int l, const int r) {
if (s <= l && r <= t) return (ANS){ node[rt].pre, node[rt].sum };
int mid = (l + r) >> 1;
if (t > mid && s <= mid) {
ANS a = queryPrefix(node[rt].lc, s, t, l , mid),
b = queryPrefix(node[rt].rc, s, t, mid+1, r );
return (ANS){ max(a.fix, a.sum + b.fix), a.sum + b.sum };
}
else if (s <= mid) return queryPrefix(node[rt].lc, s, t, l , mid);
else return queryPrefix(node[rt].rc, s, t, mid+1, r );
}
对于最大后缀和，像上面依样画葫芦即可。
代码
以下都是代码，没有其它内容，不必往下翻看。
#include <algorithm>
#include <cstdio>
using std::sort;
using std::max;
const int MAXN = 20010;
const int MAXT = 360010;
struct NODE { int lc, rc, sum, pre, suf; } node[MAXT];
int pool=2, root[MAXN];
int n, m, src[MAXN], srt[MAXN], ans=0;
int AllocNode(const int old) {
node[pool] = node[old];
return pool ++;
}
void Maintain(const int root) {
node[root].sum = node[node[root].lc].sum + node[node[root].rc].sum;
node[root].pre = max(node[node[root].lc].pre, node[node[root].lc].sum + node[node[root].rc].pre);
node[root].suf = max(node[node[root].rc].suf, node[node[root].rc].sum + node[node[root].lc].suf);
}
int initTree(const int l, const int r) {
int cur = AllocNode(1), mid = (l + r) >> 1;
if (l == r) {
node[cur].pre = node[cur].suf = node[cur].sum = 1;
return cur;
}
node[cur].lc = initTree(l, mid);
node[cur].rc = initTree(mid+1, r);
Maintain(cur);
return cur;
}
int edit(const int root, const int pos, const int val, const int l, const int r) {
int cur = AllocNode(root);
if (l == r) {
node[cur].sum = val;
node[cur].pre = node[cur].suf = max(val, 0);
return cur;
}
int mid = (l + r) >> 1;
if (pos <= mid) node[cur].lc = edit(node[cur].lc, pos, val, l, mid);
else node[cur].rc = edit(node[cur].rc, pos, val, mid+1, r);
Maintain(cur);
return cur;
}
int query(const int root, const int s, const int t, const int l, const int r) {
if (s <= l && r <= t) return node[root].sum;
if (r < s || l > t) return 0;
int mid = (l + r) >> 1;
return query(node[root].lc, s, t, l, mid) + query(node[root].rc, s, t, mid+1, r);
}
struct ANS { int fix, sum; };
ANS queryPrefix(const int rt, const int s, const int t, const int l, const int r) {
if (s <= l && r <= t) return (ANS){ node[rt].pre, node[rt].sum };
int mid = (l + r) >> 1;
if (t > mid && s <= mid) {
ANS a = queryPrefix(node[rt].lc, s, t, l, mid),
b = queryPrefix(node[rt].rc, s, t, mid+1, r);
return (ANS){ max(a.fix, a.sum + b.fix), a.sum + b.sum };
}
else if (s <= mid)
return queryPrefix(node[rt].lc, s, t, l, mid);
else if (t > mid)
return queryPrefix(node[rt].rc, s, t, mid+1, r);
abort(); // unreachable
}
ANS querySuffix(const int rt, const int s, const int t, const int l, const int r) {
if (s <= l && r <= t) return (ANS){ node[rt].suf, node[rt].sum };
int mid = (l + r) >> 1;
if (t > mid && s <= mid) {
ANS a = querySuffix(node[rt].lc, s, t, l, mid),
b = querySuffix(node[rt].rc, s, t, mid+1, r);
return (ANS){ max(b.fix, a.fix + b.sum), a.sum + b.sum };
}
else if (s <= mid)
return querySuffix(node[rt].lc, s, t, l, mid);
else if (t > mid)
return querySuffix(node[rt].rc, s, t, mid+1, r);
abort(); // unreachable
}
int count(const int a, const int b, const int c, const int d, const int k) {
int suf = querySuffix(root[k], a, b-1, 1, n).fix;
int pre = queryPrefix(root[k], c+1, d, 1, n).fix;
int mid = query(root[k], b, c, 1, n);
return mid + pre + suf;
}
int find(const int a, const int b, const int c, const int d) {
int l=0, r=n+1, mid;
while (l + 1 < r) {
mid = (l + r) / 2;
if (count(a, b, c, d, mid) >= 0) l = mid;
else r = mid;
}
return l;
}
void DealWith(int q[4], const int ans) {
for (int i=0; i<4; i++)
q[i] = (q[i] + ans) % n + 1;
sort(q, q+4);
}
struct NUM { int th, n; } num[MAXN];
int NumSort(const NUM &lhs, const NUM &rhs) {
return lhs.n < rhs.n;
}
int main() {
freopen("Temp.in" , "r", stdin );
freopen("Temp.out", "w", stdout);
scanf("%d", &n);
for (int i=1; i<=n; i++) {
scanf("%d", &src[i]);
num[i] = (NUM){ i, srt[i] = src[i] };
}
sort(num+1, num+n+1, NumSort);
sort(srt+1, srt+n+1);
node[1] = (NODE){ 1, 1, 0, 0, 0 };
root[1] = initTree(1, n);
for (int i=1, tmp; i<=n; ) {
tmp = edit(root[i], num[i].th, -1, 1, n);
for (++i; num[i-1].n == num[i].n && i<=n; i++) {
tmp = edit(tmp, num[i].th, -1, 1, n);
root[i] = root[i-1];
}
root[i] = tmp;
}
scanf("%d", &m);
for (int i=0, q[4]; i<m; i++) {
scanf("%d %d %d %d", q+0, q+1, q+2, q+3);
DealWith(q, ans);
ans = find(q[0], q[1], q[2], q[3]);
printf("%d\n", ans=srt[ans]);
}
return 0;
}
CC 原创文章采用CC BY-NC-SA 4.0协议进行许可，转载请注明：“转载自：[国家集训队] Middle”