[国家集训队]Middle

摘要

题意:对于一个数列每次询问 ,求左端点在 右端点在 的区间的中位数的最大值。偶数的情况下标向下取整。 .

对于求这种答案在某一维度上单调的最值问题,想到二分答案。二分 mid 后,大于等于 mid 的数贡献为 1,小于 mid 的数贡献为 -1. 那么 mid 是一个区间的中位数等价于贡献和为 0. 因此问题转化为判定是否存在区间使得贡献和非负。这个可以用最大左 / 右段和在线段树上来做。

我们不可能对每个数建一个线段树,因此利用主席树的思想,我们把数按权值排序,那么当前数的线段树就建立在上个线段树上,只需要做单点修改即可。

时间复杂度 ,空间复杂度 .

#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
const int N=2e5+5,SZ=N*20;
int n,Q;

pair<int,int> a[N];

int tot;
int lc[SZ],rc[SZ];
int sum[SZ],ls[SZ],rs[SZ];
int rt[N+N];

inline void cp(int u2,int u){lc[u2]=lc[u],rc[u2]=rc[u];
    sum[u2]=sum[u],ls[u2]=ls[u],rs[u2]=rs[u];
}
inline void pushup(int u){sum[u]=sum[lc[u]]+sum[rc[u]];
    ls[u]=max(ls[lc[u]],sum[lc[u]]+max(0,ls[rc[u]]));
    rs[u]=max(rs[rc[u]],sum[rc[u]]+max(0,rs[lc[u]]));
}
int build(int l=1,int r=n){int u=++tot,mid=(l+r)>>1;
    if(l==r)return sum[u]=ls[u]=rs[u]=1, u;
    lc[u]=build(l,mid), rc[u]=build(mid+1,r);
    return pushup(u), u;
}
int modify(int pos,int v,int u,int l=1,int r=n){// 不是累加是覆盖
    int u2=++tot,mid=(l+r)>>1;
    cp(u2,u);
    if(l==r)return sum[u2]=ls[u2]=rs[u2]=v, u2;//!!!rs 写成 rc
    if(pos<=mid)lc[u2]=modify(pos,v,lc[u],l,mid);
    else rc[u2]=modify(pos,v,rc[u],mid+1,r);
    return pushup(u2), u2;
}
int query_sum(int L,int R,int u,int l=1,int r=n){if(L<=l&&r<=R)return sum[u];
    int mid=(l+r)>>1,res=0;
    if(L<=mid)res+=query_sum(L,R,lc[u],l,mid);
    if(mid<R)res+=query_sum(L,R,rc[u],mid+1,r);
    return res;
}
int query_ls(int L,int R,int u,int l=1,int r=n){if(L<=l&&r<=R)return ls[u];//!!!!!!
    int mid=(l+r)>>1;
    if(L<=mid&&mid<R)return max(query_ls(L,R,lc[u],l,mid),
                    query_sum(L,R,lc[u],l,mid)
                    +max(0,query_ls(L,R,rc[u],mid+1,r)));
    else if(L<=mid)return query_ls(L,R,lc[u],l,mid);
    else if(mid<R)return query_ls(L,R,rc[u],mid+1,r);
    else return puts("WARNING"), 0;
}
int query_rs(int L,int R,int u,int l=1,int r=n){if(L<=l&&r<=R)return rs[u];//!!!!!!
    int mid=(l+r)>>1;
    if(L<=mid&&mid<R)return max(query_rs(L,R,rc[u],mid+1,r),
                    query_sum(L,R,rc[u],mid+1,r)
                    +max(0,query_rs(L,R,lc[u],l,mid)));
    else if(L<=mid)return query_rs(L,R,lc[u],l,mid);
    else if(mid<R)return query_rs(L,R,rc[u],mid+1,r);
    else return puts("WARNING"), 0;
}

int x=0,q[5];
inline bool check(int k){#define A q[0]
#define B q[1]
#define C q[2]
#define D q[3]
    const int cur=rt[k];
    int s=(B+1<=C-1)?query_sum(B+1,C-1,cur):0;
    int l=query_rs(A,B,cur), r=query_ls(C,D,cur);
    return s+l+r>=0;
}

int main(){scanf("%d",&n);
    ls[0]=rs[0]=-0x3f3f3f3f;
    for(int i=1;i<=n;i++)scanf("%d",&a[i].first), a[i].second=i;
    sort(a+1,a+n+1);
    rt[1]=build();
    for(int i=2;i<=n+1;i++){rt[i]=modify(a[i-1].second,-1,rt[i-1]);
    }
    scanf("%d",&Q);
    for(register int i=1;i<=Q;i++){scanf("%d%d%d%d",&q[0],&q[1],&q[2],&q[3]);
        q[0]=(q[0]+x)%n+1;
        q[1]=(q[1]+x)%n+1;
        q[2]=(q[2]+x)%n+1;
        q[3]=(q[3]+x)%n+1;
        sort(q,q+4);

        // 在 a 数组上二分
        int l=1, r=n ,ans;
        while(l<=r){int mid=(l+r)>>1;
            if(check(mid))ans=mid,l=mid+1;
            else r=mid-1;
        }

        printf("%d\n",x=a[ans].first);
    }
    return 0;
}
/*
 * BUG#1:query_ls/rs 的时侯,递归终止条件用的是 l==r 导致超时
 */

  转载请注明: Sshwy's Blog [国家集训队]Middle

 上一篇
[Luogu2022] 有趣的数 [Luogu2022] 有趣的数
摘要 题意:Q(N,K) 表示把 1-N 按字典序从小到大排列后 K 的排名。给出 K,M,最小化 N,且 Q(N,K)=M. 无解输出 0。 一道思路很清奇的题。首先可以想到这些结论: 关于 i 单调递增(非严格)
2019.06.08
下一篇 
线段树应用 线段树应用
摘要 啃一下线段树的课件。不过 SYF 是真的强,放一个课件中的 Scene: 提起线段树,大家肯定想起了那端令人窒息的经历: 看题:WOC,树套树套树套树? 写题:TMD,这得写上一年啊! 看榜:报警了,为什么高中生这么快就写完了?
2019.05.21
  目录