[国家集训队]middle

· · 个人记录

题目

求解一个区间的中位数：

二分一个值mid，将\geq mid的位置标记为-1，其余为1，如果此时这个区间的和\geq 0则说明中位数可以更大，否则只能更小

在这道题中，区间左右端点不确定，要最大化中位数；二分mid之后每个位置是1或者-1就已经被确定了，考虑处理某个mid对应的这个序列；[b+1,c- 1]的部分一定被包含在区间中，[a,b],[c,d]任选，中位数越大越好的话显然就是选择[a,b]的最大后缀和[c,d]的最大前缀，用线段树就可以维护区间这些值

关键是mid会变化，也就是说对于每个mid都要建一棵线段树；考虑每个位置无非只有1和-1两种情况，而且随着mid的变大只会被修改一次（从1到-1），可以用主席树完成

算法流程：对于每个mid（显然要离散化）从小到大建主席树，二分时在对应mid的线段树上查询即可，时间复杂度O(nlog^2n)

#include<bits/stdc++.h>
#define N 20005
#define ls t[rt].ch[0]
#define rs t[rt].ch[1]
using namespace std;
int n,q,a[N],b[N],len;
int root[N],RR[N],ndsum;
pair<int,int> modi[N];

struct Node
{
    int ch[2],pre,suf,sum;
}t[N*50];

template <class T> inline T Max(T a,T b) { return a > b ? a : b; }
template <class T> inline T Min(T a,T b) { return a < b ? a : b; }
template <class T> inline void read(T &x)
{
    char c; int sign=1;
    while((c=getchar())>'9'||c<'0') if(c=='-') sign=-1; x=c-48;
    while((c=getchar())>='0'&&c<='9') x=(x<<1)+(x<<3)+c-48; x*=sign;
}

inline void pushup(int rt)
{
    t[rt].sum = t[ls].sum + t[rs].sum;
    t[rt].pre = Max(t[ls].pre,t[ls].sum + t[rs].pre);
    t[rt].suf = Max(t[rs].suf,t[rs].sum + t[ls].suf);
}
void modify(int &rt,int cp,int l,int r,int x,int v)
{
    rt = ++ndsum;
    t[rt] = t[cp];
    if(l == r)
    {
        t[rt].sum = t[rt].pre = t[rt].suf = v;
        return;
    }
    int mid = (l + r) >> 1;
    if(x <= mid) modify(ls,t[cp].ch[0],l,mid,x,v);
    else modify(rs,t[cp].ch[1],mid + 1,r,x,v);
    pushup(rt);
}
Node query(int rt,int l,int r,int x,int y)
{
    if(x > y) { Node a; a.sum = 0; return a; }
    if(x <= l && r <= y) return t[rt];
    int mid =(l + r) >> 1;
    if(y <= mid) return query(ls,l,mid,x,y);
    if(x > mid) return query(rs,mid + 1,r,x,y);
    Node ret,L = query(ls,l,mid,x,y),R = query(rs,mid + 1,r,x,y);
    ret.sum = L.sum + R.sum;
    ret.pre = Max(L.pre,L.sum + R.pre);
    ret.suf = Max(R.suf,R.sum + L.suf);
    return ret;
}
void build(int &rt,int l,int r)
{
    rt = ++ndsum;
    if(l == r)
    {
        t[rt].sum = t[rt].pre = t[rt].suf = 1;
        return;
    }
    int mid = (l + r) >> 1;
    build(ls,l,mid);
    build(rs,mid + 1,r);
    pushup(rt);
}
void init()
{
    build(root[0],1,n);
    for(int i=1;i<=n;++i)
    {
        modify(root[i],root[i - 1],1,n,modi[i].second,-1);
        RR[modi[i].first] = i;
    }
}
bool check(int id,int a,int b,int c,int d)
{
    Node L = query(root[RR[id - 1]],1,n,a,b);
    Node R = query(root[RR[id - 1]],1,n,c,d);
    Node M = query(root[RR[id - 1]],1,n,b + 1,c - 1);
    return ((L.suf + R.pre + M.sum) >= 0);
}

int main()
{
    read(n);
    for(int i=1;i<=n;++i) read(a[i]),b[++len] = a[i];
    sort(b + 1,b + len + 1); len = unique(b + 1,b + len + 1) - b - 1;
    //有len棵线段树 
    for(int i=1;i<=n;++i)
    {
        a[i] = lower_bound(b + 1,b + len + 1,a[i]) - b;
        modi[i] = make_pair(a[i],i);
    }
    sort(modi + 1,modi + n + 1);
    init();//建树 

    int lasans = 0;
    read(q);
    while(q--)
    {
        int qwq[5];
        for(int i=1;i<=4;++i) read(qwq[i]),qwq[i] = (qwq[i] + lasans) % n;
        sort(qwq + 1,qwq + 5);
        for(int i=1;i<=4;++i) ++qwq[i];
        int ans = 1,l = 1,r = len;
        while(l <= r)
        {
            int mid = (l + r) >> 1;
            if(check(mid,qwq[1],qwq[2],qwq[3],qwq[4])) ans = mid,l = mid + 1;
            else r = mid - 1;
        }
        printf("%d\n",b[ans]);
        lasans = b[ans] % n;
    }
    return 0;
}