CodeJam 2019 Round 3 Rancake Pyramid

• problem
• solution
• code

problem

神奈子是個很愛打麻將的老婆婆，有一天她把她的麻將放成了 $n$ 堆，第 $i$ 堆的高度為 $a_i$ 。

因為她很喜歡風，所以她用風吹倒了最左邊的 $L$ 堆麻將和最右邊的 $R$ 堆麻將，但是她也不想吹倒太多，所以剩下的麻將至少有 $3$ 堆。

因為她很喜歡山，所以她希望剩下的麻將能形成山峰一樣的形狀。

設剩下的麻將形成的序列為 $b_1,\dots ,b_k$，她希望存在至少一個 $i\in [1,k]$ 滿足 $b_1\le b_2\le ...\le b_i\ge b_{i+1}\ge ...\ge b_k$。

然而她發現很多時候麻將并不是山峰的樣子，所以她會為若干堆麻將增高一些高度，她不想花太多時
間，所以她會選擇每一堆麻將增高的高度之和最小的方法。

她非常無聊，所以想嘗試所有情況，即對于每對滿足 $0\le L,R\le n,L+R\le n?3$ 的 $(L,R)$ 都進行一次上述過程。

每次完成一次操作后她都會把麻將還原成初始狀態，現在她想知道在全部情況下增加的麻將高度之和是多少，答案可能過大，對 $1e9+7$ 取模。

$3\le n\le 10^6,1\le a_i\le 10^9$。

solution

有個很重要的結論：對應一段區間操作，一定是選擇最高的為山峰，如果有多個相同的隨便選一個就行。

證明：這是很顯然的。不是很嚴謹的理解一下。

因為如果最高的不是山峰，那么被選成山峰的點自己都需要被拔高到至少是最高點的高度。

然后被選做山峰的點和最高的點之間的所有點都要被拔高到至少最高點的高度。

顯然不如選最高做山峰，然后同樣的一段就不需要被拔高到至少最高點的高度。

暴力的 $O(n^2)$ 我在考場上寫出來，結果內存算錯了，define int long long MLE 掛了qwq

就是枚舉 $L,R$ ，然后得到剩下的還立著的麻將區間 $[l,r]$ ，考慮怎么 $O(1)$ 計算。

首先要能快速知道區間內的最高點位置 $p$ ，st表 預處理即可。

$l,r$ 從最高點分開的左右區間是相同的對稱問題，且被最高點分開，相互獨立，接下來操作以 $l$ 為例。

$l$ 端點作為開始肯定是可以不用改變的，然后判斷 $l+1$ 與 $l$ 的麻將高度，如果 $a_{l+1}\ge a_l$ 那就不用拔高，否則貪心地只需要拔高到 $a_l$ 的高度就行了。這樣不僅拔高高度最小化，并且增加了后面不拔高的可能性。

肯定的，不可能每次都掃一遍區間，那是 $O(n^3)$ 的了。

發現可以通過維護前綴信息來 $O(1)$ 計算每個區間對應的答案。

• preh[i] ：表示從 $1$ 開始，$i$ 最后的高度。

  具體而言：

  • 如果不拔高，即 $preh[i?1]\le a[i]$，則 $preh[i]=a[i]$
  • 如果拔高，即 $preh[i?1]>a[i]$，則 $preh[i]=preh[i?1]$

• pres[i] ：表示從 $1$ 開始維護到 $i$ 為止一共拔高的高度。

  具體而言：

  • 如果不拔高，則 $pres[i]=pres[i?1]$
  • 如果拔高，則 $pres[i]=pres[i?1]+preh[i]?a[i]$

每次區間 $[l,r]$ 是從 $l$ 開始的，所以要減去前 $l?1$ 個的拔高影響，$pres[i]?pres[l?1]$。

但是注意到，這段區間可能 $l$ 是被拔高了的，所以要再判斷一下然后減去。

具體而言：

• 如果 $a[l]=preh[l]$，證明從 $1$ 開始 $l$ 是沒有被拔高的。

  那么 $pres[i]?pres[l?1]$ 就是 $[l,r]$ 從 $l$ 開始拔高的貢獻。

• 如果 $a[i]<preh[l]$，證明從 $1$ 開始 $l$ 是被拔高過的。

  但是 $[l,r]$ 從 $l$ 開始就不需要拔高，所以 $preh[l]?a[l]$ 是后面一段多被拔高的高度的。

  要減去，但也不是單獨的乘以區間長度，因為有些點不一定被拔高了。

  所以還要維護一個 prec[i]：表示從 $1$ 開始維護到 $i$ 為止被拔高過的麻將個數。

  減去的應該為：$(preh[l]?a[l])(prec[p]?prec[l?1])$

后綴同理維護，sufh[i] sufs[i] sufc[i]。

因為傘兵博主寫代碼時直接原地覆蓋，導致n^2暴力的代碼徹底沒了。所以就不能提供給大家了┏┛墓┗┓…(((m -__-)m

---

暴力是抓住左右端點不放。然而一般具有性質的特殊位置，比如最大點位置，一堆區間然后有一個特殊位置等等，正解都是考慮枚舉這個特殊位置的。

所以這里考慮枚舉每一個麻將做一個區間的最大值的答案。

假設一個麻將 $i$ 是一段區間 $[l,r]$ 的最大值，即 $a[l?1],a[r+1]$ 都比 $i$ 麻將高度高。

那么對于 $?l\le x\le i\le y\le r,[x,y]$ 都是以 $i$ 為不變的最高麻將計算。

這樣子就是笛卡爾樹大根堆的區間限制，考慮左右兒子的貢獻，然后再考慮節點本身的貢獻。

這里也有正如前面遇到的問題，不同位置開始如果預處理要考慮被多拔高了的高度。

所以不妨一開始就將每個麻將的高度直接剪掉，麻將能在多少種區間內就被減去多少次。

后面直接加上最終高度，這中間的差就是被拔高高度，而且是一一對應的。

具體而言：

建立大根堆笛卡爾樹，計算每個點作為最大值的貢獻。

記錄笛卡爾樹上點 $i$ 的信息 $suml,sumr$ 表示 $i$ 向左 / 右區間內每個點的答案之和，通過兒子快速計算。

跨越 $i$ 的答案為 $suml?(r?i+1)+sumr?(i?l+1)$。

以及 $i$ 點本身的答案，$(i?l+1)?(r?i+1)?a[i]$。

詳情可見代碼實現。

code

#include <bits/stdc++.h> using namespace std; #define maxn 1000005 #define int long long #define mod 1000000007 int n, ans; pair < int, int > MS[maxn]; bool vis[maxn]; int a[maxn], s[maxn], L[maxn], R[maxn];void solve( int p ) {vis[p] = 1;int l = p, r = p, suml = 0, sumr = 0;if( vis[p - 1] ) l = L[p - 1], suml = s[p - 1];if( vis[p + 1] ) r = R[p + 1], sumr = s[p + 1];ans = ( ans + ( p - l + 1 ) * sumr ) % mod;ans = ( ans + ( r - p + 1 ) * suml ) % mod;int w = a[p] * ( p - l + 1 ) % mod * ( r - p + 1 ) % mod;ans = ( ans + w ) % mod;L[r] = l, R[l] = r, s[l] = s[r] = ( suml + sumr + w ) % mod; }signed main() {scanf( "%lld", &n );for( int i = 1;i <= n;i ++ ) {scanf( "%lld", &a[i] );ans = ( ans - i * ( n - i + 1 ) % mod * a[i] ) % mod;MS[i] = { a[i], i };}sort( MS + 1, MS+ n + 1 );for( int i = 1;i <= n;i ++ ) solve( MS[i].second );printf( "%lld\n", ( ans + mod ) % mod );return 0; }

總結

以上是生活随笔為你收集整理的[CodeJam 2019 Round 3] Rancake Pyramid（笛卡尔树）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。