傳送門

文章目錄

• 題意：
• 思路：

題意：

題面有點問題，按照人類正常的理解來就好啦。

思路：

可以想到維護每個位置的一個斜率，模擬的話就是從第一個位置開始向后選，當某個位置斜率大于當前位置的時候，答案加一，并且將斜率更新為這個最大值。
有修改操作，復雜度顯然過不去，考慮用線段樹維護。
線段樹維護的話，修改很好寫，按照正常的來就好，主要在于如何$pushup$。
首先我們維護的信息需要當前區間的斜率最大值$mx$，當前區間要求的長度$len$。那么$pushup$的時候$mx$直接取兩個子樹的$max$即可，而$len$就沒那么簡單了。
考慮如何更新$len$，由于是從左往右看的，那么左邊的$len$所包含的位置是必選的，那么先讓$tr[u].len=tr[L].len$， 選完左邊之后，左邊的最大值一定被選到了，那么就用最大值來切右邊，即定義一個$calc(u,k)$的函數，返回的是當前區間$u$斜率大于$k$的條件下從左到右能看到的最多的房屋。那么在$calc$函數中如果到了葉子，就直接返回$mx>k$即可，否則分以下兩種情況：
$(1)$$tr[L].mx<=k$，那么此時左區間都被砍掉了，遞歸左區間，返回$calc(R,k)$即可。
$(2)$$tr[L].mx>k$，此時左區間沒有全部被砍掉，那么說明左區間是有一部分樓房能被看到，那么顯然我們需要遞歸左區間也需要遞歸右區間，即$calc(L,k)+calc(R,tr[L].mx)$，但是這樣復雜度會劇增，考慮如何優化呢？顯然我們左區間是一定要遞歸的，如何快速算出來右區間的長度呢？注意到此時左區間的最大值是一定被選到了，當前整個區間的長度就是由$tr[L].len+calc(R,tr[L].mx)$得到的，那么$calc(R,tr[L],mx)=tr[u].len?tr[L].len$，這樣$calc$函數復雜度是穩定的$logn$的了。
最終答案就是$tr[1].len$。

總體復雜度$n(logn{)}^2$

// Problem: P4198 樓房重建 // Contest: Luogu // URL: https://www.luogu.com.cn/problem/P4198 // Memory Limit: 125 MB // Time Limit: 1000 ms // // Powered by CP Editor (https://cpeditor.org)//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native") //#pragma GCC optimize(2) #include<cstdio> #include<iostream> #include<string> #include<cstring> #include<map> #include<cmath> #include<cctype> #include<vector> #include<set> #include<queue> #include<algorithm> #include<sstream> #include<ctime> #include<cstdlib> #define X first #define Y second #define L (u<<1) #define R (u<<1|1) #define pb push_back #define mk make_pair #define Mid (tr[u].l+tr[u].r>>1) #define Len(u) (tr[u].r-tr[u].l+1) #define random(a,b) ((a)+rand()%((b)-(a)+1)) #define db puts("---") using namespace std;//void rd_cre() { freopen("d://dp//data.txt","w",stdout); srand(time(NULL)); } //void rd_ac() { freopen("d://dp//data.txt","r",stdin); freopen("d://dp//AC.txt","w",stdout); } //void rd_wa() { freopen("d://dp//data.txt","r",stdin); freopen("d://dp//WA.txt","w",stdout); }typedef long long LL; typedef unsigned long long ULL; typedef pair<int,int> PII;const int N=1000010,mod=1e9+7,INF=0x3f3f3f3f; const double eps=1e-6;int n,m; struct Node {int l,r;int len;double mx; }tr[N<<2];void pushup(int u) {tr[u].mx=max(tr[L].mx,tr[R].mx); }void build(int u,int l,int r) {tr[u]={l,r};if(l==r) return;build(L,l,Mid); build(R,Mid+1,r); }int calc(int u,double k) {if(tr[u].mx<=k) return 0;if(tr[u].l==tr[u].r) return tr[u].mx>k;if(tr[L].mx<=k) return calc(R,k);else return tr[u].len-tr[L].len+calc(L,k); }void change(int u,int l,int r,double k) {if(tr[u].l>=l&&tr[u].r<=r) {tr[u].mx=k;tr[u].len=1;return;}if(l<=Mid) change(L,l,r,k);else change(R,l,r,k);pushup(u);tr[u].len=tr[L].len+calc(R,tr[L].mx); }int main() { // ios::sync_with_stdio(false); // cin.tie(0);scanf("%d%d",&n,&m);build(1,1,n);for(int i=1;i<=m;i++) {int x,y; scanf("%d%d",&x,&y);double k=1.0*y/x;change(1,x,x,k);printf("%d\n",tr[1].len);}return 0; } /**/

總結

以上是生活随笔為你收集整理的P4198 楼房重建 线段树 + 区间合并的全部內容，希望文章能夠幫你解決所遇到的問題。

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