CF1491C Pekora and Trampoline

原題鏈接 洛谷鏈接

題目翻譯
這題放 n 2 n^2 n2 過就離譜

考慮貪心，顯然每輪最開始調到第一個 s i s_i si? 不為 1 1 1 的蹦床上是最優的，因為這樣可以讓后面的 s s s 盡可能減少，
定義 c i c_i ci? 為位置 i i i 已經被踩了多少次

那么，我們貪心的從 1 1 1 開始列舉跳到的第一個蹦床，設當前列舉到第 i i i 個蹦床
由于最終這個蹦床的 s i s_i si? 會被踩到只剩 1 1 1，所以肯定會對區間 [ i + 2 , min ? ( i + s i , n ) ] [i+2,\min(i+s_i,n)] [i+2,min(i+si?,n)] 的蹦床造成 1 1 1 點貢獻（后面會講到對 i + 1 i+1 i+1 的貢獻）
由于在正常情況下，當蹦床的 s i s_i si? 達到 1 1 1 的時候，就不會再從它開始起跳了，所以這樣就不會對 i + 1 i+1 i+1 造成貢獻，只有當 s i ? c i < 1 s_i-c_i<1 si??ci?<1 的時候，也就是說從別的地方跳過來，才可以對 i + 1 i+1 i+1 做出貢獻，所以蹦床 i i i 對 i + 1 i+1 i+1 做出的貢獻為 max ? ( 0 , 1 ? ( s i ? c i ) ) \max(0,1-(s_i-c_i)) max(0,1?(si??ci?))

在考慮完對后面蹦床的貢獻后，我們考慮蹦床 i i i 對最終答案的貢獻，這個其實非常簡單，就不細說了，貢獻： max ? ( 0 , ( s i ? c i ) ? 1 ) \max(0,(s_i-c_i)-1) max(0,(si??ci?)?1)

總時間復雜度 O ( T ? n log ? n ) \mathcal O(T\cdot n\log n) O(T?nlogn)
PS: 為了美觀并且方便理解，這里只提供未開long long的代碼

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int Maxn=5010;
int n,ans;
int a[Maxn],sum[Maxn];
inline int lowbit(int x)
{
    return x&(-x);
}
void modify(int x,int v)
{
    if(x>n || x<1)return;
    while(x<=n)
    {
        sum[x]+=v;
        x+=lowbit(x);
    }
}
int query(int x)
{
    int ret=0;
    while(x)
    {
        ret+=sum[x];
        x-=lowbit(x);
    }
    return ret;
}
inline int read()
{
    int s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0' && ch<='9')s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
    return s*w;
}
int main()
{
    // freopen("in.txt","r",stdin);
    int T=read();
    while(T--)
    {
        n=read();
        for(int i=1;i<=n;++i)
        a[i]=read(),sum[i]=0;
        for(int i=1;i<=n;++i)
        {
            int tmp=a[i]-query(i);
            if(tmp>1)
            ans+=tmp-1;
            if(a[i]>1)
            modify(i+2,1),modify((i+a[i])+1,-1);
            if(tmp<1ll)
            modify(i+1,1-tmp),modify(i+2,tmp-1);
        }
        printf("%lld\n",ans);
        ans=0;
    }
    return 0;
}