题目链接
前言
为什么会爆栈啊,那么爆栈是什么呢,小编也不知道爆栈是什么,如果你有关于爆栈的看法,欢迎留言(留言区已关闭,调了一晚上+一早上,虽然过了,仍然有一些小问题,将在后文提出
题目大意
给你一个长度为 $n$ 的序列,同时给你 $m$ 个询问,求一个字串 $S$ ,其左端点在 $[a,b]$ ,右端点在 $[c,d]$ 内,求其最大的中位数
题解
看到有关中位数的题,我们很清晰的知道可以二分中位数的值,并将大于等于它的赋为 $1$ ,小于它的赋为 $-1$
同时,我们容易发现,区间$[b+1,c-1]$是必选的区间,所以我们只需要在 $[a,b]$ 选(至少选一个的)最大后缀,和在 $[c,d]$ 选(至少选一个的)最大前缀即可
感性理解一下,我们要使中位数最大,则应该尽量贪心的选比它大的数,致使其尽量合法
这样做的复杂度是 $O(nm\log n)$ 的。我们考虑建一棵主席树,主席树的建在原区间上,但是按照原序列的数的权值的从小到大开始建,同样的,一开始我们给每个叶子节点赋初值为 $1$ ,让 $rt[i]$ 表示从排序后第 $i$ 个值的树,其中所有在 $i$ 之前的值的位置上的数都为 $-1$ ,在其之后(包括它自己)都为 $1$ ,这样我们就可以 $O(m\log n)$ 的完成上述操作
代码
inline node merge(node &c,node a,node b)
{
c.sum=a.sum+b.sum;
c.lsum=max(a.lsum,a.sum+b.lsum);
c.rsum=max(b.rsum,b.sum+a.rsum);
return c;
}
void build(int &u,int l,int r)
{
if(!u)u=++tot;
if(l==r)return tr[u].sum=tr[u].lsum=tr[u].rsum=1,void();
int mid=(l+r)>>1;
build(tr[u].ls,l,mid);
build(tr[u].rs,mid+1,r);
merge(tr[u],tr[tr[u].ls],tr[tr[u].rs]);
}
void insert(int &u,int pre,int l,int r,int pos,int val)
{
if(!u)u=++tot;
tr[u]=tr[pre];
if(l==r)return tr[u].sum=tr[u].lsum=tr[u].rsum=val,void();
int mid=(l+r)>>1;
if(mid>=pos)
insert(tr[u].ls=0,tr[pre].ls,l,mid,pos,val);
else
insert(tr[u].rs=0,tr[pre].rs,mid+1,r,pos,val);
merge(tr[u],tr[tr[u].ls],tr[tr[u].rs]);
}
int query_sum(int u,int l,int r,int x,int y)
{
if(l>r)return 0;
if(l>=x&&r<=y)return tr[u].sum;
int mid=(l+r)>>1;
int res=0;
if(mid>=x)res+=query_sum(tr[u].ls,l,mid,x,y);
if(mid<y)res+=query_sum(tr[u].rs,mid+1,r,x,y);
return res;
}
node query__sum(int u,int l,int r,int x,int y)
{
if(l>=x&&r<=y)return tr[u];
int mid=(l+r)>>1;
node res;
if(mid>=x&&mid>=y)return query__sum(tr[u].ls,l,mid,x,y);
if(mid<y&&mid<x)return query__sum(tr[u].rs,mid+1,r,x,y);
return merge(res,query__sum(tr[u].ls,l,mid,x,y),query__sum(tr[u].rs,mid+1,r,x,y));
}
int check(int val,int l,int r,int x,int y)
{
int res=0;
res+=query_sum(rt[val],1,n,r+1,x-1);
res+=query__sum(rt[val],1,n,l,r).rsum;
res+=query__sum(rt[val],1,n,x,y).lsum;
return res>=0;
}
signed main(void)
{
n=read();
for(register int i=1;i<=n;++i)a[i].val=read(),a[i].pos=i;
sort(a+1,a+1+n,cmp);
build(rt[1],1,n);
for(register int i=2;i<=n;++i)
insert(rt[i],rt[i-1],1,n,a[i-1].pos,-1);
p=read();
int lastans=0,q[4];
for(register int i=1;i<=p;++i)
{
q[0]=(read()+lastans)%n,q[1]=(read()+lastans)%n,q[2]=(read()+lastans)%n,q[3]=(read()+lastans)%n;
sort(q,q+4);
int l=1,r=n;
while(l<=r)
{
int mid=(l+r)>>1;
if(check(mid,q[0]+1,q[1]+1,q[2]+1,q[3]+1))l=mid+1,lastans=mid;
else r=mid-1;
}
lastans=a[lastans].val;
printf("%d\n",lastans);
}
return 0;
}
后记
在本题中,我们二分的值是原序列排序后的第 $i$ 个值,而不是大小排序为 $i$ 的值,如果你不幸对数列离散化后并去重,那么你很有可能只有 $30pts$ (如果去重后过了本题,希望能够留言告诉 Caicz