音乐网站开发结语,建筑设计方案网站,专业手机网站设计,如何做静态网站正题
题目链接:https://www.luogu.com.cn/problem/P7405 题目大意 nnn个点在坐标轴上#xff0c;qqq次每次所有点向一个方向移动若干步#xff0c;每个点的权值是它第一次覆盖的区间长度#xff08;也就是一个区间只能贡献到第一次经过它的点#xff09;。
求所有点的最终…正题
题目链接:https://www.luogu.com.cn/problem/P7405 题目大意
nnn个点在坐标轴上qqq次每次所有点向一个方向移动若干步每个点的权值是它第一次覆盖的区间长度也就是一个区间只能贡献到第一次经过它的点。
求所有点的最终权值。
1≤n,q≤2×1051\leq n,q\leq 2\times 10^51≤n,q≤2×105 解题思路
因为两个点的区间只会被这两个点覆盖所以考虑求出每个区间被两边各占了多少。
先去掉无用的条件求出一个数组fff满足正负交替表示一左一右正负的绝对值各自递增。
然后在fff数组上二分出两个点覆盖的区间第一次相交的时候就可以计算各自被覆盖多少了。
时间复杂度O(nlogn)O(n\log n)O(nlogn) code
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N2e510;
ll n,m,Q,lmax,rmax,x[N],g[N],f[N],w[N];
signed main()
{scanf(%lld%lld,n,Q);for(ll i1;in;i)scanf(%lld,x[i]);for(ll i1;iQ;i){scanf(%lld,g[i]);g[i]g[i-1];if(g[i]rmax){if(f[m]0)rmaxf[m]g[i];else rmaxf[m]g[i];}if(g[i]lmax){if(f[m]0)lmaxf[m]g[i];else lmaxf[m]g[i];}}w[1]-lmax;w[n]rmax;for(ll i1;in;i){ll lenx[i1]-x[i];ll l0,rm-2;while(lr){ll mid(lr)1;if(abs(f[mid])abs(f[mid1])len)rmid-1;else lmid1;}if(abs(f[l])abs(f[l1])len){if(f[l1]0)w[i1]-f[l],w[i]lenf[l];else w[i]f[l],w[i1]len-f[l];}else{if(f[l1]0)w[i1]-f[l],w[i]f[l1];else w[i]f[l],w[i1]-f[l1];}}for(ll i1;in;i)printf(%lld\n,w[i]);return 0;
}
