P2839 [国家集训队] middle 题解

· · 题解

为啥没人写这个思路，可能是区间修改主席树不好写吧。

首先看到中位数这种只关注相对排名的东西肯定是要二分了。

用形式化的东西刻画这个 check ：

设 g(l,r,x) 表示区间 [l,r] 中 <x 的个数

区间 [l,r] 的中位数 \ge x \iff g(l,r,x)\times 2 \le r-l+1

发现求出 g 是重点。

这个 g 显然可以拆成两个前缀和相减。

设 g(i,x) 表示区间 [1,i] 中 <x 的个数

则上面的东西又可以表示成 :

(g(r,x)-g(l-1,x)) \times 2 \le r-l+1

移项，分离 l,r：

r-g(r,x)\times 2 \ge l-1-g(l-1,x)\times2

在本题中有： l\in[a,b],r\in[c,d]。

如果没有 x 的限制 g 就是个前缀和，加上限制，就是个主席树。

考虑用主席树维护这个信息，第 x 棵树维护 i-g(i,x)\times2 即可。

回到 check，贪心考虑，就是 [c,d] 中的 max 和 [a,b] 中的 min 来比较是最好的。

最后思考实现，考察一个位置加入主席树的时候需要哪些操作，以及查询的时候需要哪些操作。

考虑到这个位置 i 会使得后缀 [i,n] 的 g 全部 +1,相当于区间加法

相当于求区间 max,min。

直接写个标记永久化的区间修改主席树即可，注意 pushup 的时候别忘了加上自己的 add。tr[u].maxv=max(tr[ls].maxv,tr[rs].maxv)+tr[u].add;

附上AC代码：

#include<bits/stdc++.h>
#define ls tr[u].l
#define rs tr[u].r
using namespace std;
const int N=2e4+10,Inf=1e6;
int a[N];
struct Tree
{
    int l,r;
    int maxv,minv;
    int add;
}tr[N*30];
int root[N],idx;
int n,m,q;
vector<int> nums;
vector<int> Pos[N];

inline void pushup(int u)
{
    tr[u].maxv=max(tr[ls].maxv,tr[rs].maxv);
    tr[u].minv=min(tr[ls].minv,tr[rs].minv);
}

inline int build(int l,int r)
{
    int u=++idx;
    if(l==r) tr[u]={0,0,l,l,0};
    else
    {
        int mid=l+r>>1;
        ls=build(l,mid),rs=build(mid+1,r);
        pushup(u);
    }
    return u;
}

inline int modify(int p,int l,int r,int ql,int qr,int c)
{
    int u=++idx;
    tr[u]=tr[p];
    if(l>=ql && r<=qr) tr[u].maxv+=c,tr[u].minv+=c,tr[u].add+=c;
    else
    {
        int mid=l+r>>1;
        if(ql<=mid) ls=modify(tr[p].l,l,mid,ql,qr,c);
        if(qr>mid) rs=modify(tr[p].r,mid+1,r,ql,qr,c);
        tr[u].maxv=max(tr[ls].maxv,tr[rs].maxv)+tr[u].add;
        tr[u].minv=min(tr[ls].minv,tr[rs].minv)+tr[u].add;
    }
    return u;
}

inline int query_max(int u,int l,int r,int ql,int qr,int c)
{
    if(!u) return -Inf;
    if(l>=ql && r<=qr) return tr[u].maxv+c;
    else
    {
        c+=tr[u].add;
        int mid=l+r>>1,res=-Inf;
        if(ql<=mid) res=max(res,query_max(ls,l,mid,ql,qr,c));
        if(qr>mid) res=max(res,query_max(rs,mid+1,r,ql,qr,c));
        return res;
    }
}

inline int query_min(int u,int l,int r,int ql,int qr,int c)
{
    if(!u) return Inf;
    if(l>=ql && r<=qr) return tr[u].minv+c;
    else
    {
        c+=tr[u].add;
        int mid=l+r>>1,res=Inf;
        if(ql<=mid) res=min(res,query_min(ls,l,mid,ql,qr,c));
        if(qr>mid) res=min(res,query_min(rs,mid+1,r,ql,qr,c));
        return res;
    }
}

inline int solve(int a,int b,int c,int d)
{
    int l=1,r=m,ans=1;
    while(l<=r)
    {
        int mid=l+r>>1,k=mid-1;
        int A=query_max(root[k],0,n,c,d,0),B=query_min(root[k],0,n,a-1,b-1,0);
        if(A>=B) ans=mid,l=mid+1;
        else r=mid-1;
    }
    return nums[ans-1];
}

signed main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);

    tr[0].maxv=-Inf,tr[0].minv=Inf;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i],nums.push_back(a[i]);

    sort(nums.begin(),nums.end());
    nums.erase(unique(nums.begin(),nums.end()),nums.end());
    m=nums.size();

    for(int i=1;i<=n;i++) a[i]=lower_bound(nums.begin(),nums.end(),a[i])-nums.begin()+1,Pos[a[i]].push_back(i);

    root[0]=build(0,n);
    for(int i=1;i<=m;i++)
    {
        root[i]=root[i-1];
        for(auto x:Pos[i]) root[i]=modify(root[i],0,n,x,n,-2);
    }

    int ans=0;
    cin>>q;
    while(q--)
    {
        int a,b,c,d;
        cin>>a>>b>>c>>d;
        a=(a+ans)%n,b=(b+ans)%n,c=(c+ans)%n,d=(d+ans)%n; 
        vector<int> vec;vec.push_back(a+1),vec.push_back(b+1),vec.push_back(c+1),vec.push_back(d+1);
        sort(vec.begin(),vec.end());
        a=vec[0],b=vec[1],c=vec[2],d=vec[3];
        ans=solve(a,b,c,d);
        cout<<ans<<"\n";
    }

    return 0;
}

跑得还挺快，只有 2.03s。 感觉比维护啥最大子段和好写。