自动搬运

查看原文

来自洛谷，原作者为

	大眼仔Happy AFO（2020.9.1 - 2024.11.30）

搬运于2025-08-24 22:54:29，当前版本为作者最后更新于2024-01-25 22:24:26，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目传送门

前言

赛时感觉 6 道题唯一可以做出的题，但是赛后感觉除了三个黑题，其他也可以做一下的。看来是有场切蓝题的能力的 awa。

题解部分

考虑一个区间 $[l,r]$ 要满足什么性质才可以打出无限次：

• 打完一轮之后不能亏费。

• 最低的情况也需要保持 $\ge 0$。

对于第一种情况显然很好做，记录一个前缀和即可。对于第二种情况我们考虑如何快速的找到一个区间中最低的情况（找到谷）。对于 $a_i\ge b_i$ 的情况，全部选了肯定可以更低。选了这些之后，我们还可以再选择一个 $a_i$，或者在刚刚选择过的 $(a,b)$ 中，扔掉一个 $b$，就能达到最低点了。为了方便描述，前者记为 $d_i$（如果不选，则 $d_i=0$），后者记为 $p_i$，而区间 $[l,r]$ 的最低点 $pos=\displaystyle\sum_{i=l}^r d_i+\min_{i=l}^r p_i$。

时间复杂度为 $O(n^2)$，还需要优化。

可以发现，当 $r\to r+1$ 的时候，$pos$ 只会单调不增。那么就可以用双指针。这个时候就还有性质 1，用一个数据结构记录 $s$（前缀和）的权值，然后找到那些 $s_i\ge s_{l-1}$ 即可。左端点右移的时候 $\min$ 也要重新计算一次，也可以使用一个数据结构。时间复杂度为 $O(n\log n)$。

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
#define ll long long
ll inline read()
{
    ll num=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='0')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){num=(num<<3)+(num<<1)+(ch^48);ch=getchar();}
    return num*f;
}
int n;ll E,ans;
ll a[N],b[N],d[N],s[N],p[N],sd[N];
struct STable
{
    ll st[22][N];
    void build()
    {
        for(int i=1;i<=n;i++)st[0][i]=p[i];
        for(int i=1;(1<<i)<=n;i++)
            for(int j=1;j+(1<<i)-1<=n;j++)
                st[i][j]=min(st[i-1][j],st[i-1][j+(1<<i-1)]);
    }
    ll ask(int l,int r)
    {
        int t=__lg(r-l+1);
        return min(st[t][l],st[t][r-(1<<t)+1]);
    }
}ST;
#define lb (x&-x)
struct BIT
{
    int t[N];
    void add(int x,int v){while(x<=n+1)t[x]+=v,x+=lb;}
    int ask(int x){int res=0;while(x)res+=t[x],x-=lb;return res;}
}T;
ll c[N];
void discret(ll A[N])
{
    for(int i=0;i<=n;i++)c[i]=A[i];
    sort(c,c+1+n);int l=unique(c,c+1+n)-c-1;
    for(int i=0;i<=n;i++)A[i]=lower_bound(c,c+1+l,A[i])-c+1;
}
int main(){
    n=read();E=read();
    for(int i=1;i<=n;i++)a[i]=read();
    for(int i=1;i<=n;i++)b[i]=read();
    for(int i=1;i<=n;i++)
    {
        d[i]=min(0ll,b[i]-a[i]);
        s[i]=s[i-1]+b[i]-a[i];
        p[i]=-a[i]-d[i];
        sd[i]=sd[i-1]+d[i];
    }
    discret(s);ST.build();
    for(int L=1,R=1;L<=n;L++)
    {
        ll sum=sd[R]-sd[L-1],mn=ST.ask(L,R);
        while(R<=n)
        {
            if(sum+mn+E>=0)T.add(s[R++],1),sum+=d[R],mn=min(mn,p[R]);
            else break;
        }
        ans+=R-L-T.ask(s[L-1]-1);
        if(L==R)R++;else T.add(s[L],-1);
    }
    printf("%lld",ans);
    return 0;
}

My Stupid Mistake

赛时 $s_0$ 要离散化但是没做，发现了。双指针 $L>R$ 没有发现，导致 SubTask 4 获得 RE 而 SubTask 5 没炸，还以为被评测机针对了。

赛后再码一遍（没有原来代码了）有如下错误：

• const int N=2e5+5; 超好习惯。

• ST 表写挂了。

• int ans; 不开 long long 见祖宗。最简单的问题却总是在我发完帖才发现的。