[国家集训队]middle
主席树的想法感觉挺妙的，但是这题数据范围这么小，直接分块草过去不就好了吗
二分是要二分的，把(<x)置(-1)，(ge x)的置(1)，于是我们需要取一个(ge 0)的区间
对询问(a,b,c,d)，其中([b,c])是必选的,([a,b-1])取后缀最大和，([c+1,d])取前缀最大和
我们直接分块，对每个块的每个答案(x)维护一个块内和，前缀最大和和后缀最大和就可以了
然后询问的时候暴力跳块就好了
复杂度(O(nsqrt n+nsqrt 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
",las=b[query(qry[1],qry[2],qry[3],qry[4])]);
}
return 0;
}
2019.3.17