二分、队列、差分、前缀和

容易发现题目答案存在单调性，考虑二分答案。难点在于如何检查答案合法性。

注意答案上界为 $10^9 + 10^6$，过小的二分上界会导致错误。

Solution 1：使用队列维护在位置 $i$ 左侧，对位置 $i$ 有贡献的所有位置，以及在位置 $i$ 右侧，对位置 $i$ 有贡献的所有位置，然后计算当前位置的快乐值。注意一个位置如果能产生贡献，则其会对自身产生两次贡献，应该减掉一次贡献。

时间复杂度 $O(n \log V)$。

#include<bits/stdc++.h>
using namespace std;
int n,m,ans,a[1'000'005];
bool on[1'000'005];
bool fail(long long x){
    static long long w[1'000'005];
    long long sum=0ll;
    queue<int> q;
    fill(w+1,w+n+1,0ll);
    for(int i=1;i<=n;i++){
        if(on[i]) q.push(i),sum+=x;
        if(!q.empty()&&q.front()<=i-x) q.pop();
        w[i]+=sum,sum-=q.size();
    }
    while(!q.empty()) q.pop();
    sum=0ll;
    for(int i=n;i>=1;i--){
        if(on[i]) q.push(i),sum+=x;
        if(!q.empty()&&q.front()>=i+x) q.pop();
        w[i]+=sum,sum-=q.size();
    }
    for(int i=1;i<=n;i++) if(on[i]) w[i]-=x;
    for(int i=1;i<=n;i++) if(w[i]<a[i]) return 1;
    return 0;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=m;i++){
        static int x;
        cin>>x,on[x]=1;
    }
    long long l=0ll,r=1'001'000'000ll;
    while(l<=r){
        auto mid=(l+r)>>1;
        if(fail(mid)) l=mid+1;
        else ans=mid,r=mid-1;
    }
    cout<<ans<<'\n';
    return 0;
}

Solution 2：容易发现一个数向右和向左的贡献分别为公差为 $-1$ 和 $1$ 的等差数列，考虑使用差分与前缀和计算贡献。

首先考虑向右的贡献，如果位置 $i$ 能产生 $k$ 的贡献，那么贡献就是在区间 $[i,i+k-1]$ 上首项为 $k$ 公差为 $-1$ 的等差数列。

首先处理公差的部分，先在位置 $i$ 加 $-1$，在位置 $i+k$ 加 $1$，然后做一遍前缀和。接着在位置 $i+k$ 加 $k$ 后再做一遍前缀和。这样能让区间 $[i,i+k-1]$ 加上一个首项为 $-1$，公差为 $-1$ 的等差数列。不直接在位置 $\bf{i+1}$ 加 $\bf{-1}$ 的原因是不便处理 $\bf{k=0}$ 的情况。

然后处理首项，第一次前缀和结束后在位置 $i$ 加 $k+1$，在位置 $i+k$ 减 $k+1$，这样的话第二次前缀和能让区间 $[i,i+k-1]$ 加上 $k+1$。注意差分数组的边界。

向左的贡献只需要反转序列再做一次。与解法一相同的是，一个能产生贡献的位置会对自身产生两次贡献，需要减掉这部分贡献。

时间复杂度 $O(n \log V)$。

#include<bits/stdc++.h>
using namespace std;
long long w[1'000'005],sum[1'000'005];
int n,m,ans,a[1'000'005],b[1'000'005];
void calculate(long long x){
    fill(sum,sum+n+5,0ll);
    for(int i=1;i<=m;i++) --sum[b[i]],++sum[min(b[i]+x,n+1ll)];
    for(int i=1;i<=n;i++) sum[i]+=sum[i-1];
    for(int i=1;i<=m;i++) sum[min(b[i]+x,n+1ll)]+=x;
    for(int i=1;i<=m;i++) sum[b[i]]+=x+1,sum[min(b[i]+x,n+1ll)]-=x+1;
    for(int i=1;i<=n;i++) sum[i]+=sum[i-1];
}
bool fail(long long x){
    fill(w+1,w+n+1,0ll);
    calculate(x);
    for(int i=1;i<=n;i++) w[i]+=sum[i];
    for(int i=1;i<=n;i++) b[i]=n-b[i]+1;
    calculate(x);
    reverse(sum+1,sum+n+1);
    for(int i=1;i<=n;i++) w[i]+=sum[i];
    for(int i=1;i<=n;i++) b[i]=n-b[i]+1;
    for(int i=1;i<=m;i++) w[b[i]]-=x;
    for(int i=1;i<=n;i++) if(w[i]<a[i]) return 1;
    return 0;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=m;i++) cin>>b[i];
    long long l=0ll,r=1'001'000'000ll;
    while(l<=r){
        auto mid=(l+r)>>1;
        if(fail(mid)) l=mid+1;
        else ans=mid,r=mid-1;
    }
    cout<<ans<<'\n';
    return 0;
}