正題

題目鏈接:https://www.luogu.com.cn/problem/P5579

---

題目大意

$n$個樹，第$i$個每天長高$a_i$米。

$m$次修剪，第$i$次在$d_i$天，將高度為$b_i$的部分修剪掉

求每次修剪掉的高度

---

解題思路

按照$a_i$排序后我們知道每次修改的一定是一個后綴，所以我們先考慮如何計算修改的位置。首先我們可想到類似二分的方法，為了方便維護，我們使用一個線段樹，記錄每個區間內最左邊的樹的情況，然后左右走動即可。詢問時我們需要知道這個修改區間內的高度和

考慮如何儲存情況，首先我們需要知道這個區間內所有樹一天的成長和記為$w_i$，然后上次修改的時間$t_i$和上次修改后的高度$h_i$，那么我們就可以用$h_i?(r?l+1)+(T?t_i)?w_i$表示現在的高度和。同理最左邊的樹也可以這樣來計算

時間復雜度$O(n\log n)$

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; const ll N=5e5+10,M=4*N; ll n,m,a[N],d[N],b[N],T,answer; ll w[M],t[M],h[M],lazy[M],ans[M]; void Build(ll x,ll l,ll r){if(l==r){w[x]=a[l];return;}ll mid=(l+r)>>1;Build(x*2,l,mid);Build(x*2+1,mid+1,r);w[x]=w[x*2]+w[x*2+1]; } void updata(ll x,ll l,ll r,ll T){t[x]=d[T];h[x]=b[T];lazy[x]=T;ans[x]=h[x]*(r-l+1)-w[x]*t[x]; } void Change(ll x,ll l,ll r){if(l==r){if(h[x]+(d[T]-t[x])*a[r]>b[T]){answer+=h[x]+(d[T]-t[x])*a[r]-b[T];updata(x,l,r,T);}return;}ll mid=(l+r)>>1;if(lazy[x]){updata(x*2,l,mid,lazy[x]);updata(x*2+1,mid+1,r,lazy[x]);lazy[x]=0;}if(h[x*2+1]+(d[T]-t[x*2+1])*a[mid+1]>b[T]){ll z=x*2+1;Change(x*2,l,mid);answer+=d[T]*w[x*2+1]+ans[x*2+1]-(r-mid)*b[T];updata(x*2+1,mid+1,r,T);}else Change(x*2+1,mid+1,r);ans[x]=ans[x*2]+ans[x*2+1];h[x]=h[x*2];t[x]=t[x*2];return; } int main() {scanf("%lld%lld",&n,&m);for(ll i=1;i<=n;i++)scanf("%lld",&a[i]);sort(a+1,a+1+n);Build(1,1,n);for(T=1;T<=m;T++){answer=0;scanf("%lld%lld",&d[T],&b[T]);Change(1,1,n);printf("%lld\n",answer); } }

總結

以上是生活随笔為你收集整理的P5579-[PA2015]Siano【线段树】的全部內容，希望文章能夠幫你解決所遇到的問題。

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