别样的积木大赛（？）| 题解：CF1884E Hard Design

· · 题解

先不考虑环，就做一个序列的情况。改变一下 a_i 的定义，定义为与初始最大值的差（因为最优策略显然是全部改到最大值）。

第一问是容易的，就是经典的积木大赛，结论是 \sum\limits_{i=1}^{n}\max(a_{i}-a_{i-1},0)，这里我们认为 a_0=0.

第二问我们考虑上面那个式子是怎么来的。如果你依稀记得积木大赛的做法的话，我们实际上是在维护目前覆盖到 i 的线段数量，如果 a_{i+1}>a_i 就加入 a_{i+1}-a_{i} 条新线段，否则断开 a_i-a_{i+1} 条旧线段。那么为了使平方和尽可能大，我们每次一定会继续延长最长的线段，断开最短的线段。这个过程可以用单调栈维护。

最后考虑一下环怎么做。第一问还是容易的，第二问我们需要观察到一个很重要的事情：因为所有数都要改到最大值，所以最大值所在位置的 a_i=0。这启发我们从这个位置断环成链，因为不存在经过这个位置的操作。接着预处理前缀和后缀的答案，那么一个位移的答案就能表示成一个前缀 + 一个后缀的答案了。时间复杂度 \mathcal O(n)。

注意取模。

#include<bits/stdc++.h>
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
#define pii pair<ll,ll>
#define rep(i,a,b) for(ll i=(a);i<=(b);++i)
#define per(i,a,b) for(ll i=(a);i>=(b);--i)
using namespace std;
bool Mbe;
ll read(){
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
void write(ll x){
    if(x<0)putchar('-'),x=-x;
    if(x>9)write(x/10);
    putchar(x%10+'0');
}
const ll N=1e6+9,Mod=1e9+7;
ll T,n,a[N],top,L[N],R[N];
pii stk[N];
void solve(){
    n=read();
    rep(i,1,n)a[i]=read();
    ll mx=*max_element(a+1,a+n+1);
    rep(i,1,n)a[i]=mx-a[i];
    top=0;
    ll P=0;
    rep(i,1,n){
        if(!a[i])P=i;
    }
    rep(i,0,n+1)L[i]=R[i]=0;
    ll lst=P,sum=0,cnt=0;
    rep(i,1,n){
        ll now=(lst==n?1:lst+1);
        if(a[now]>a[lst]){
            ll d=a[now]-a[lst];
            stk[++top]={d,i},cnt+=d;
        }
        else {
            ll d=a[lst]-a[now];
            while(d){
                if(stk[top].first<=d){
                    d-=stk[top].first,cnt-=stk[top].first,sum-=stk[top].first*(i-stk[top].second);
                    stk[top]={0,0},top--;
                }
                else cnt-=d,stk[top].first-=d,sum-=d*(i-stk[top].second),d=0;
            }
        }
        R[i]=(R[i-1]+2*sum+cnt)%Mod,sum+=cnt,lst=now;
    }
    lst=P,sum=0,cnt=0;
    rep(i,1,n){
        ll now=(lst==1?n:lst-1);
        if(a[now]>a[lst]){
            ll d=a[now]-a[lst];
            stk[++top]={d,i},cnt+=d;
        }
        else {
            ll d=a[lst]-a[now];
            while(d){
                if(stk[top].first<=d){
                    d-=stk[top].first,cnt-=stk[top].first,sum-=stk[top].first*(i-stk[top].second);
                    stk[top]={0,0},top--;
                }
                else cnt-=d,stk[top].first-=d,sum-=d*(i-stk[top].second),d=0;
            }
        }
        L[i]=(L[i-1]+2*sum+cnt)%Mod,sum+=cnt,lst=now;
    }
    ll C=0;
    rep(i,1,n){
        ll lst=(i==1?n:i-1);
        C+=max(0ll,a[i]-a[lst]);
    }
    rep(i,1,n){
        ll lst=(i==1?n:i-1);
        ll ncnt=C-max(0ll,a[i]-a[lst])+a[i];
        write(ncnt),putchar(' ');
        if(P>=i)write((L[P-i]+R[n-(P-i)-1])%Mod);
        else write((R[i-P-1]+L[n-(i-P-1)-1])%Mod);
        putchar('\n');
    }
}
bool Med;
int main(){
    cerr<<fabs(&Med-&Mbe)/1048576.0<<"MB\n";
    T=read();
    while(T--)solve();
    cerr<<"\n"<<clock()*1.0/CLOCKS_PER_SEC*1000<<"ms\n";
    return 0;
}