提交时间:2024-10-30 15:50:33
运行 ID: 33936
#include<bits/stdc++.h> using namespace std; #define int long long int a[100300],n; int lc[100300],rc[100300],siz[100300]; int S[100300],tp; vector<int>T[100300]; inline void dfs(int u,int fa){ if(u==0)return ; siz[u]=1; dfs(lc[u],u),siz[u]+=siz[lc[u]]; dfs(rc[u],u),siz[u]+=siz[rc[u]]; T[siz[u]].push_back(a[fa]-a[u]); } signed main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); // freopen("magic.in","r",stdin); // freopen("magic.out","w",stdout); // int C=clock(); int t; cin>>t; while(t--){ cin>>n; tp=0; int rt=0; int res=0; int St=0; for(int i=1;i<=n;i++){ cin>>a[i]; T[i].clear(); lc[i]=rc[i]=0; int lst=0; while(tp&&a[S[tp]]<a[i])lst=S[tp],tp--; if(lst)lc[i]=lst; if(tp)rc[S[tp]]=i; else rt=i; S[++tp]=i; } a[0]=a[n+1]=1e9; for(int i=1;i<=n;i++) res+=a[i]; for(int i=1;i<=n+1;i++) St+=abs(a[i]-a[i-1]); dfs(rt,0); // cout<<St<<endl; St-=2e9; for(int i=1;i<=n;i++) for(int x:T[i]){ int t=min((St+1)/2,x); res+=t*i;St-=2*t; // cout<<i<<" "<<x<<" "<<t<<endl; } cout<<res<<endl; } // cerr<<(clock()-C)*1000/CLOCKS_PER_SEC<<endl; cout.flush(); return 0; }