洛谷题单指南-线段树的进阶用法-P2839 [国家集训队] middle

原题链接：https://www.luogu.com.cn/problem/P2839

题意解读：求左端点在 [a,b]之间，右端点在 [c,d]之间的子区间中，最大的中位数。

解题思路：

1、直男暴力法

枚举左、右端点，然后排序计算中位数，这样的复杂度在n*n*logn，显然不可行。

2、渣男巧妙法

首先，要重新来看待何为中位数。

设一段区间的中位数x，将该区间中>=x的数全部置为1，<x的数置为-1，设区间和为sum，如果sum>=0，显然中位数可以更大，反之则更小。

那么，完全可以通过二分最大中位数x（离散化之后的），然后针对每一个x建立一个权值线段树，线段树中节点区间是x对应的原序列下标，节点值>=x的是1，<x的是-1，这样二分时check()函数主要用来判断当前的中位数x是否存在合理的区间满足左端点在 [a,b]之间，右端点在 [c,d]之间。

怎么判断呢？

既然左端点在 [a,b]之间，右端点在 [c,d]之间，那么区间[b+1,c-1]是一定包含的，

区间最大和 = 区间[b+1,c-1]和+区间[a,b]最大后缀和+区间[c,d]最大前缀和

只要区间最大和 >= 0，就可以往更大的数进行二分，反之往更小的数二分。

关于如何计算区间最大后缀和、最小前缀和的方法可以参考：https://www.cnblogs.com/jcwy/p/18582207

如果对于每一个离散化后的中位数都建立一棵线段树，内存显然支撑不住，可以用可持久化线段树进行优化。

将序列中所有数按照从小到大排序，同时记录每个数原下标，从1~n遍历

对于第1个数，建立线段树root[1]的每一个元素值都为1，对于root[i]可以从root[i-1]进行复制，然后将i-1对应的序列原下标的值改为-1。

具体逻辑最好还是参考代码：

100分代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 20005, INF = 1e5;

struct Num
{
    int v; //序列的值
    int idx; //在原序列中的下标
} w[N];

bool cmp(Num x, Num y)
{
    return x.v < y.v;
}

struct Node
{
    int L, R;
    int sum; //区间和
    int presum; //区间最大前缀和
    int subsum; //区间最大后缀和
} tr[N * 80];

int root[N], idx;
int ques[4];
int n, q;

void pushup(Node &root, Node &left, Node &right)
{
    root.sum = left.sum + right.sum;
    root.presum = max(left.presum, left.sum + right.presum);
    root.subsum = max(right.subsum, right.sum + left.subsum);
}

void pushup(int u)
{
    pushup(tr[u], tr[tr[u].L], tr[tr[u].R]);
}

//建立root[1]的线段树，所有节点值都为1
int build(int l, int r)
{
    int u = ++idx;
    if(l == r)
    {
        tr[u].sum = tr[u].presum = tr[u].subsum = 1;
        return u;
    }
    int mid = l + r >> 1;
    tr[u].L = build(l, mid);
    tr[u].R = build(mid + 1, r);
    pushup(u);
    return u;
}

//从pre复制线段树，将pos位置的值改为-1
int update(int pre, int l, int r, int pos)
{
    int u = ++idx;
    tr[u] = tr[pre];
    if(l == r)
    {
        tr[u].sum = tr[u].presum = tr[u].subsum = -1;
        return u;
    }
    int mid = l + r >> 1;
    if(pos <= mid) tr[u].L = update(tr[pre].L, l, mid, pos);
    else tr[u].R = update(tr[pre].R, mid + 1, r, pos);
    pushup(u);
    return u;
}

//在根为u的线段树中查询值区间在[lpos,rpos]的sum、presum、subsum
Node query(int u, int l, int r, int lpos, int rpos)
{
    if(lpos > rpos) return {0, 0, 0, -INF, -INF}; //注意边界情况
    if(l >= lpos && r <= rpos) return tr[u];
    else if(l > rpos || r < lpos) return {0, 0, 0, -INF, -INF};
    else 
    {
        int mid = l + r >> 1;
        Node left = query(tr[u].L, l, mid, lpos, rpos);
        Node right = query(tr[u].R, mid + 1, r, lpos, rpos);
        Node res;
        pushup(res, left, right);
        return res;
    }
}

bool check(int a, int b, int c, int d, int x)
{
    //区间最大和
    int sum = query(root[x], 1, n, a, b).subsum + query(root[x], 1, n, b + 1, c - 1).sum + query(root[x], 1, n, c, d).presum;
    return sum >= 0;
}

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        cin >> w[i].v;
        w[i].idx = i; //记录下标
    }
    sort(w + 1, w + n + 1, cmp); //按值从小到大排序
    root[1] = build(1, n); //建立最小元素的线段树
    //建立可持久化线段树，对于第i个值，把前面一个值的下标对应值变成-1
    for(int i = 2; i <= n; i++) root[i] = update(root[i - 1], 1, n, w[i - 1].idx);
 
    int a, b, c, d, x = 0;
    cin >> q;
    while(q--)
    {
        cin >> a >> b >> c >> d;
        ques[0] = (a + x) % n + 1; //注意原来的序列从0开始，调整为从1开始
        ques[1] = (b + x) % n + 1;
        ques[2] = (c + x) % n + 1;
        ques[3] = (d + x) % n + 1;
        sort(ques, ques + 4);
        int l = 1, r = n, ans;
        while(l <= r)
        {
            int mid = l + r >> 1;
            if(check(ques[0], ques[1], ques[2], ques[3], mid)) 
            {
                ans = mid;
                l = mid + 1;
            }
            else r = mid - 1;
        }
        x = w[ans].v;
        cout << x << endl;
    }

    return 0;
}