BZOJ 2653 middle 二分答案+可持久化线段树

　　题目大意：有一个序列，包含多次询问。询问区间左右端点在规定区间里移动所得到的最大中位数的值。

　　考虑对于每个询问，如何得到最优区间？枚举显然是超时的，只能考虑二分。

　　中位数的定义是在一个序列中，比中位数小的数跟比它大的数一样多，由于我们要求的是最大的中位数，自然希望能找到一个区间，使得该区间内比该中位数大的数尽量多。

　　二分中位数k，假设比k小的数记为-1，其余的数记为1，那么我们就是要寻找最大连续子序列和，若找到的最大的和>=0，则当前的k就是合法的。

　　最大连续子序列和可以用线段树来维护，由于存在多组询问，每次建一棵线段树很慢，我们选择建主席树。初始时，把数按从小到大排好序，全部的数记为1，做到第i个数时，将第i-1个数记为-1，以此做下去。

　　那么这样最终二分到的答案会不会不在指定的区间范围之中呢？

　　肯定是不存在的，我们可以分类讨论。

　　　n为偶数：n = 4时，0 1 2 3，中位数的位置为2，如果答案在1-2之间，则会有更优的答案；如果在2-3之间，显然是不可能的。

　　　n为奇数：n = 3时，0 1 2 3 4，中位数的位置为2，分析同上。

#include <cstdio>

#include <cstdlib>

#include <algorithm>

using namespace std;

typedef long long LL;

const int maxn = ;

int n, a[maxn], b[maxn], root[maxn], q[];

struct Tree

{

    int cnt;

    int ml[maxn*], mr[maxn*], sum[maxn*], ls[maxn*], rs[maxn*];

    Tree()

    {

        cnt = ;

    }

    void pushup(int rt)

    {

        ml[rt] = max(ml[ls[rt]], sum[ls[rt]]+ml[rs[rt]]);

        mr[rt] = max(mr[rs[rt]], sum[rs[rt]]+mr[ls[rt]]);

        sum[rt] = sum[ls[rt]]+sum[rs[rt]];

    }

    void build(int rt, int l, int r)

    {

        if (l == r)

        {

            ml[rt] = mr[rt] = sum[rt] = ;

            return ;

        }

        int mid = (l+r)>>;

        ls[rt] = ++cnt, build(ls[rt], l, mid);

        rs[rt] = ++cnt, build(rs[rt], mid+, r);

        pushup(rt);

    }

    void update(int las_rt, int rt, int l, int r, int p, int d)

    {

        if (l == r)

        {

            ml[rt] = mr[rt] = sum[rt] = d;

            return ;

        }

        int mid = (l+r)>>;

        if (p <= mid)

        {

            ls[rt] = ++cnt, rs[rt] = rs[las_rt];

            update(ls[las_rt], ls[rt], l, mid, p, d);

        }

        else

        {

            ls[rt] = ls[las_rt], rs[rt] = ++cnt;

            update(rs[las_rt], rs[rt], mid+, r, p, d);

        }

        pushup(rt);

    }

    int query_sum(int rt, int l, int r, int L, int R)

    {

        if (L <= l && r <= R)

            return sum[rt];

        int mid = (l+r)>>, ret = ;

        if (L <= mid)

            ret += query_sum(ls[rt], l, mid, L, R);

        if (R > mid)

            ret += query_sum(rs[rt], mid+, r, L, R);

        return ret;

    }

    int query_ml(int rt, int l, int r, int L, int R)

    {

        if (L <= l && r <= R)

            return ml[rt];

        int mid = (l+r)>>;

        if (R <= mid)

            return query_ml(ls[rt], l, mid, L, R);

        else

            if (L > mid)

                return query_ml(rs[rt], mid+, r, L, R);

            else

                return max(query_ml(ls[rt], l, mid, L, R), query_sum(ls[rt], l, mid, L, R)+query_ml(rs[rt], mid+, r, L, R));

    }

    int query_mr(int rt, int l, int r, int L, int R)

    {

        if (L <= l && r <= R)

            return mr[rt];

        int mid = (l+r)>>;

        if (R <= mid)

            return query_mr(ls[rt], l, mid, L, R);

        else

            if (L > mid)

                return query_mr(rs[rt], mid+, r, L, R);

            else

                return max(query_mr(rs[rt], mid+, r, L, R), query_sum(rs[rt], mid+, r, L, R)+query_mr(ls[rt], l, mid, L, R));

    }

}T;

bool cmp(const int &AI, const int &BI)

{

    return a[AI] < a[BI];

}

void build_tree()

{

    root[] = ++T.cnt;

    T.build(root[], , n);

    for (int i = ; i <= n; ++i)

    {

        root[i] = ++T.cnt;

        T.update(root[i-], root[i], , n, b[i-], -);

    }

}

bool check(int k, int q1, int q2, int q3, int q4)

{

    int sum = ;

    if (q2+ < q3)

        sum += T.query_sum(root[k], , n, q2+, q3-);

    sum += T.query_mr(root[k], , n, q1, q2);

    sum += T.query_ml(root[k], , n, q3, q4);

    return sum >= ;

}

int main()

{

    scanf("%d", &n);

    for (int i = ; i <= n; ++i)

        scanf("%d", &a[i]), b[i] = i;

    sort(b+, b+n+, cmp);

    build_tree();

    int ans = ;

    int task;

    scanf("%d", &task);

    while (task --)

    {

        scanf("%d %d %d %d", &q[], &q[], &q[], &q[]);

        for (int i = ; i <= ; ++i)

            q[i] = (q[i]+ans)%n+;

        sort(q+, q++);

        int l = , r = n;

        while (l < r)

        {

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

            if (check(mid, q[], q[], q[], q[]))

                l = mid;

            else

                r = mid-;

        }

        ans = a[b[l]];

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

    }

    return ;

}

巴特西

BZOJ 2653 middle 二分答案+可持久化线段树

最新文章

热门文章