原題

我們定義“區(qū)間的價(jià)值”為一段區(qū)間的最大值*最小值。
一個(gè)區(qū)間左端點(diǎn)在L，右端點(diǎn)在R，那么該區(qū)間的長(zhǎng)度為(R?L+1)。
求長(zhǎng)度分別為1～n的區(qū)間的最大價(jià)值。
保證數(shù)據(jù)隨機(jī)

---

因?yàn)楸ＷC數(shù)據(jù)隨機(jī)，所以我們可以考慮用區(qū)間的最大值把這個(gè)區(qū)間分為兩個(gè)部分，這樣答案的貢獻(xiàn)就有兩種情況。
1、在同一個(gè)區(qū)間里
2、跨過(guò)最大值，在兩個(gè)區(qū)間里

情況1通過(guò)遞歸就變成了情況2，而情況二我們通過(guò)two-points來(lái)完成。記錄l指針和r指針，因?yàn)樗鬄樽畲笾?#xff0c;所以選取l和r指針較大的內(nèi)個(gè)加入，并每次更新答案即可。
因?yàn)閿?shù)據(jù)隨機(jī)，所以O(shè)(nlogn)

#include<cstdio> #include<algorithm> #include<cstring> #define N 100010 typedef long long ll; using namespace std; ll n,ans[N],a[N];ll read() {ll ans=0,fu=1;char j=getchar();for (;(j<'0' || j>'9') && j!='-';j=getchar()) ;if (j=='-') j=getchar(),fu=-1;for (;j>='0' && j<='9';j=getchar()) ans*=10,ans+=j-'0';return ans*fu; }void solve(int l,int r) {if (l>r) return ;ll mx=0,pos,mn;for (int i=l;i<=r;i++)if (a[i]>mx) mx=a[i],pos=i;int ll=pos-1,rr=pos+1;mn=mx;ans[1]=max(ans[1],mx*mx);while (ll>=l && rr<=r){if (a[ll]<a[rr]) mn=min(a[rr],mn),rr++;else mn=min(a[ll],mn),ll--;ans[rr-ll-1]=max(ans[rr-ll-1],mx*mn);}while (ll>=l) mn=min(a[ll],mn),ll--,ans[rr-ll-1]=max(ans[rr-ll-1],mx*mn);while (rr<=r) mn=min(a[rr],mn),rr++,ans[rr-ll-1]=max(ans[rr-ll-1],mx*mn);solve(l,pos-1);solve(pos+1,r); }int main() {while (~scanf("%lld",&n)){memset(ans,0,sizeof(ans));for (int i=1;i<=n;i++)a[i]=read();solve(1,n);for (int i=1;i<=n;i++)printf("%lld\n",ans[i]);}return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/mrha/p/8031212.html

總結(jié)

以上是生活随笔為你收集整理的[hdu] 5696 区间的价值 || 序列分治的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。