BZOJ 2653 Middle

非常有趣的一道数据结构题。
非常反套路啊。

首先明确题意中对中位数的定义。如果下标从 1 开始，那么就是第 n2+1 小。
即当 n 为偶数时，取中间二项的后者。

发现这题区间大小不确定，所以我们没法以 ≤mid 的数字个数的基本二分套路求第 k 小。
但是，根据中位数的定义，发现求的是比它小的数的个数比不比它小的数的个数要少的最大的数。
于是考虑把前者当做 −1，后者当做 1。问题转化为区间和 ≥0。

进一步思考如何判定，发现 (b,c) 区间肯定是有贡献的。
除此以外，对于 [a,b] 和 [c,d] 区间，显然要贪心地分别求最大后缀和及最大前缀和。
显然线段树可以维护。

但是，如果对于每个数都开一棵线段树空间肯定不够。
再次发现如果把数排序之后依次插入，每次修改的结点数是均摊 O(logn) 的。
于是可以可持久化一下。

代码：

#include <cstdio>
#include <vector>
#include <algorithm>
#define ls(p) seg[p].lson
#define rs(p) seg[p].rson
using namespace std;
const int N = 2e4;
int n,q;
int a[N + 5],ind[N + 5],len;
struct node
{
    int val,sum,lsum,rsum;
    int lson,rson;
} seg[(N << 5) + 10];
int rt[N + 5],lastans;
vector<int> pos[N + 5];
void change(int x,int k,int &p,int tl,int tr)
{
    static int tot = 0;
    seg[++tot] = seg[p],p = tot;
    if(tl == tr)
    {
        seg[p].val = seg[p].sum = seg[p].lsum = seg[p].rsum = k;
        return ;
    }
    int mid = tl + tr >> 1;
    if(x <= mid)
        change(x,k,ls(p),tl,mid);
    else
        change(x,k,rs(p),mid + 1,tr);
    seg[p].sum = seg[ls(p)].sum + seg[rs(p)].sum;
    seg[p].lsum = max(seg[ls(p)].lsum,seg[ls(p)].sum + seg[rs(p)].lsum);
    seg[p].rsum = max(seg[ls(p)].rsum + seg[rs(p)].sum,seg[rs(p)].rsum);
}
int query_sum(int l,int r,int p,int tl,int tr)
{
    if(!p || (l <= tl && tr <= r))
        return seg[p].sum;
    int mid = tl + tr >> 1;
    int ret = 0;
    if(l <= mid)
        ret += query_sum(l,r,ls(p),tl,mid);
    if(r > mid)
        ret += query_sum(l,r,rs(p),mid + 1,tr);
    return ret;
}
int query_lsum(int l,int r,int p,int tl,int tr)
{
    if(!p || (l <= tl && tr <= r))
        return seg[p].lsum;
    int mid = tl + tr >> 1;
    int ret = 0;
    if(l <= mid && r > mid)
        ret = max(query_lsum(l,r,ls(p),tl,mid),query_sum(l,r,ls(p),tl,mid) + query_lsum(l,r,rs(p),mid + 1,tr));
    else if(l <= mid)
        ret = query_lsum(l,r,ls(p),tl,mid);
    else if(r > mid)
        ret = query_lsum(l,r,rs(p),mid + 1,tr);
    return ret;
}
int query_rsum(int l,int r,int p,int tl,int tr)
{
    if(!p || (l <= tl && tr <= r))
        return seg[p].rsum;
    int mid = tl + tr >> 1;
    int ret = 0;
    if(l <= mid && r > mid)
        ret = max(query_rsum(l,r,ls(p),tl,mid) + query_sum(l,r,rs(p),mid + 1,tr),query_rsum(l,r,rs(p),mid + 1,tr));
    else if(l <= mid)
        ret = query_rsum(l,r,ls(p),tl,mid);
    else if(r > mid)
        ret = query_rsum(l,r,rs(p),mid + 1,tr);
    return ret;
}
int main()
{
    scanf("%d",&n);
    for(register int i = 1;i <= n;++i)
        scanf("%d",a + i),ind[i] = a[i];
    sort(ind + 1,ind + n + 1);
    len = unique(ind + 1,ind + n + 1) - ind - 1;
    for(register int i = 1;i <= n;++i)
        pos[a[i] = lower_bound(ind + 1,ind + len + 1,a[i]) - ind].push_back(i);
    for(register int i = 1;i <= n;++i)
        change(i,1,rt[1],1,n);
    for(register int i = 2;i <= len;++i)
    {
        rt[i] = rt[i - 1];
        for(register int j = 0;j < pos[i - 1].size();++j)
            change(pos[i - 1][j],-1,rt[i],1,n);
    }
    scanf("%d",&q);
    int a,b,c,d;
    int l,r,mid,ans;
    while(q--)
    {
        scanf("%d%d%d%d",&a,&b,&c,&d);
        a = (a + lastans) % n,b = (b + lastans) % n,c = (c + lastans) % n,d = (d + lastans) % n;
        ++a,++b,++c,++d;
        a > b ? swap(a,b) : (void)0;
        a > c ? swap(a,c) : (void)0;
        a > d ? swap(a,d) : (void)0;
        b > c ? swap(b,c) : (void)0;
        b > d ? swap(b,d) : (void)0;
        c > d ? swap(c,d) : (void)0;
        l = 1,r = len;
        while(l <= r)
        {
            mid = l + r >> 1;
            if(query_rsum(a,b,rt[mid],1,n) + query_sum(b + 1,c - 1,rt[mid],1,n) + query_lsum(c,d,rt[mid],1,n) >= 0)
                l = mid + 1,ans = mid;
            else
                r = mid - 1;
        }
        printf("%d\n",lastans = ind[ans]);
    }
}