「国家集训队」middle

传送门

按照中位数题的套路，二分答案 \(mid\)，序列中 \(\ge mid\) 记为 \(1\)，\(< mid\) 的记为 \(-1\)

然后只要存在一个区间 \([l, r](l \in [a, b], r \in [c, d])\) 的和 \(\ge 0\) 则答案可以更大，否则就更小。

所以说我们就要算出区间 \([b + 1, c - 1]\) 的和，加上 \([a, b]\) 的最大后缀，还有 \([c, d]\) 最大前缀，加起来就是我们用来 \(check\) 的值。

这些过程可以用线段树来搞，具体维护细节就和维护区间最大子段和差不多。

但是我们面临另一个问题：\(mid\) 会变，也就是我们的序列是会变的，我们不可能对于每一个 \(mid\) 都建一棵线段树。

那能不能用主席树优化空间呢？

我们发现，\(mid\) 扩大 \(1\) ，只会有一个数的值从 \(1\) 变成 \(-1\) ，也就是说我们只需要修改一条链上的信息，这显然可以用主席树来搞，空间问题也就解决了。

参考代码：

#include <algorithm>

#include <cstdio>

#define rg register

#define file(x) freopen(x".in", "r", stdin), freopen(x".out", "w", stdout)

using namespace std;

template < class T > inline void read(T& s) {

    s = 0; int f = 0; char c = getchar();

    while ('0' > c || c > '9') f |= c == '-', c = getchar();

    while ('0' <= c && c <= '9') s = s * 10 + c - 48, c = getchar();

    s = f ? -s : s;

}

typedef long long LL;

const int _ = 20005;

int n, m, q[5], a[_], id[_], tot, rt[_];

struct node { int lc, rc, sum, L, R; } t[_ << 5];

inline void pushup(int p) {

    t[p].sum = t[t[p].lc].sum + t[t[p].rc].sum;

    t[p].L = max(t[t[p].lc].L, t[t[p].lc].sum + t[t[p].rc].L);

    t[p].R = max(t[t[p].rc].R, t[t[p].rc].sum + t[t[p].lc].R);

}

inline void build(int& p, int l = 1, int r = n) {

    p = ++tot;

    if (l == r) { t[p].sum = t[p].L = t[p].R = 1; return ; }

    int mid = (l + r) >> 1;

    build(t[p].lc, l, mid), build(t[p].rc, mid + 1, r), pushup(p);

}

inline void update(int& p, int q, int x, int l = 1, int r = n) {

    t[p = ++tot] = t[q];

    if (l == r) { t[p].sum = t[p].L = t[p].R = -1; return ; }

    int mid = (l + r) >> 1;

    if (x <= mid) update(t[p].lc, t[q].lc, x, l, mid);

    else update(t[p].rc, t[q].rc, x, mid + 1, r);

    pushup(p);

}

inline node query(int ql, int qr, int p, int l = 1, int r = n) {

    if (ql <= l && r <= qr) return t[p];

    int mid = (l + r) >> 1;

    if (qr <= mid) return query(ql, qr, t[p].lc, l, mid);

    if (ql > mid) return query(ql, qr, t[p].rc, mid + 1, r);

    node ls = query(ql, mid, t[p].lc, l, mid), rs = query(mid + 1, qr, t[p].rc, mid + 1, r);

    return (node) { 0, 0, ls.sum + rs.sum, max(ls.L, ls.sum + rs.L), max(rs.R, rs.sum + ls.R) };

}

inline bool check(int mid) {

    int res = 0;

    if (q[1] + 1 <= q[2] - 1) res += query(q[1] + 1, q[2] - 1, rt[mid]).sum;

    res += query(q[0], q[1], rt[mid]).R;

    res += query(q[2], q[3], rt[mid]).L;

    return res >= 0;

}

inline bool cmp(int i, int j) { return a[i] < a[j]; }

int main() {

#ifndef ONLINE_JUDGE

    file("cpp");

#endif

    read(n);

    for (rg int i = 1; i <= n; ++i) read(a[i]), id[i] = i;

    sort(id + 1, id + n + 1, cmp);

    build(rt[1]);

    for (rg int i = 2; i <= n; ++i) update(rt[i], rt[i - 1], id[i - 1]);

    read(m);

    for (rg int ans = 0; m--; ) {

	    for (rg int i = 0; i < 4; ++i) read(q[i]), q[i] = (q[i] + ans) % n + 1;

	    sort(q, q + 4);

	    int l = 1, r = n;

	    while (l <= r) {

    	    int mid = (l + r) >> 1;

	        if (check(mid)) ans = a[id[mid]], l = mid + 1; else r = mid - 1;

	    }

	    printf("%d\n", ans);

    }

    return 0;

}

巴特西

「国家集训队」middle

「国家集训队」middle

最新文章

热门文章