题解：P11677 [USACO25JAN] Shock Wave P

· · 题解

场上奋战两个半小时，最后二十分钟推出来性质，最后获得零分。

这个题要你刻画的是若干个绝对值函数的加和的性质。

我们把问题变成维护一个一开始全为 0 的序列 b，每次给序列 b 加上一个绝对值函数，问需要多少次使得 \forall i,b_i\geq a_i。

既然刻画不明白，我们先考虑一些简单的性质。首先我们可以发现一件事情是你操作不同的位置，对 \sum b_i 的贡献是不同的，具体来说，操作位置 1 和 n 能使序列 b 的和单次增加最多。

然后你发现如果同时在 1 和 n 上做操作相当于给每个 b_i 都加上 n-1，从而我们可以使用这个策略通过 sub1，容易证明这是最优的。

继续观察。注意到如果你同时选了 i 和 n-i，这个操作肯定不如选 1 和 n，所以我们得到结论 i 和 n-i 不能同时选。

很可惜这个结论没有用，但是令人惊讶的是这个结论是可以推广的，具体来说，如果你操作了两个位置 1<x<y<n，你不如操作 x-1 和 y+1。

由此归纳出一个结论：在最优解中一定是选了若干个 1，若干个 n，和**一个**其他位置。证明考虑假如现在有两个不为 1 或 n 的位置，一定可以通过上面的变化把其中一个变成 1 或 n）

问题变成下面这个形式，设 1 操作了 x 次，n 操作了 y 次，还在位置 m 选了一个数，则有限制 \forall i,ix+(n-i)y+|m-i|\geq a_i，你需要最小化 x+y 的值。

我们先考虑暴力是怎么做，首先枚举一个 m，因为我们要求的是 x+y 的最小值，把 x+y 提出来处理，然后就可以二分答案，既 (x+y)(n-i)+(2i-n)x+|m-i|\geq a_i ，可以对其二分，会得到若干对 x 的限制，时间复杂度 O(n^2\log V)。

接下来我们观察到第二个性质：如果规定只能操作 1 和 n，得到的答案最多比最优解多 1。

这个结论是显然的，因为选择的 m 显然可以用一个 1 和一个 n 代替，从而可以取到 ans+1。

我们可以先二分答案求出来只用 1 和 n 时的答案，设为 ans，接下来我们只需要判断 ans-1 是否能被取到。

我们希望对于不同的 m 同时维护 check 的结果。可以先把式子列出来，不妨设 2i \geq n，则需要 x \geq \dfrac{a_i+(x+y)(n-i)+|m-i|}{2i-n}，由于我们需要 check 的答案固定，所以右边其实是个常数。

接下来考虑 m 改变对这个式子的影响，注意到对于一个 i，|m-i| 的变化量是 O(n) 的，所以实际上右边式子的值只会改变 O(\dfrac{n}{2i-n}) 次，这是可以维护的。

具体来说我们可以用一个优先队列维护当前最严格的限制，这样做时间复杂度是 O(n\log n\log V) 的，但是注意到操作是 O(n\log n) 次区间取 \max，只需要在最后输出每个位置的值，可以使用猫树优化，这样时间复杂度是 O(n\log V) 的。

实际上 2i-n 可以是一个负数，也可以是 0，需要特判。

代码正在赶工中，因为负数除负数上下取整实在写不明白了。

upd on 2.6: 奋战四个小时终于把代码写出来了，感觉其实和季风差不多，但是写不明白啊。

//非常优美的题，但是代码太毒瘤了 
#include<bits/stdc++.h>
using namespace std;
#define int long long
int Abs(__int128 x){if(x<0)return -x;return x;}
__int128 chu(__int128 x,int y){
    //向上取整
    return (x+y-1)/y;
}
__int128 Chu(__int128 x,int y){
    //向下取整
    if(x<=0 and y<0)return (-x)/(-y);
    else return -1;
}
int n;
__int128 a[500005];int b[500005];
bool check(__int128 x){
    __int128 L = 0,R = x;
    for(int i = 0;i<=n;i++){
        if(2*i == n){
            if(x*(n-i)<a[i])return 0;
            continue;
        }
        if(2*i<n){
            //是一个负数
            __int128 C = a[i]-(n-i)*x;
            R = min(R,Chu(C,2*i-n)); 
        }else{
            __int128 C = a[i]-(n-i)*x;
            L = max(L,chu(C,2*i-n));
        }
    }
    return (L<=R);
}
struct heap{
    priority_queue<int,vector<int>,greater<int> >q,del;
    void clear(){while(q.size())q.pop();while(del.size())del.pop();}
    void Delete(int x){del.push(x);}
    void Insert(int x){q.push(x);}
    int top(){
        while(del.size() and q.top() == del.top())q.pop(),del.pop();
        return q.top();
    }
}ql,qr;
vector<int>addl[500005],dell[500005],addr[500005],delr[500005];
void Addl(int l,int r,int x,int id){
    //给一段区间加上 x 的限制
    addl[l].push_back(-x),dell[r+1].push_back(-x); 
}
void Addr(int l,int r,int x,int id){
    addr[l].push_back(x),delr[r+1].push_back(x);
}

int work(int X){
    ql.clear(),qr.clear();
    ql.Insert(0),qr.Insert(X);
    for(int i =0;i<=n+1;i++)addl[i].clear(),dell[i].clear(),addr[i].clear(),delr[i].clear();
    int i = n;
    for(int i = 0;i<=n;i++)a[i] -= (n-i)*X; 
    while(2*i>n){
        // n-2i
        int now = i;
        while(now<=n){
            // (0,a] 算一段
            //算出和这个点值相同的最远的点
            __int128 C = a[i]-abs(now-i),to = 0;
            //对于更远的点 C 的数值会减小
            if(C<=0){
                to = 0;
            }else{
                to = C/(2*i-n)*(2*i-n)+1;
                if(C%(2*i-n) == 0)to = C-(2*i-n)+1;
            }
            int r = min(Abs(to-C)+now,n);

            if(C>0){
                Addl(now,r,chu(C,i*2-n),i);
            }
            now = r+1;
        }
        now = i-1;
        while(now>=0){
            __int128 C = a[i]-abs(now-i),to = 0;
            if(C<=0){
                to = 0;
            }else{
                to = C/(n-2*i)*(n-2*i)+1;
                if(C%(2*i-n) == 0)to = C-(2*i-n)+1;
            } 
            int l = max(now-Abs(to-C),0ll);
            if(C>0){
                Addl(l,now,chu(C,i*2-n),i);
            }
            now = l-1;
        }
        --i;
    }
    i = 0;
    while(2*i<n){
        int now = i;
        while(now<=n){
            __int128 C = a[i]-abs(now-i),to = 0;
            if(C<=0){
                to = -C;
                if(to%(n-2*i)!=0)to += (n-2*i)-to%(n-2*i);
                else to += (n-2*i);
                --to;
                to = -to;
            }else{
                to = 0;
            }
            int r = min(Abs(to-C)+now,n);
            if(C>0)Addr(now,r,-1,i);
            else Addr(now,r,Chu(C,i*2-n),i);
            now = r+1;
        }
        now = i-1;
        while(now>=0){
            __int128 C = a[i]-abs(now-i),to = 0;
            if(C<=0){
                to = -C;
                if(to%(n-2*i)!=0)to += (n-2*i)-to%(n-2*i);
                else to += (n-2*i);
                --to;
                to = -to;
            }else{
                to = 0;
            }
            int l = max(now-Abs(to-C),0ll);
            if(C>0)Addr(l,now,-1,i);
            else Addr(l,now,Chu(C,i*2-n),i);
            now = l-1; 
        }
        ++i;
    }
    for(int i = 0;i<=n;i++){
        for(auto x:addl[i])ql.Insert(x);
        for(auto x:dell[i])ql.Delete(x);
        for(auto x:addr[i])qr.Insert(x);
        for(auto x:delr[i])qr.Delete(x);
        if(n%2 == 0 and (a[n/2]-abs(n/2-i))>0)continue;
        int L = -ql.top(),R = qr.top();
        if(L<=R)return 1;
    }
    return 0;
}
void solve(){
    cin >> n;--n;
    for(int i = 0;i<=n;i++)cin >> b[i];for(int i = 0;i<=n;i++)a[i] = b[i];
    __int128 sum = 0;int mx = 0;for(int i = 0;i<=n;i++)sum += b[i],mx = max(mx,b[i]);
    int l = sum/n/n,r = 2*(mx+n-1)/n;
    while(l<r){
        int mid = l+r>>1;
        if(check(mid))r = mid;
        else l = mid+1;
    }
    int ans = r;
    if(ans>1 and work(ans-2))--ans;
    cout << ans << '\n';
}
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t;cin >> t;;
    while(t--)solve();
    return 0;
}/*
*/