Luogu2839 [国家集训队]middle 题解

题目很好，考察对主席树的深入理解与灵活运用。

首先看看一般解决中位数的思路，我们二分一个 \(mid\)，将区间中 \(\ge mid\) 的数置为 \(1\)，小于的置为 \(-1\)，然后求区间和，若大于等于零则 \(mid\) 还能增大，否则减小。

现在就有了两个问题：第一，区间不固定；第二，每次二分一个答案就要重构区间，复杂度爆炸。

现在我们来仔细分析一下主席树的结构，首先，它是一个每个点都建了一棵线段树，形成前缀和的形式；每棵线段树又与区间有关。抽象地说，我们可以把第一个特征看作解决时间这一维限制，第二个特征解决位置这一维限制，即主席树同时解决了两维限制。

那再来找找这题的两维限制。如果我们把每次二分看做时间先后的操作，将每次二分的值作为一个“点”建线段树，就相当于预处理出了每次二分后区间的情况，省去了重构。再把权值离散化，那么就映射到了 \(1\sim n\) 的区间，对于 \(mid+1\)，显然只有 \(mid\) 这个权值由 \(1\) 变成了 \(-1\) ，这其实只是一个单点修改的操作，这样就解决了第二个问题。

对于第一个问题，我们可以用最大子段和的思路维护 \(lmax,rmax,sum\) 的 tag，那么对于题目给出的区间 \([a,b],[c,d]\) ，答案即是 \([a,b]\) 的 \(rmax\)、\([b+1,c-1]\) 的 \(sum\)，\([c,d]\) 的 \(lmax\) 之和。

哪里没有讲清楚可以看代码进一步理解。

#include <bits/stdc++.h>

#define l(x) t[x].l

#define r(x) t[x].r

using namespace std;

const int N=1e5+5;

struct Tree

{

    int l,r,lmax,rmax,sum;

    void clear() {lmax=rmax=-N,l=r=sum=0;}

}t[N*20],Ans;

int n,Q,a[N],q[4],root[N],cntnode,id[N],ans;

void build(int &rt,int l,int r)

{

    t[rt=++cntnode]=(Tree){0,0,r-l+1,r-l+1,r-l+1};

    if(l==r) return; int mid=l+r>>1;

    build(l(rt),l,mid); build(r(rt),mid+1,r);

}

inline void pushup(int rt)

{

    t[rt].lmax=max(t[l(rt)].lmax,t[l(rt)].sum+t[r(rt)].lmax);

    t[rt].rmax=max(t[r(rt)].rmax,t[r(rt)].sum+t[l(rt)].rmax);

    t[rt].sum=t[l(rt)].sum+t[r(rt)].sum;

}

void Insert(int &rt,int pre,int l,int r,int pos)

{

    t[rt=++cntnode]=t[pre];

    if(l==r) {t[rt].lmax=t[rt].rmax=t[rt].sum=-1; return;}

    int mid=l+r>>1;

    if(pos<=mid) Insert(l(rt),l(pre),l,mid,pos);

    else Insert(r(rt),r(pre),mid+1,r,pos);

    pushup(rt);

}

void query(int rt,int lc,int rc,int l,int r)

{

    if(l<=lc&&r>=rc)

    {

        Ans.lmax=max(Ans.lmax,Ans.sum+t[rt].lmax);

        Ans.rmax=max(t[rt].rmax,Ans.rmax+t[rt].sum);

        Ans.sum+=t[rt].sum;

        return;

    }

    int mid=lc+rc>>1;

    if(l<=mid) query(l(rt),lc,mid,l,r);

    if(r>mid) query(r(rt),mid+1,rc,l,r);

}

bool check(int mid)

{

    int res=0;

    if(q[1]+1<=q[2]-1)

        Ans.clear(),query(root[mid],1,n,q[1]+1,q[2]-1),res+=Ans.sum;

    Ans.clear(),query(root[mid],1,n,q[0],q[1]),res+=Ans.rmax;

    Ans.clear(),query(root[mid],1,n,q[2],q[3]),res+=Ans.lmax;

    return res>=0;

}

int main()

{

    scanf("%d",&n);

    for(int i=1;i<=n;++i) scanf("%d",a+i),id[i]=i;

    build(root[1],1,n);

    sort(id+1,id+n+1,[](int x,int y){return a[x]<a[y];});

    for(int i=2;i<=n;++i) Insert(root[i],root[i-1],1,n,id[i-1]);

    scanf("%d",&Q);

    while(Q--)

    {

        for(int i=0;i<4;++i)

            scanf("%d",q+i),q[i]=(q[i]+ans)%n+1;

        sort(q,q+4); int l=1,r=n;

        while(l<=r)

        {

            int mid=l+r>>1;

            if(check(mid)) ans=a[id[mid]],l=mid+1;

            else r=mid-1;

        }

        printf("%d\n",ans);

    }

    return 0;

}

巴特西

Luogu2839 [国家集训队]middle 题解

最新文章

热门文章