[Solution] CF1998E2

· · 题解

校内 NOIP 模拟赛搬的题，是放在 T2 的 *2500。

@IceKylin 有高贵 O(n) 做法，但事实上他自己都分析不动复杂度。

题意

有点长就不贴了。

分析

我们先考虑 E1 的情形。

我们现在想要快速判定一个数能否最后留下，先看一下最大值，你发现它必胜；然后再看一下次大值，你发现只要它把自己身边小于等于自己的全吃掉后能吃掉最大值那么它也能留下；然后数值再往下也同理……你发现一个数能留下有两种情况：

1.它是最大值。

2.它把自己身边所有小于等于自己的全吃掉后能吃掉一个已经确定能留下的数。

显然在第二种情况中它只可能吃掉自己左/右边第一个大于自己的数，记为 L_i,R_i。这个东西我们可以先用单调栈求一下，然后按数值从大到小枚举每个数，按上述方法判断即可。

然后考虑 E2 的情形，要对于每个前缀求一遍，复杂度爆炸。显然每个数的贡献作用于一段区间，于是你可以考虑维护每个数的贡献区间然后差分统计答案。

我们还是按数值从大到小转移，只不过这次转移的是区间。首先第 i 个数的区间为 [i,n]，然后你再交上一些东西：

如果 i 先往左吃到 L_i+1，再往右至少吃到 x 后大于 a_{L_i}，其中要求 x\leq R_i-1，那么区间就可以与 [\max(x,l_{L_i}),r_{L_i}] 取交，x 可以通过二分简单求出。

同理可以从 R_i 的区间类似转移，当然还要考虑 i 恰为前缀最大值的情况。注意区间的交与并。

时间复杂度 O(n\log n)，具体实现见代码。

代码

//From: ifffer_2137
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define inf 0x7fffffff
#define eb emplace_back
#define pii pair<int,int>
#define mkpr make_pair
#define fir first
#define sec second
inline int read(){
    char ch=getchar();int x=0,w=1;
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+ch-48,ch=getchar();return w==1?x:-x;
}
const int maxn=1e6+5;
int T;
int n,X;
int a[maxn],s[maxn],p[maxn];
int stk[maxn],tp;
int L[maxn],R[maxn];
int x[maxn],y[maxn];
bool cmp(int x,int y){return a[x]>a[y];}
int getpos(int x){
    int l=x+1,r=R[x]-1,pos=n+1;
    while(l<=r){
        int m=(l+r)>>1;
        if(s[m]-s[L[x]]>=a[L[x]]){
            pos=m;
            r=m-1;
        }else{
            l=m+1;
        }
    }
    return pos;
}
int ans[maxn];
signed main(){
    #ifndef ONLINE_JUDGE
    freopen("data.in","r",stdin);
    freopen("test.out","w",stdout);
    #endif
    cin.tie(0),cout.tie(0);
    T=read();
    while(T--){
        n=read(),X=read();
        for(int i=1;i<=n;i++){
            ans[i]=0;x[i]=0,y[i]=n+1;
            a[i]=read();p[i]=i;
            s[i]=s[i-1]+a[i];
            L[i]=0,R[i]=n+1;
        }
        tp=0;
        for(int i=1;i<=n;i++){
            while(tp&&a[stk[tp]]<a[i]) R[stk[tp]]=i,tp--;
            stk[++tp]=i;
        }
        tp=0;
        for(int i=n;i>=1;i--){
            while(tp&&a[stk[tp]]<a[i]) L[stk[tp]]=i,tp--;
            stk[++tp]=i;
        }
        sort(p+1,p+n+1,cmp);
        for(int i=1;i<=n;i++){
            x[p[i]]=p[i],y[p[i]]=n;
            int xx=n+1,yy=0;
            if(L[p[i]]){
                int xxx=n+1,yyy=0;
                if(s[p[i]]-s[L[p[i]]]>=a[L[p[i]]]) xxx=x[L[p[i]]],yyy=y[L[p[i]]];
                else xxx=max(getpos(p[i]),x[L[p[i]]]),yyy=y[L[p[i]]];
                xx=min(xx,xxx),yy=max(yy,yyy);
            }else{
                xx=min(xx,p[i]),yy=max(yy,R[p[i]]-1);
            }
            if(R[p[i]]){
                int xxx=n+1,yyy=0;
                if(s[R[p[i]]-1]-s[L[p[i]]]>=a[R[p[i]]]) xxx=max(R[p[i]],x[R[p[i]]]),yyy=y[R[p[i]]];
                xx=min(xx,xxx),yy=max(yy,yyy);
            }
            x[p[i]]=max(x[p[i]],xx),y[p[i]]=min(y[p[i]],yy);
            if(x[p[i]]>y[p[i]]) continue;
            ans[x[p[i]]]++,ans[y[p[i]]+1]--;
        }
        for(int i=1;i<=n;i++){
            ans[i]+=ans[i-1];
            cout<<ans[i]<<" ";
        }
        cout<<"\n";
    }
    return 0;
}