?

? ? ?可以很容易的發現，如果選了最高的房子，那么就不能再選了；否則在左邊選一坨合法的，在右邊選一坨合法的，拼起來還是合法的。

? ? ?所以我們可以處理出，每個數的控制區間[L,R] (保證這個區間是其他數都小于它的極大區間)，以及左邊右邊最大的比它小的數的位置(在區間里)。

? ? ?這樣我們就可以做到類似線段樹的分割并合并區間的答案。

?

? ? ?但還有一個問題，，，這樣建樹的話，最高深度可能是O(N)的，這樣不就gg了？？？

? ? ?但是數據是隨機的啊，，，期望log N. ?(好像這種根據權值分割樹的數據結構叫笛卡爾樹？)

?

#include<iostream> #include<cstdio> #define ll long long using namespace std; const int maxn=100005,ha=1e9+7; int L[maxn],R[maxn],S[maxn],tp,le; int n,m,H[maxn],V[maxn],Q,W[maxn],ri; inline int add(int x,int y){ x+=y; return x>=ha?x-ha:x;} inline int Merge(int o,int x,int y){ return add(add(x*(ll)y%ha,x),add(y,V[o]));} void build(int o,int l,int r){if(L[o]) build(L[o],l,o-1);if(R[o]) build(R[o],o+1,r);W[o]=Merge(o,W[L[o]],W[R[o]]); }int query(int o,int l,int r){if(!o) return 0;if(l>=le&&r<=ri) return W[o];else if(le>o) return query(R[o],o+1,r);else if(ri<o) return query(L[o],l,o-1);else return Merge(o,query(L[o],l,o-1),query(R[o],o+1,r)); }inline void prework(){for(int i=1;i<=n;i++){int t=tp;while(t&&H[S[t]]<H[i]) t--;if(t<tp) L[i]=S[t+1];if(t) R[S[t]]=i;S[tp=++t]=i;}build(S[1],1,n); }inline void solve(){while(Q--){scanf("%d%d",&le,&ri);printf("%d\n",query(S[1],1,n));} }int main(){freopen("monopoly.in","r",stdin);freopen("monopoly.out","w",stdout);scanf("%d%d",&n,&Q);for(int i=1;i<=n;i++) scanf("%d",H+i);for(int i=1;i<=n;i++) scanf("%d",V+i);prework();solve();return 0; }

　　

?

轉載于:https://www.cnblogs.com/JYYHH/p/8973049.html

總結

以上是生活随笔為你收集整理的某考试 T1 monopoly的全部內容，希望文章能夠幫你解決所遇到的問題。

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