LuoP2839 [国家集训队]middle

主席树好题,点个赞！
这道题让我知道了,主席树不只是维护权值线段树。也是可以去像普通线段树一样操作的.
首先,关于求区间中位数的一个小\(trick\)(反正我之前没听说过)
二分答案
将大于等于\(mid\)的值看做\(1\)，小于\(mid\)的看做\(-1\)
那么如果区间和大于等于\(0\),则说明区间中位数大于等于\(mid\)(因为此题定义偶数个元素时,中位数为中间靠前的一个,如果是靠后的就要严格大于了)
之后,发现这个左端点和右端点不固定有点恶心.但是\([b + 1,c - 1]\)是一定要选的,所以\([b + 1,c - 1]\)这个区间和的贡献是要算的
所以我们先算这一区间的值。然后区间\([a,b]\),\([c,d]\).我们最优选,就是最大前缀后缀和啊
所以要维护区间和，最大左起子段和,最大右起子段和

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cctype>
#define LL long long
const int N = 2e4 + 3;
struct node{
    int sum;
    int lsum,rsum;
    int lc,rc;
}a[N << 6];
struct inf{
    LL val;
    int pos;    
}v[N];
int rt[N];
int n,q,t;
inline LL read(){
    LL v = 0,c = 1;char ch = getchar();
    while(!isdigit(ch)){
        if(ch == '-') c = -1;
        ch = getchar(); 
    }
    while(isdigit(ch)){
        v = v * 10 + ch - 48;
        ch = getchar(); 
    }
    return v * c;   
}
inline void pushup(int u){
    a[u].sum = a[a[u].lc].sum + a[a[u].rc].sum;
    a[u].lsum = std::max(a[a[u].lc].lsum,a[a[u].lc].sum + a[a[u].rc].lsum);
    a[u].rsum = std::max(a[a[u].rc].rsum,a[a[u].rc].sum + a[a[u].lc].rsum);
}
inline void build(int &u,int l,int r){
    u = ++t;
    if(l == r){
        a[u].sum = a[u].lsum = a[u].rsum = 1;
        return ;    
    }
    int mid = (l + r) >> 1;
    build(a[u].lc,l,mid);
    build(a[u].rc,mid + 1,r);
    pushup(u);
}
inline void ins(int &u,int l,int r,int x){
    a[++t] = a[u];  
    u = t;
    if(l == r){
        a[u].sum = -1;
        a[u].lsum = -1;
        a[u].rsum = -1;
        return ;
    }
    int mid = (l + r) >> 1;
    if(x <= mid) ins(a[u].lc,l,mid,x);
    else ins(a[u].rc,mid + 1,r,x);
    pushup(u);
}
inline int query_sum(int u,int l,int r,int ll,int rr){
    if(rr < ll) return 0;
    if(l == ll && r == rr) return a[u].sum;
    int mid = (l + r) >> 1;
    if(rr <= mid) return query_sum(a[u].lc,l,mid,ll,rr);
    else if(ll > mid) return query_sum(a[u].rc,mid + 1,r,ll,rr);
    else return query_sum(a[u].lc,l,mid,ll,mid) + query_sum(a[u].rc,mid + 1,r,mid + 1,rr);  
}
inline int query_lsum(int u,int l,int r,int ll,int rr){
    if(rr < ll) return 0;
    if(l == ll && r == rr) return a[u].lsum;
    int mid = (l + r) >> 1;
    if(rr <= mid) return query_lsum(a[u].lc,l,mid,ll,rr);
    else if(ll > mid) return query_lsum(a[u].rc,mid + 1,r,ll,rr);
    else return std::max(query_lsum(a[u].lc,l,mid,ll,mid),query_sum(a[u].lc,l,mid,ll,mid) 
    + query_lsum(a[u].rc,mid + 1,r,mid + 1,rr));
}
inline int query_rsum(int u,int l,int r,int ll,int rr){
    if(rr < ll) return 0;
    if(l == ll && r == rr) return a[u].rsum;
    int mid = (l + r) >> 1;
    if(rr <= mid) return query_rsum(a[u].lc,l,mid,ll,rr);
    else if(ll > mid) return query_rsum(a[u].rc,mid + 1,r,ll,rr);
    else return std::max(query_rsum(a[u].rc,mid + 1,r,mid + 1,rr),query_sum(a[u].rc,mid + 1,r,mid + 1,rr) + 
    query_rsum(a[u].lc,l,mid,ll,mid));  
}
inline bool check(int mid,int Q1,int Q2,int Q3,int Q4){
    int res = 0;
    //printf("%d %d %d %d\n",Q1,Q2,Q3,Q4);
    res += query_sum(rt[mid],1,n,Q2 + 1,Q3 - 1);
    res += query_rsum(rt[mid],1,n,Q1,Q2);
    res += query_lsum(rt[mid],1,n,Q3,Q4);
    return res >= 0;
}
inline bool cmp(inf x,inf y){
    return x.val < y.val;
}
int main(){
    n = read();
    for(int i = 1;i <= n;++i){
        v[i].val = read();
        v[i].pos = i;   
    }
    std::sort(v + 1,v + n + 1,cmp);
    build(rt[1],1,n);
    for(int i = 2;i <= n + 1;++i) {
        rt[i] = rt[i - 1];
        ins(rt[i],1,n,v[i - 1].pos);
    }
    q = read();
    LL last = 0,Q[4];
    while(q--){
        for(int i = 0;i < 4;++i) Q[i] = (read() + last ) % n + 1;
        std::sort(Q,Q + 4);
        int l = 1,r = n,ans;
        while(l <= r){
            int mid = (l + r) >> 1;//printf("%d\n",mid);
            if(check(mid,Q[0],Q[1],Q[2],Q[3])) ans = mid,l = mid + 1;
            else r = mid - 1;   
        }
        printf("%lld\n",last = v[ans].val);
    }
    return 0;   
}