P2839 [国家集训队]middle - 洛谷 - 计算机科学教育新生态">P2839 [国家集训队]middle - 洛谷 - 计算机科学教育新生态"> Luogu - P2839 - [国家集训队]middle - 题解 - TonyYin - Blog
Luogu – P2839 – [国家集训队]middle

题目链接:P2839 [国家集训队]middle – 洛谷 – 计算机科学教育新生态

题意

中位数:给定一个长度为 $n$,下标从 $0$ 开始的序列 $a$,设其排序之后为 $b$,那么中位数为 $b_{\lfloor\frac{n}{2}\rfloor}$.

给定一个长度为 $n$ 的,下标从 $0$ 开始的序列 $s$,回答 $Q$ 次形如 $(a, b, c, d)$ 的询问,表示:

在 $s$ 上取子区间 $[l, r]$,满足 $l\in[a, b]$,$r\in [c, d]$,要让子区间内的中位数最大,回答这个最大值

保证 $a_i<b_i<c_i<d_i$,多测,强制在线。

$1\leq n\leq 20000$,$1\leq Q\leq 25000$.

分析

由于中位数的定义中,下标从 $0$ 开始,一些细节问题需要特别考虑。

对于一个 $x$,把 $>=x$ 的元素赋值为 $1$,否则赋值为 $-1$。则区间元素和 $>=0$,当且仅当中位数 $\operatorname{mid}>=x$.

考虑对每次询问二分。

在处理询问之前,对于每个 $x$ 预处理出一颗线段树,维护区间内的最大前缀、最大后缀、区间元素和。

在询问 $(a,b,c,d)$ 中,$[b+1,c]$ 这段是必须选的,再加上 $[a, b]$ 中的最大后缀,和 $[c,d]$ 中的最大前缀即可。

注意到离散化后,每当 $x$ 的值增加 $1$ 时,只会影响序列中的一个值,因此建立可持久化线段树。

$x$ 每增加 $1$,线段树只会多加一条链,空间复杂度为 $\mathcal{O}(Q\log n)$ 级别。

代码

不难实现。

const int MAXN = 20010, inf = 0x3f3f3f3f3f3f3f3f;
int n;
struct Node{
    int v, pos;
} a[MAXN];
bool cmp(Node A, Node B) { return A.v < B.v; }
struct Point{ //可持久化线段树
    int lv, rv, sum; //区间内最大前缀和,最大后缀和,区间元素和
    int lc, rc; //左右儿子编号
} t[MAXN << 5];
int root[MAXN], p_cnt = 0;
#define ls(x) (t[x].lc)
#define rs(x) (t[x].rc)
void push_up(int rt) {
    t[rt].sum = t[ls(rt)].sum + t[rs(rt)].sum;
    t[rt].lv = max(t[ls(rt)].lv, t[ls(rt)].sum + t[rs(rt)].lv);
    t[rt].rv = max(t[rs(rt)].rv, t[rs(rt)].sum + t[ls(rt)].rv);
}
void build(int &rt, int l, int r) {
    rt = ++p_cnt;
    if(l == r) {
        //初始的 x = 0,所以每个点权值都是 1
        t[rt].lv = t[rt].rv = t[rt].sum = 1;
        return;
    }
    int mid = (l + r) >> 1;
    build(ls(rt), l, mid);
    build(rs(rt), mid + 1, r);
    push_up(rt);
}
void update(int &rt, int his, int l, int r, int x, int v) {
    //以 his 为基础进行修改,把 x -> v
    rt = ++p_cnt; t[rt] = t[his];
    if(l == r) {
        t[rt].lv = t[rt].rv = t[rt].sum = v;
        return;
    }
    int mid = (l + r) >> 1;
    if(x <= mid) update(ls(rt), ls(his), l, mid, x, v);
    else update(rs(rt), rs(his), mid + 1, r, x, v);
    push_up(rt);
}
int query_s(int rt, int l, int r, int x, int y) {
    //询问区间[x ,y]的和
    if(x <= l && r <= y) return t[rt].sum;
    int mid = (l + r) >> 1, ret = 0;
    if(x <= mid) ret += query_s(ls(rt), l, mid, x, y);
    if(y > mid) ret += query_s(rs(rt), mid + 1, r, x, y);
    return ret;
}
int query_l(int rt, int l, int r, int x, int y) {
    //询问区间[x, y]最大的前缀和
    if(x <= l && r <= y) return t[rt].lv;
    int mid = (l + r) >> 1;
    if(y <= mid) return query_l(ls(rt), l, mid, x, y); //注意要分类讨论
    else if(x > mid) return query_l(rs(rt), mid + 1, r, x, y);
    else return max(
        query_l(ls(rt), l, mid, x, mid), 
        query_s(ls(rt), l, mid, x, mid) + query_l(rs(rt), mid + 1, r, mid + 1, y)
    );
}
int query_r(int rt, int l, int r, int x, int y) {
    //询问区间[x, y]最大的后缀和
    if(x <= l && r <= y) return t[rt].rv;
    int mid = (l + r) >> 1;
    if(y <= mid) return query_r(ls(rt), l, mid, x, y);
    else if(x > mid) return query_r(rs(rt), mid + 1, r, x, y);
    else return max(
        query_r(rs(rt), mid + 1, r, mid + 1, y), 
        query_s(rs(rt), mid + 1, r, mid + 1, y) + query_r(ls(rt), l, mid, x, mid)
    );
}
bool check(int x, int a, int b, int c, int d) {
    //是否存在端点 a<=l<=b, c<=r<=d 满足 [l, r] 的元素和 >= 0
    int sum = 0;
    if(c >= b + 2) { //b, c中间有一段一定要选
        sum += query_s(root[x], 1, n, b + 1, c - 1);
    }
    sum += query_r(root[x], 1, n, a, b); //后缀 最大连续段
    sum += query_l(root[x], 1, n, c, d); //前缀 最大连续段
    return (sum >= 0);
}
signed main() {
    n = read();
    for(int i = 1; i <= n; i++) a[i].v = read(), a[i].pos = i;
    sort(a + 1, a + n + 1, cmp); //离散化
    build(root[1], 1, n);
    for(int i = 2; i <= n + 1; i++) {
        update(root[i], root[i - 1], 1, n, a[i - 1].pos, -1);
    }
    int Q = read(), lstans = 0;
    while(Q--) {
        int q[4];
        q[0] = (read() + lstans) % n + 1;
        q[1] = (read() + lstans) % n + 1;
        q[2] = (read() + lstans) % n + 1;
        q[3] = (read() + lstans) % n + 1;
        sort(q, q + 4);
        int l = 1, r = n, mid, ans = -1;
        while(l <= r) {
            mid = (l + r) >> 1;
            if(check(mid, q[0], q[1], q[2], q[3])) {
                l = mid + 1;
                ans = mid;
            } else r = mid - 1;
        }
        printf("%lld\n", a[ans].v); lstans = a[ans].v;
    }
    return 0;
}
暂无评论

发送评论 编辑评论

|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇