谷歌网站推广排名工具,电商沙盘seo裤子关键词,爱站网的关键词是怎么来的,怎么在国税网站上做实名认证吗正题
题目链接:https://www.luogu.com.cn/problem/P5579 题目大意 nnn个树#xff0c;第iii个每天长高aia_iai米。 mmm次修剪#xff0c;第iii次在did_idi天#xff0c;将高度为bib_ibi的部分修剪掉
求每次修剪掉的高度 解题思路
按照aia_iai排序后我们知道每次修…正题
题目链接:https://www.luogu.com.cn/problem/P5579 题目大意
nnn个树第iii个每天长高aia_iai米。
mmm次修剪第iii次在did_idi天将高度为bib_ibi的部分修剪掉
求每次修剪掉的高度 解题思路
按照aia_iai排序后我们知道每次修改的一定是一个后缀所以我们先考虑如何计算修改的位置。首先我们可想到类似二分的方法为了方便维护我们使用一个线段树记录每个区间内最左边的树的情况然后左右走动即可。询问时我们需要知道这个修改区间内的高度和
考虑如何储存情况首先我们需要知道这个区间内所有树一天的成长和记为wiw_iwi然后上次修改的时间tit_iti和上次修改后的高度hih_ihi那么我们就可以用hi∗(r−l1)(T−ti)∗wih_i*(r-l1)(T-t_i)*w_ihi∗(r−l1)(T−ti)∗wi表示现在的高度和。同理最左边的树也可以这样来计算
时间复杂度O(nlogn)O(n\log n)O(nlogn) codecodecode
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N5e510,M4*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(lr){w[x]a[l];return;}ll mid(lr)1;Build(x*2,l,mid);Build(x*21,mid1,r);w[x]w[x*2]w[x*21];
}
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-l1)-w[x]*t[x];
}
void Change(ll x,ll l,ll r){if(lr){if(h[x](d[T]-t[x])*a[r]b[T]){answerh[x](d[T]-t[x])*a[r]-b[T];updata(x,l,r,T);}return;}ll mid(lr)1;if(lazy[x]){updata(x*2,l,mid,lazy[x]);updata(x*21,mid1,r,lazy[x]);lazy[x]0;}if(h[x*21](d[T]-t[x*21])*a[mid1]b[T]){ll zx*21;Change(x*2,l,mid);answerd[T]*w[x*21]ans[x*21]-(r-mid)*b[T];updata(x*21,mid1,r,T);}else Change(x*21,mid1,r);ans[x]ans[x*2]ans[x*21];h[x]h[x*2];t[x]t[x*2];return;
}
int main()
{scanf(%lld%lld,n,m);for(ll i1;in;i)scanf(%lld,a[i]);sort(a1,a1n);Build(1,1,n);for(T1;Tm;T){answer0;scanf(%lld%lld,d[T],b[T]);Change(1,1,n);printf(%lld\n,answer); }
}
