题意: 一个长度为n的序列, Q个询问, 查询左端点在[a, b], 右端点在[c, d]的所有子串中最大的中位数. 奇数个数的中位数是排序后最中间的一个, 偶数个数的中位数定义为排序后中间靠右的那一个. (n≤20000, Q≤25000) 陈老师2012年的互测题. 很妙, 对我来说展现了并不是只能将权值线段树持久化.
据说得二分, 所以先往二分的方向想想......中位数的直接定义跟序列长度有关, 要想同时判定一堆序列, 得把长度去掉. 将≥x的数置为1, <x的数置为-1, 中位数≥x当且仅当转化后序列中数的和≥0. 于是, 问题的对象转化为我们熟悉的量.
然后, 得判定是否存在这样一个和大于等于0的序列. 再转化一下, 和最大的序列的和是否大于等于0.
我的想法是转化为两个前缀和相减, 于是得对一个区间内的i, "S(i, x) = [0, i]位置替换后的和", 求最大, 最小值. 原以为替换后的和只能用 "≥x的数的个数-<x的数的个数" 来求, 发现犯了蠢. 新加入一个a[i], 则对于(i+1), x≤a[i]的和+1, x>a[i]的和-1, 所以, 在每个位置i, 可以直接对于 (离散化后) 所有的x求出S(i, x). 然而, 这对解题帮助不大. 又想分一下块, 每块一棵线段树维护这些S, 依次加入, 求个历史最值, 无奈时间复杂度
于是看了题解. 推荐丽洁本人的: Middle 解题报告 (来自清澄)
上面的想法开始是不错的, 以下重新叙述一遍:
二分答案x, 将≥x的数置为1, <x的数置为-1, 问题转化为判定左端点在[a, b], 右端点在[c, d]的所有子串中, 和的最大值是否≥0. 这样的子串可拆成三部分[a, b]++[b+1, c-1]++[c, d], 则最大的和=[a, b]的最大后缀和+[b+1, c-1]的和+[c, d]的最大前缀和. 对离散化后的每一个x, 建一棵线段树维护替换后的序列的这三个量. x从小到大枚举, 每次仅将一个+1修改为-1, 于是可以通过持久化用
我的想法是对每个位置建一棵线段树, 维护不同x的答案. 正解是对每个x建一棵线段树, 维护不同位置的答案. 由于按位置查询, 前者并不能搞什么事情 (我们并不需要知道对于 x=1~3, S(i, x)的和或最大值是多少). 就像, 如果要查询区间k大, 权值线段树套区间线段树更优, 如果要查询区间排名, 区间线段树套权值线段树更优, 虽然都可以做, 却相差一个
实现的时候, 借鉴了一下Po姐的写法, 用一个函数返回两个子区间的信息合并后的结果, query的时候也可以用, 挺方便. 区间[b+1, c-1]可能为空, 忘记判了, 但是这种情况恰好会在query的第一层就返回, 所以写题解的时候才发现.
#include <bits/stdc++.h>
#define Rep(i, a, b) for (int i = (a), i##_ = (b); i < i##_; ++i)
#define For(i, a, b) for (int i = (a), i##_ = (b); i <= i##_; ++i)
#define Down(i, a, b) for (int i = (a), i##_ = (b); i >= i##_; --i)
using namespace std;
const int MAX_N = 2e4, LG_N = 15, inf = 1e9 + 1;
struct Data {
int sum, pre, suf;
Data(int sum=0, int pre=-inf, int suf=-inf): sum(sum), pre(pre), suf(suf) {}
Data operator+(const Data& x)
{
return Data(sum + x.sum, max(pre, sum + x.pre), max(x.suf, x.sum + suf));
}
};
struct Node {
Node* lc, * rc;
Data v;
} nodes[MAX_N*2 + (MAX_N-1)*(LG_N+1) + 1], * nil = nodes, * root[MAX_N];
inline void init()
{
*nil = (Node){nil, nil, Data()};
}
inline Node* new_node(const Node& v)
{
static Node* cur = nodes + 1;
*cur = v;
return cur++;
}
void modify(Node* &o, Node* p, int x, int l, int r)
{
o = new_node(*p);
if (l == r)
o->v = Data(-1, -1, -1);
else {
int m = (l+r)/2;
if (x <= m)
modify(o->lc, p->lc, x, l, m);
else
modify(o->rc, p->rc, x, m+1, r);
o->v = o->lc->v + o->rc->v;
}
}
Data query(Node* o, int L, int R, int l, int r)
{
if (L <= l && r <= R)
return o->v;
int m = (l+r)/2;
Data v;
if (L <= m)
v = query(o->lc, L, R, l, m);
if (R > m)
v = v + query(o->rc, L, R, m+1, r);
return v;
}
void build(Node* &o, int l, int r)
{
o = new_node(*nil);
if (l == r)
o->v = Data(1, 1, 1);
else {
int m = (l+r)/2;
build(o->lc, l, m);
build(o->rc, m+1, r);
o->v = o->lc->v + o->rc->v;
}
}
int n;
int solve(int a, int b, int c, int d)
{
int l = 0, r = n; // [l, r)
while (r-l > 1) {
int m = (l+r)/2, v = query(root[m], a, b, 0, n-1).suf
+ query(root[m], b+1, c-1, 0, n-1).sum + query(root[m], c, d, 0, n-1).pre;
if (v >= 0)
l = m;
else
r = m;
}
return l;
}
int a[MAX_N], b[MAX_N];
inline bool cmp(int i, int j) { return a[i] < a[j]; }
int main()
{
scanf("%d", &n);
Rep (i, 0, n) {
scanf("%d", &a[i]);
b[i] = i;
}
sort(b, b+n, cmp);
build(root[0], 0, n-1);
Rep (i, 0, n-1)
modify(root[i+1], root[i], b[i], 0, n-1);
int m, lastans = 0;
scanf("%d", &m);
while (m--) {
int q[4];
Rep (i, 0, 4) {
scanf("%d", q+i);
q[i] = (q[i] + lastans)%n;
}
sort(q, q+4);
printf("%d\n", lastans = a[b[solve(q[0], q[1], q[2], q[3])]]);
}
return 0;
}发现用了宏之后就不能高亮了, 似乎是<的问题. 读者 (如果存在) 可以将代码复制到文本编辑器里再阅读. QwQ