「题解」「国家集训队互测」middle

国家集训队 的一道 二分 + 可持久化线段树 的简单题。

题目链接:Luogu P2839

题目

题目描述

一个长度为 $n$ 的序列 $a$,设其排过序之后为 $b$,其中位数定义为 $b _ \frac{n}{2}$,其中 $a,b$ 从 $0$ 开始标号,除法取下整。

给你一个长度为 $n$ 的序列 $s$。回答 $Q$ 个这样的询问:$s$ 的左端点在 $[a,b]$ 之间,右端点在 $[c,d]$ 之间的子序列中,最大的中位数。

其中 $a<b<c<d$。位置也从 $0$ 开始标号。

强制在线。

数据范围

变量数据范围
$n$$\leq 2\times 10^4$
$Q$$\leq 2.5\times 10^4$

时空限制

题目编号时间限制空间限制
Luogu P2839$2\text{s}$$500\text{MiB}$

题解

国家集训队 的神仙题。

思路

常见套路

考虑到对于一个数列 $\{a _ n\}$,如果我们选择一个数 $k$,假定为中位数。

然后把数列中小于 $k$ 的数设为 $-1$,大于 $k$ 的设成 $1$,等于 $k$ 的设为 $0$。(其实就是 $a _ i\to\operatorname{sgn}(a _ i-k)$,其中 $\operatorname{sgn}(x)$ 是符号函数)。

那么我们有一个结论

  • $\sum a _ i<0$,可以得出 $k$ 小于中位数;
  • $\sum a _ i>0$,可以得出 $k$ 大于中位数。

所以我们可以通过二分在 $\Theta(\log _ 2a)$ 时间内确定中位数

上面其实都是套路,我们需要更深层的理解。

进一步的理解

对于这道题,我们可以发现,对于下标在 $[b+1,c-1]$ 内的数字,其实都是一定要选的

如果我们要最大化中位数,我们就应该在之前的理论基础上得出这么一个结论

我们左右两边多出的部分转化后的和一定要大于 $0$,因为只有这样二分的时候才有可能使得中位数增大。

考虑实现

下面考虑如何快速处理转化后的数列,即快速转化数列。

其实很简单,用一个可持久化的线段树就搞定了。具体流程如下

  • 离散化一下给出的数列 $\{a _ n\}$。
  • 对每一个 $\text{mid}$ 都开一颗线段树(动态开点),维护三个元素:区间和,最大连续左子串,最大连续右子串。

时间复杂度为 $\Theta(n\log^2 _ 2n)$。

代码

#include<bits/stdc++.h>
using namespace std;
#define reg register
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline int read(void){
    reg char ch=getchar();
    reg int res=0;
    while(ch<'0'||'9'<ch)ch=getchar();
    while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
    return res;
}

const int MAXN=20000+5;

int n,m;
int a[MAXN];
int cnt,V[MAXN]; //离散化用数组
vector<int> pos[MAXN]; //标记每个数在哪个位置

inline int GetID(int x){ //得到离散化后的数字
    return lower_bound(V+1,V+cnt+1,x)-V;
}

namespace SegmentTree{ //动态开点线段树
    #define mid ( ( (l) + (r) ) >> 1 )
    const int MAXSIZE=MAXN*40;
    struct Node{
        int sum,lMax,rMax; //区间和,最大连续左子串,最大连续右子串
        int lson,rson; //左右儿子编号
        bool L,R; //是否存在左右儿子
        #define sum(x) unit[(x)].sum
        #define lson(x) unit[(x)].lson
        #define rson(x) unit[(x)].rson
        #define lMax(x) unit[(x)].lMax
        #define rMax(x) unit[(x)].rMax
        #define cl(x) unit[(x)].L
        #define cr(x) unit[(x)].R
    };
    int tot;
    int root[MAXN];
    Node unit[MAXSIZE];
    inline void pushup(reg int k){ //维护信息
        sum(k)=sum(lson(k))+sum(rson(k));
        lMax(k)=max(lMax(lson(k)),sum(lson(k))+lMax(rson(k)));
        rMax(k)=max(rMax(rson(k)),sum(rson(k))+rMax(lson(k)));
        return;
    }
    inline int Build(reg int l,reg int r){ //建树
        reg int k=++tot;
        if(l==r){
            if(GetID(a[l])<=1)
                sum(k)=lMax(k)=rMax(k)=-1;
            else
                sum(k)=lMax(k)=rMax(k)=1;
            return k;
        }
        cl(k)=cr(k)=true;
        lson(k)=Build(l,mid);
        rson(k)=Build(mid+1,r);
        pushup(k);
        return k;
    }
    inline int Update(reg int k,reg int y,reg int l,reg int r,reg int pos,reg int c,reg bool nc){
        if(!nc) //不存在
            k=++tot;
        if(l==r){
            sum(k)=lMax(k)=rMax(k)=c; //直接保存
            return k;
        }
        if(pos<=mid){
            if(!cr(k))
                rson(k)=rson(y); //没有右儿子,直接复制
            if(!cl(k)){
                cl(k)=true; //没有左儿子,递归更新左儿子
                lson(k)=Update(k,lson(y),l,mid,pos,c,false);
            }
            else
                lson(k)=Update(lson(k),lson(y),l,mid,pos,c,true); //简单的递归
        }
        else{
            if(!cl(k))
                lson(k)=lson(y); //赋值儿子
            if(!cr(k)){
                cr(k)=true; //递归更新
                rson(k)=Update(k,rson(y),mid+1,r,pos,c,false);
            }
            else
                rson(k)=Update(rson(k),rson(y),mid+1,r,pos,c,true); //递归更新
        }
        pushup(k); //维护信息
        return k;
    }
    inline int Query(reg int k,reg int l,reg int r,reg int L,reg int R){
        //查询区间和
        if(L<=l&&r<=R)
            return sum(k);
        reg int res=0;
        if(L<=mid)
            res+=Query(lson(k),l,mid,L,R);
        if(R>mid)
            res+=Query(rson(k),mid+1,r,L,R);
        return res;
    }
    inline Node QueryL(reg int k,reg int l,reg int r,reg int L,reg int R){
        //查询区间最大连续左子串
        if(L<=l&&r<=R)
            return unit[k];
        if(L<=mid&&mid<R){
            Node res;
            Node left=QueryL(lson(k),l,mid,L,R),right=QueryL(rson(k),mid+1,r,L,R);
            res.sum=left.sum+right.sum;
            res.lMax=max(left.lMax,left.sum+right.lMax);
            return res;
        }
        else if(L<=mid)
            return QueryL(lson(k),l,mid,L,R);
        else
            return QueryL(rson(k),mid+1,r,L,R);
    }
    inline Node QueryR(reg int k,reg int l,reg int r,reg int L,reg int R){
        //查询区间最大连续右子串
        if(L<=l&&r<=R)
            return unit[k];
        if(L<=mid&&mid<R){
            Node res;
            Node left=QueryR(lson(k),l,mid,L,R),right=QueryR(rson(k),mid+1,r,L,R);
            res.sum=left.sum+right.sum;
            res.rMax=max(right.rMax,right.sum+left.rMax);
            return res;
        }
        else if(L<=mid)
            return QueryR(lson(k),l,mid,L,R);
        else
            return QueryR(rson(k),mid+1,r,L,R);
    }
    #undef mid
}

using namespace SegmentTree;

int A,B,C,D; //询问用数

inline bool check(reg int val){
    reg int size=0;
    if(B+1<=C-1)
        size=Query(root[val],1,n,B+1,C-1); //必选数之和
    reg int L=QueryL(root[val],1,n,C,D).lMax; //左部最大值
    reg int R=QueryR(root[val],1,n,A,B).rMax; //右部最大值
    return (L+size+R)>=0;
}

int main(void){
    n=read();
    for(reg int i=1;i<=n;++i){
        a[i]=read();
        V[++cnt]=a[i];
    }
    sort(V+1,V+cnt+1);
    cnt=unique(V+1,V+cnt+1)-(V+1); //离散化
    for(int i=1;i<=n;++i)
        pos[GetID(a[i])].push_back(i);
    root[1]=Build(1,n);
    for(reg int i=2;i<=cnt;++i)
        for(reg int j=0,size=pos[i-1].size();j<size;++j)
            root[i]=Update(root[i],root[i-1],1,n,pos[i-1][j],-1,root[i]>0); //建树
    reg int Q=read();
    reg int lastans=0;
    while(Q--){
        static int q[4]; //强制在线用的数组
        A=read(),B=read(),C=read(),D=read();
        q[0]=(A+lastans)%n+1,
        q[1]=(B+lastans)%n+1,
        q[2]=(C+lastans)%n+1,
        q[3]=(D+lastans)%n+1,
        sort(q,q+4);
        A=q[0],B=q[1],C=q[2],D=q[3];
        reg int l=1,r=cnt,mid,ans=0; //二分答案
        while(l<=r){
            mid=(l+r)>>1;
            if(check(mid))
                ans=mid,l=mid+1;
            else
                r=mid-1;
        }
        printf("%d\n",lastans=V[ans]); //输出答案
    }
    return 0;
}

相关题目