題意：http://www.lydsy.com/JudgeOnline/problem.php?id=2957

sol ?：首先考慮轉化問題，即給你一個斜率序列，讓你動態維護單調棧

　　　考慮線段樹，令get(x,r)表示以r為初值在節點x時會增加多少個數

　　　遞歸處理，get(x,r)=get(lson[x],r)+get(rson[x],max(mx[lson[x]],r))

　　　然而這樣復雜度是爆炸的.....考慮預處理get(rson[x],mx[lson[x]])

　　　這樣的話每次查詢答案分為以下情況

　　　　　mx[lson[x]]>=r，這樣的話右邊已經預處理好了，遞歸左邊即可

　　　　　mx[lson[x]]<r，這樣的話左邊的貢獻為0，遞歸右邊即可

　　　那么我們只需維護get(rson[x],mx[lson[x]])即可

　　　對于每次將位置pos修改為val，僅會對其右側產生影響，分為以下情況

　　　　　若val<=mx[lson[x]],則對get(rson[x],mx[lson[x]])無影響

　　　　　若val>mx[lson[x]]，那么遞歸進右邊處理

　　　最終復雜度O(n*log^2)

#include<iostream> #include<algorithm> #include<cstdio> #include<cstring> using namespace std; const int Mx=400010; int n,m,l[Mx],r[Mx],lson[Mx],rson[Mx],ans[Mx]; double maxn[Mx];void build(int x,int L,int R) {l[x]=L,r[x]=R;lson[x]=x*2,rson[x]=x*2+1;if(L==R) return ;int mid=(L+R)/2;build(lson[x],L,mid);build(rson[x],mid+1,R); }int cal(int x,double val) {int L=l[x],R=r[x];if(L==R) return maxn[x]>val;if(maxn[lson[x]]<=val) return cal(rson[x],val);return ans[x]-ans[lson[x]]+cal(lson[x],val); }void change(int x,int pos,double c) {int L=l[x],R=r[x],mid=(L+R)/2;if(L==R) { ans[x]=1,maxn[x]=c; return ; }if(pos<=mid) change(lson[x],pos,c);else change(rson[x],pos,c);maxn[x]=max(maxn[lson[x]],maxn[rson[x]]);ans[x]=ans[lson[x]]+cal(rson[x],maxn[lson[x]]); }int main() {scanf("%d%d",&n,&m);build(1,1,n);for(int i=1,x,y;i<=m;i++){scanf("%d%d",&x,&y);change(1,x,(double) y/x);printf("%d\n",ans[1]);}return 0; }

?

轉載于:https://www.cnblogs.com/xiaoxubi/p/6632671.html

總結

以上是生活随笔為你收集整理的bzoj2957：楼房重建的全部內容，希望文章能夠幫你解決所遇到的問題。

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