2653: middle

分析：

　　二分答案+主席树。

　　对于中位数的经典做法，就是二分一个数，将小于的变成-1，大于等于的变成+1，那么如果sum>=0（因为+1包括等于），L=mid+1，否则R=mid-1。

　　那么考虑二分一个中位数（当然只二分出现过的数即可），然后向上面一样判断。

　　因为二分的数字只有n个，可以建立n颗只包含-1和+1的权值线段树，发现第i小的权值线段树与第i+1小的权值线段树只有一个位置不同，所以可以类似可持久化的思路，每次只去建立一条链。

　　查询的区间有很多个，不能挨个查询它们的和，由于查询最大值，所以可以再在线段树上维护左端最大子段和，右端最大子段和。

代码：

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<iostream>

#include<cmath>

#include<cctype>

#include<set>

#include<queue>

#include<vector>

#include<map>

#define pa pair<int,int>

using namespace std;

typedef long long LL;

inline int read() {

    int x=,f=;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-;

    for(;isdigit(ch);ch=getchar())x=x*+ch-'';return x*f;

}

const int N = ;

struct Node{

    int sum, Lmx, Rmx;

}T[N * ];

int ls[N * ], rs[N * ], Root[N], Index, n;

pa A[N];

Node operator + (const Node &A,const Node &B) {

    Node res;

    res.sum = A.sum + B.sum;

    res.Lmx = max(A.Lmx, A.sum + B.Lmx);

    res.Rmx = max(B.Rmx, A.Rmx + B.sum);

    return res;

}

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

    rt = ++Index;

    if (l == r) {

        T[rt].sum = T[rt].Lmx = T[rt].Rmx = ; return ;

    }

    int mid = (l + r) >> ;

    build(l, mid, ls[rt]); build(mid + , r, rs[rt]);

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

}

void update(int l,int r,int &rt,int pre,int p) {

    if (!rt) rt = ++Index;

    if (l == r) {

        T[rt].sum = T[rt].Lmx = T[rt].Rmx = -; return ;

    }

    int mid = (l + r) >> ;

    if (p <= mid) {

        rs[rt] = rs[pre];

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

    } else {

        ls[rt] = ls[pre];

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

    }

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

}

Node query(int l,int r,int rt,int L,int R) {

    if (L <= l && r <= R) return T[rt];

    int mid = (l + r) >> ;

    if (R <= mid) return query(l, mid, ls[rt], L, R);

    else if (L > mid) return query(mid + , r, rs[rt], L, R);

    else return query(l, mid, ls[rt], L, R) + query(mid + , r, rs[rt], L, R);

}

bool check(int x,int l1,int r1,int l2,int r2) {

    Node a, b, c; b.sum = ;

    if (l2 > r1 + ) b = query(, n, Root[x], r1 + , l2 - );

    a = query(, n, Root[x], l1, r1);

    c = query(, n, Root[x], l2, r2);

    return (a.Rmx + b.sum + c.Lmx) >= ;

}

int main() {

    n = read();

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

        A[i].first = read(), A[i].second = i;

    }

    sort(A + , A + n + );

    build(, n, Root[]);

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

        update(, n, Root[i], Root[i - ], A[i - ].second);

    int c[], m = read(), ans = , pos;

    while (m --) {

        for (int i = ; i < ; ++i) c[i] = (read() + ans) % n + ;

        sort(c, c + );

        int l = , r = n;

        while (l <= r) {

            int mid = (l + r) >> ;

            if (check(mid, c[], c[], c[], c[])) pos = mid, l = mid + ;

            else r = mid - ;

        }

        ans = A[pos].first;

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

    }

    return ;

}

巴特西

2653: middle

2653: middle

最新文章

热门文章