P10083 [GDKOI2024 提高组] 不休陀螺 题解

· · 题解

题目传送门

前言

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

题解部分

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

对于第一种情况显然很好做，记录一个前缀和即可。对于第二种情况我们考虑如何快速的找到一个区间中最低的情况（找到谷）。对于 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 没炸，还以为被评测机针对了。

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