参考Codeforces Round 983 (Div. 2) E. Balanced 讲解

寻找这个操作的本质，尝试用这个操作的组合，达到：“改变大小的数字最少（可以是相对大小的）”这个目的。

考虑这个操作中间的+2，两边的+1，我们容易想到隔一个数操作一下，看一下发生的变化。

如：a b c d e。在1 3 5位置操作后：a+3 b+2 c+2 d+2 e+3，发现就改变了a，e的相对大小。

由于数组是循环的，我们把操作位置循环右移一位，就能只改变a，b的相对大小。即这个操作本质上就是使相邻两个数加一。

如在2 4 1位置操作后：a+3 b+3 c+2 d+2 e+2。只改变了a，b的相对大小。

知道了所谓本质，来看看怎么使得数组全部相等。同样的，对于一个长度为5的数组：a,b,c,d,e

首先很容易想到能变成a,a,a,a,e。对于处理最后一个数，这一步，我们不把e变成a，而是把所有a变成e即可。

那么操作的时候，如b大于a的话，我们需要让b减一而不是加一。对于这个问题有一个trick：

对于操作数，我们先对每个位置都操作一个足够大的数。然后我们就可以“执行反操作”，即让相邻的两个数减一（只需要让+1需要操作的位置少操作一次即可）

所以为什么需要数组长度为奇数，因为如果为偶数的话，这个所谓的“本质”就不存在了。

用两个差分数组维护奇偶下标的修改值。奇数组的偶下标的数据无用，偶数组的奇下标的数据无用。

#include<bits/stdc++.h>
#define int ll


using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
#define MULTI_TEST
void solve(){
    int n;
    cin>>n;
    vector<int> a(n+1),ans(n+1,1000000000000000);
    vector<int> odd(n+2),even(n+2);
    auto update = [&](vector<int>& v,int l,int r,int x){
        v[l]+=x,v[r+1] -=x;
    };
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=2;i<n;i++){
        int x = a[i-1] - a[i];
        a[i] += x;
        a[i+1] += x;
        if(i%2==0){
            update(odd,i+1,n,x);
            update(even,1,i,x);
        }else{
            update(even,i+1,n,x);
            update(odd,1,i,x);
        }
    }

    for(int i=1;i<n;i+=2){
        int nxt = i==1?n:i-2;
        int x = a[nxt] - a[i];
        a[i] = a[i+1] = a[nxt];
        update(even,i+1,n,x);
        update(odd,1,i,x);
    }

    for(int i=1;i<=n;i++){
        odd[i] += odd[i-1];
        even[i] += even[i-1];
    }
    for(int i=1;i<=n;i++){
        if(i%2){
            ans[i] += odd[i];
        }else{
            ans[i] += even[i];
        }
        cout<<ans[i]<<" ";
    }
    cout<<endl;

}

signed main(){      
    ifstream test_file("0in.txt");
    if (test_file) {
        freopen("0in.txt", "r", stdin);
        freopen("0output.txt", "w", stdout);
    }
    std::ios::sync_with_stdio(0);std::cout.tie(0);std::cin.tie(0);
    int T = 1;
#ifdef MULTI_TEST
    cin>>T;
#endif
    while(T--){
        solve();
    }
    return 0;
}