题解 P2839 【[国家集训队]middle】
EternalEpic · · 题解
（调整完格式后，第三次提交。望请批准！）
前置知识：主席树，二分答案，线段树合并左右最大子段和思想。
不会主席树的，跳转：P3834 【模板】主席树
不会线段树合并左右最大子段和的，可以去做：P3792 大母神
ps：两到紫题再加一个二分就是集训队黑题惹（雾）
看到大家的码风都清奇俊秀（有的用下划线当变量，有的不打空格在压行），我来提供一份比较正常的题解。
看到区间中位数，老司机一般都会想到用二分，num >= mid设1， num < mid设-1。如果区间和大于0，l = mid + 1 否则 r = mid - 1
但此题，区间不固定（大雾）。我们该如何处理呢？
我们可以重新考虑一下check函数。
以(前区间rmax + 后区间lmax + 必选区间[b + 1, c - 1]的tot 是否>= 0)来判断
Check函数:
inline bool check(int id, int A, int B, int C, int D)
{
int ret = 0;
if (B + 2 <= C) ret += pst.query(root[id], 1, n, B + 1, C - 1).tot;
ret += pst.query(root[id], 1, n, A, B).rmax;
ret += pst.query(root[id], 1, n, C, D).lmax;
return ret >= 0;
}为什么要这样做，必选区间不说，剩下两区间要是1尽可能多所以如此check了。
而lmax，rmax，和tot就要用主席树维护啦。
//Program written by Liu Zhaozhou ~~~
#include <bits/stdc++.h>
#include <algorithm>
#include <queue>
#include <set>
#include <vector>
#include <deque>
#include <string>
#define lowbit(x) x & -x
#pragma GCC optimize(3)
using namespace std;
using namespace std;
namespace Base {
inline char gc(void)
{
static char buf[100000], *p1 = buf, *p2 = buf;
return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}
#define gc() getchar()
template <class T> inline void read(T &x)
{
T flag = (T) 1; x = 0; static char ch = gc();
for (; !isdigit(ch); ch = gc()) if (ch == '-') flag = -1;
for (; isdigit(ch); ch = gc()) x = x * 10 + ch - 48;
if (ch == '.') {
T dgt = 0.1;
for (ch = gc(); isdigit(ch); ch = gc())
x = x + dgt * (ch - 48), dgt *= 0.1;
} x *= flag; return;
}
template <class T> inline void write(T x) {
if (x < 0) putchar('-'), x = -x;
register T y = 1; int len = 1;
for (; y <= x / 10; y *= 10) ++len;
for (; len; --len, x %= y, y /= 10) putchar(x / y + 48);
}
template <class T> inline void writeln(T x) {write(x); puts("");}
template <class T> inline void writeln(T x, char c) {write(x); putchar(c);}
template <class T> inline void writeln(char c, T x) {putchar(c); write(x);}
template <class T> inline void chkmax(T &x, const T y) {x > y ? x = x : x = y;}
template <class T> inline void chkmin(T &x, const T y) {x < y ? x = x : x = y;}
typedef long long ll;
typedef unsigned long long ull;
typedef double ld;
#define Ms(arr, opt) memset(arr, opt, sizeof(arr))
#define Mp(x, y) make_pair(x, y)
inline void file(string str) {
freopen((str + ".in").c_str(), "r", stdin);
freopen((str + ".out").c_str(), "w", stdout);
}
}
using namespace Base;
enum {
Maxn = 20005
};
int n, cnt, m, lastans, q[4], root[Maxn];
struct State {
public:
int id, num;
inline bool operator < (const State&x) const{
return num < x.num;
}
} a[Maxn << 2 | 1];
class Info {
public:
int tot, lmax, rmax;
inline Info operator + (const Info&opt)
const {
return (Info) {
tot + opt.tot,
max(lmax, tot + opt.lmax),
max(opt.rmax, opt.tot + rmax)
};
}
inline void Init(int _t, int _l, int _r) {
tot = _t, lmax = _l, rmax = _r;
}
};
class Node {
public:
int ls, rs; Info sum;
} t[Maxn * 40 + 5];
class PST {
public:
inline void pushup(int pos) {
t[pos].sum = t[t[pos].ls].sum + t[t[pos].rs].sum;
}
inline void build(int &u, int l, int r) {
int tmp = u; u = ++cnt; t[u] = t[tmp];
if (l == r) {t[u].sum.Init(1, 1, 1); return;}
int mid = l + r >> 1;
build(t[u].ls, l, mid),
build(t[u].rs, mid + 1, r);
pushup(u);
}
inline void modify(int &u, int l, int r, int x) {
int tmp = u; u = ++cnt; t[u] = t[tmp];
if (l == r) {t[u].sum.Init(-1, -1, -1); return;}
int mid = l + r >> 1;
if (x <= mid) modify(t[u].ls, l, mid, x);
else modify(t[u].rs, mid + 1, r, x);
pushup(u);
}
inline Info query(int u, int l, int r, int L, int R) {
if (L <= l && r <= R) return t[u].sum;
int mid = l + r >> 1;
if (R <= mid) return query(t[u].ls, l, mid, L, R);
else if (mid < L) return query(t[u].rs, mid + 1, r, L, R);
else return query(t[u].ls, l, mid, L, mid)
+ query(t[u].rs, mid + 1, r, mid + 1, R);
}
} pst;
inline bool check(int id, int A, int B, int C, int D)
{
int ret = 0;
if (B + 2 <= C) ret += pst.query(root[id], 1, n, B + 1, C - 1).tot;
ret += pst.query(root[id], 1, n, A, B).rmax;
ret += pst.query(root[id], 1, n, C, D).lmax;
return ret >= 0;
}
signed main(void) {
//file("PST");
read(n);
for (int i = 1; i <= n; i++)
read(a[i].num), a[i].id = i;
sort(a + 1, a + n + 1);
pst.build(root[1], 1, n);
for (int i = 2; i <= n; i++)
root[i] = root[i - 1],
pst.modify(root[i], 1, n, a[i - 1].id);
read(m);
while (m--) {
for(int i = 0; i < 4; i++)
read(q[i]), q[i] = (q[i] + lastans) % n + 1;
sort(q, q + 4);
int l = 1, r = n, mid, ans;
while(l <= r){
mid = l + r >> 1;
if (check(mid, q[0], q[1], q[2], q[3]))
ans = mid, l = mid + 1;
else r = mid - 1;
}
writeln(lastans = a[ans].num);
}
return 0;
}
/**/
谢谢兹磁！