洛谷P2839 [国家集训队]middle

传送门

做主席树练习的时候搜到了这题，不过看到这数据范围我的第一反应是分块……

分块确实能过，时间复杂度没问题，代码短，常数小，跑得更快。只不过渐进时间复杂度更高。不过反正都是来练习主席树的就用主席树做吧。

框架大概是二分中位数 mid 值看能否实现。

于是沉思良久决定看题解。

首先，对于区间中位数，有一个比较套路的做法：将区间内每个比当前mid值大或相等的设置为1，否则设置为-1，对区间进行求和。如果和非负，中位数可以变大；否则，中位数只能调小

摘自题解。

wcnmd这是套路？果然还是我太年轻了啊。

于是我想了想决定对于每一个 mid 建一颗线段树（肯定要离散化）。空间炸了，于是用主席树。

然后二分 mid ，对于每个给定的区间范围，$[b,c]$ 为必选区间，然后在 $[a,b-1]$ 中取最大后缀，在 $[c+1,d]$ 中取最大前缀。

主席树每个节点维护当前区间的和，最大前缀，最大后缀，区间合并的时候就很easy了。

复杂度 $O(nlog^2_2n)$，而分块复杂度为 $O(n\sqrt{n})$
然后不能Unique啥的，我就做了四天

cnm

$Code:$

#include <cstdio>
#include <algorithm>

inline int read() {
char ch;
int x(0), f(1);
while ((ch = getchar()) < 48) if (ch == '-') f = -1;
do x = x * 10 + ch - 48; while ((ch = getchar()) >= 48);
return x * f;
}
struct Max {inline int operator () (const int x, const int y) const {return x > y ? x : y;}} max;
const int N = 20005, n = read();
int a[N], Key[N];
struct I_want_to_AKIOI {
int v, idx, rnk;
inline bool operator < (const I_want_to_AKIOI x) const {return v < x.v;}
} b[N];

struct Chairman_tree {
struct node {
int v, v1, v2, ls, rs;
} a[N << 5];
int rt[N], tot, x, y, ans, s;

inline void build() {make_tree(rt[1] = tot = 1, 1, n);}
void make_tree(const int p, const int l, const int r) {
a[p].v = a[p].v1 = a[p].v2 = r - l + 1;
if (l != r) make_tree(a[p].ls = ++ tot, l, l + r >> 1),
make_tree(a[p].rs = ++ tot, (l + r >> 1) + 1, r);
}

inline void Update() {
int k(1);
for (int i(1); i <= n; ++ i)
//if (b[i].rnk == b[i - 1].rnk) x = b[i].idx, update(rt[k], 1, n, rt[k - 1]);
x = b[i].idx, rt[++ k] = ++ tot, update(rt[k], 1, n, rt[k - 1]);
}
void update(const int p, const int l, const int r, const int root) {
if (l == r) {a[p].v = -1, a[p].v1 = a[p].v2 = 0; return;}
int mid(l + r >> 1), &ls(a[p].ls), &rs(a[p].rs);
if (mid >= x) {
update((ls ? ls : ls = ++ tot), l, mid, a[root].ls);
if (!rs) rs = a[root].rs;
}
else {
update((rs ? rs : rs = ++ tot), mid + 1, r, a[root].rs);
if (!ls) ls = a[root].ls;
}
a[p].v = a[ls].v + a[rs].v, a[p].v1 = max(a[ls].v1, a[ls].v + a[rs].v1),
a[p].v2 = max(a[rs].v2, a[rs].v + a[ls].v2);
}

inline int Query(const int A, const int B, const int C, const int D) {
int l(1), r(n), Ans(0);
while (l <= r) {
x = B, y = C;
int mid(l + r >> 1), sum(query(rt[mid], 1, n));
x = A, y = B - 1, s = ans = 0, queryr(rt[mid], 1, n), sum += ans;
x = C + 1, y = D, s = ans = 0, queryl(rt[mid], 1, n), sum += ans;
sum >= 0 ? Ans = mid, l = mid + 1 : r = mid - 1;
}
return Ans;
}
void queryl(const int p, const int l, const int r) {
if (x <= l && r <= y) {ans = max(ans, s + a[p].v1), s += a[p].v; return;}
int mid(l + r >> 1);
if (mid >= x) queryl(a[p].ls, l, mid);
if (mid < y) queryl(a[p].rs, mid + 1, r);
}
void queryr(const int p, const int l, const int r) {
if (x <= l && r <= y) {ans = max(ans, s + a[p].v2), s += a[p].v; return;}
int mid(l + r >> 1);
if (mid < y) queryr(a[p].rs, mid + 1, r);
if (mid >= x) queryr(a[p].ls, l, mid);
}
int query(const int p, const int l, const int r) const {
if (x <= l && r <= y) return a[p].v;
int mid(l + r >> 1), sum(0);
if (mid >= x) sum += query(a[p].ls, l, mid);
if (mid < y) sum += query(a[p].rs, mid + 1, r);
return sum;
}
} Tree;

int main() {
int last(0), m;
Tree.build();
for (int i(1); i <= n; ++ i) b[i].idx = i, b[i].v = a[i] = read();
std::sort(b + 1, b + n + 1);
Key[b[1].rnk = 1] = b[1].v;
for (int i(2); i <= n; ++ i)
Key[b[i].rnk = (b[i].v == b[i - 1].v ? b[i - 1].rnk : b[i - 1].rnk + 1)] = b[i].v;
std::sort(a + 1, a + n + 1);
Tree.Update(), m = read();
while (m --) {
int q[4] = {read(), read(), read(), read()};
for (int i(0); i < 4; ++ i) q[i] = (q[i] + last) % n + 1;
std::sort(q, q + 4);
printf("%d\n", last = a[Tree.Query(q[0], q[1], q[2], q[3])]);
}
}