[国家集训队]middle

主席树的想法感觉挺妙的，但是这题数据范围这么小，直接分块草过去不就好了吗

二分是要二分的，把\(<x\)置\(-1\)，\(\ge x\)的置\(1\)，于是我们需要取一个\(\ge 0\)的区间

对询问\(a,b,c,d\)，其中\([b,c]\)是必选的,\([a,b-1]\)取后缀最大和，\([c+1,d]\)取前缀最大和

我们直接分块，对每个块的每个答案\(x\)维护一个块内和，前缀最大和和后缀最大和就可以了

然后询问的时候暴力跳块就好了

复杂度\(O(n\sqrt n+n\sqrt n \log n)\)

---

Code:

#include <cstdio>
#include <cctype>
#include <cmath>
#include <cstring>
#include <algorithm>
const int N=30010;
using std::min;
using std::max;
template <class T>
void read(T &x)
{
    x=0;char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) x=x*10+c-'0',c=getchar();
}
int yuul[200][N],yuur[200][N],bee[200][N],belong[N];
int a[N],b[N],L[200],R[200],qry[5],n,m,q;
int cal(int l,int r,int x)
{
    int lp=belong[l],rp=belong[r],ret=0;
    if(rp-lp<=1)
    {
        for(int i=l;i<=r;i++) ret+=a[i]<x?-1:1;
        return ret;
    }
    for(int i=l;i<=R[lp];i++) ret+=a[i]<x?-1:1;
    for(int i=L[rp];i<=r;i++) ret+=a[i]<x?-1:1;
    for(int i=lp+1;i<rp;i++) ret+=bee[i][x];
    return ret;
}
int rig(int l,int r,int x)
{
    if(l>r) return 0;
    int lp=belong[l],rp=belong[r],sum=0,mx=0;
    if(rp-lp<=1)
    {
        for(int i=l;i<=r;i++)
        {
            sum+=a[i]<x?-1:1;
            mx=max(mx,sum);
        }
        return mx;
    }
    for(int i=l;i<=R[lp];i++)
    {
        sum+=a[i]<x?-1:1;
        mx=max(mx,sum);
    }
    for(int i=lp+1;i<rp;i++)
    {
        mx=max(mx,sum+yuul[i][x]);
        sum+=bee[i][x];
    }
    for(int i=L[rp];i<=r;i++)
    {
        sum+=a[i]<x?-1:1;
        mx=max(mx,sum);
    }
    return mx;
}
int lef(int l,int r,int x)
{
    if(l>r) return 0;
    int lp=belong[l],rp=belong[r],sum=0,mx=0;
    if(rp-lp<=1)
    {
        for(int i=r;i>=l;i--)
        {
            sum+=a[i]<x?-1:1;
            mx=max(sum,mx);
        }
        return mx;
    }
    for(int i=r;i>=L[rp];i--)
    {
        sum+=a[i]<x?-1:1;
        mx=max(sum,mx);
    }
    for(int i=rp-1;i>lp;i--)
    {
        mx=max(mx,sum+yuur[i][x]);
        sum+=bee[i][x];
    }
    for(int i=R[lp];i>=l;i--)
    {
        sum+=a[i]<x?-1:1;
        mx=max(sum,mx);
    }
    return mx;
}
bool check(int a,int b,int c,int d,int x)
{
    return lef(a,b-1,x)+cal(b,c,x)+rig(c+1,d,x)>=0;
}
int query(int a,int b,int c,int d)
{
    int l=1,r=m;
    while(l<r)
    {
        int mid=l+r+1>>1;
        if(check(a,b,c,d,mid)) l=mid;
        else r=mid-1;
    }
    return l;
}
int main()
{
    memset(bee,-0x3f,sizeof bee);
    memset(yuul,-0x3f,sizeof yuul);
    memset(yuur,-0x3f,sizeof yuur);
    read(n);
    for(int i=1;i<=n;i++) read(a[i]),b[i]=a[i];
    std::sort(b+1,b+1+n);
    m=std::unique(b+1,b+1+n)-b-1;
    for(int i=1;i<=n;i++) a[i]=std::lower_bound(b+1,b+1+m,a[i])-b;
    int B=sqrt(n)+1,T=(n-1)/B+1;
    for(int i=1;i<=T;i++)
    {
        L[i]=R[i-1]+1,R[i]=min(L[i]+B-1,n);
        for(int j=L[i];j<=R[i];j++)
        {
            belong[j]=i;
            int sum=0,mx=0,x=a[j];
            for(int k=L[i];k<=R[i];k++)
            {
                sum+=a[k]<x?-1:1;
                mx=max(mx,sum);
            }
            yuul[i][x]=mx;
            sum=0,mx=0;
            for(int k=R[i];k>=L[i];k--)
            {
                sum+=a[k]<x?-1:1;
                mx=max(mx,sum);
            }
            yuur[i][x]=mx;
            bee[i][x]=sum;
        }
        bee[i][m+1]=yuul[i][m+1]=yuur[i][m+1]=-B;
        for(int j=m;j;j--)
        {
            bee[i][j]=max(bee[i][j],bee[i][j+1]);
            yuul[i][j]=max(yuul[i][j],yuul[i][j+1]);
            yuur[i][j]=max(yuur[i][j],yuur[i][j+1]);
        }
    }
    read(q);
    for(int las=0,i=1;i<=q;i++)
    {
        for(int j=1;j<=4;j++)
        {
            read(qry[j]);
            qry[j]=(qry[j]+las)%n+1;
        }
        std::sort(qry+1,qry+5);
        printf("%d\n",las=b[query(qry[1],qry[2],qry[3],qry[4])]);
    }
    return 0;
}

---

2019.3.17