题解：CF2126G2 Big Wins! (hard version)

· · 题解

思路

倒开了一手，写了 90 分钟切了。

首先发现有中位数，我们套路的扫描线扫值域。

把 \ge x 的数看成 1，剩下的数看成 -1。然后一个区间 [l,r] 的中位数 \ge x 当且仅当这个区间的和是 0 或者 1。

我们先假设我们有办法能求出所有这样区间的最小值，然后这里要说明一下，为什么中位数不是 x 但是没有影响。

因为这里的贡献式子是中位数减去最小值，最小值不变，中位数我们当成 x 来算，但是实际上 \ge x，所以答案不会算大。

然后我们考虑怎么求这个最小值。

我们设 s_i 为这个只有 -1,1 的序列的前缀和数组。然后一个位置 i 的数可能是最小值当且仅当 \displaystyle\max_{j=i}^{n}(s_j)\ge\min_{k=0}^{i-1}(s_k)。

首先我们让一个更大的数成为最小值，一定不会使答案更优，所以没有必要检验这个数到底是不是区间内最小值。然后如果上面的式子被满足了，一定能够选到两个位置，使得这两个位置的差要么是 0，要么是 1。

下面我们说明一下这个东西的正确性：

假设 s_{i-1}+1=s_i，那么直接合法了。所以我们只需要讨论其他情况。显然因为这个不等式关系，一定能选到两个数相差 0，然后就对了（上面的差指的是 s_j-s_k)。

所以对于一个位置，我们现在能快速判断他能不能成为最小值了。这里我猜想一个最小值如果某一时刻不再能作为最小值了，那么以后也不能。

下面是证明。假设我们之前对这个最小值选出两个位置 k,j 使得满足上述不等式关系。我们考虑一次会把一些位置从 1 变为 -1，观察这个东西，发现只有这个位置在 k,j 之间才有影响。

那么此时最小值不会变，最大值会变小，所以显然这个过程是不可逆的，于是结论就对了。

最后拿一个 vector 维护当前的最小值与其位置，用线段树维护 s，这样应该能做到 O(n\log n)。虽然我场上写的 set，但是区别不大。

代码

把场上的 set 换成 vector 了。

#include<bits/stdc++.h>
#define int long long
#define N 200005
#define K 20
#define mod 998244353
#define pii pair<int,int>
#define x first
#define y second
using namespace std;
int T=1,n,a[N],inf=2e9,s[N];
vector<int>e[N];
struct sgt{
    struct node{
        int mx,mn,tag;
    }tr[N<<2];
    void pushup(int u){
        tr[u].mx=max(tr[u<<1].mx,tr[u<<1|1].mx);
        tr[u].mn=min(tr[u<<1].mn,tr[u<<1|1].mn);
    }
    void build(int u,int l,int r){
        tr[u].tag=0;
        if(l==r){
            tr[u].mx=tr[u].mn=s[l];
            return;
        }
        int mid=l+r>>1;
        build(u<<1,l,mid);
        build(u<<1|1,mid+1,r);
        pushup(u);
    }
    void maketag(int u,int v){
        tr[u].mx+=v;
        tr[u].mn+=v;
        tr[u].tag+=v;
    }
    void pushdown(int u){
        maketag(u<<1,tr[u].tag);
        maketag(u<<1|1,tr[u].tag);
        tr[u].tag=0;
    }
    void modify(int u,int l,int r,int L,int R,int v){
        if(l>=L&&r<=R){
            maketag(u,v);
            return;
        }
        int mid=l+r>>1;
        pushdown(u);
        if(L<=mid)modify(u<<1,l,mid,L,R,v);
        if(R>mid)modify(u<<1|1,mid+1,r,L,R,v);
        pushup(u);
    }
    int qry_min(int u,int l,int r,int L,int R){
        if(L>R)return inf;
        if(l>=L&&r<=R)return tr[u].mn;
        int mid=l+r>>1;
        int res=inf;
        pushdown(u);
        if(L<=mid)res=min(res,qry_min(u<<1,l,mid,L,R));
        if(R>mid)res=min(res,qry_min(u<<1|1,mid+1,r,L,R));
        return res;
    }
    int qry_max(int u,int l,int r,int L,int R){
        if(L>R)return -inf;
        if(l>=L&&r<=R)return tr[u].mx;
        int mid=l+r>>1;
        int res=-inf;
        pushdown(u);
        if(L<=mid)res=max(res,qry_max(u<<1,l,mid,L,R));
        if(R>mid)res=max(res,qry_max(u<<1|1,mid+1,r,L,R));
        return res;
    }
}sgt;
void solve(int cs){
    if(!cs)return;
    cin>>n;
    for(int i=1;i<=n;i++){
        e[i].clear();
    }
    vector<pii>t;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        t.push_back({a[i],i});
        e[a[i]].push_back(i);
        s[i]=s[i-1]+1;
    }
    sort(t.begin(),t.end());
    sgt.build(1,1,n);
    int res=0;
    int cur=0;
    for(int i=1;i<=n;i++){
        for(auto p:e[i-1]){
            sgt.modify(1,1,n,p,n,-2);
        }
        while(cur<t.size()){
            auto it=t[cur];
            if(sgt.qry_max(1,1,n,it.y,n)<min(0ll,sgt.qry_min(1,1,n,1,it.y-1))){
                cur++;
            }
            else break;
        }
        if(cur==t.size())continue;
        res=max(res,i-t[cur].x);
    }
    cout<<res<<'\n';
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>T;
    for(int cs=1;cs<=T;cs++){
        solve(cs);
    }
    return 0;
}