正題

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

---

題目大意

$n$個點在坐標軸上，$q$次每次所有點向一個方向移動若干步，每個點的權值是它第一次覆蓋的區間長度（也就是一個區間只能貢獻到第一次經過它的點）。

求所有點的最終權值。

$1\le n,q\le 2\times 10^5$

---

解題思路

因為兩個點的區間只會被這兩個點覆蓋，所以考慮求出每個區間被兩邊各占了多少。

先去掉無用的條件，求出一個數組$f$滿足正負交替表示一左一右，正負的絕對值各自遞增。

然后在$f$數組上二分出兩個點覆蓋的區間第一次相交的時候就可以計算各自被覆蓋多少了。

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

---

code

#include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; const ll N=2e5+10; ll n,m,Q,lmax,rmax,x[N],g[N],f[N],w[N]; signed main() {scanf("%lld%lld",&n,&Q);for(ll i=1;i<=n;i++)scanf("%lld",&x[i]);for(ll i=1;i<=Q;i++){scanf("%lld",&g[i]);g[i]+=g[i-1];if(g[i]>rmax){if(f[m]<=0)rmax=f[++m]=g[i];else rmax=f[m]=g[i];}if(g[i]<lmax){if(f[m]>=0)lmax=f[++m]=g[i];else lmax=f[m]=g[i];}}w[1]-=lmax;w[n]+=rmax;for(ll i=1;i<n;i++){ll len=x[i+1]-x[i];ll l=0,r=m-2;while(l<=r){ll mid=(l+r)>>1;if(abs(f[mid])+abs(f[mid+1])>=len)r=mid-1;else l=mid+1;}if(abs(f[l])+abs(f[l+1])>=len){if(f[l+1]>0)w[i+1]-=f[l],w[i]+=len+f[l];else w[i]+=f[l],w[i+1]+=len-f[l];}else{if(f[l+1]>0)w[i+1]-=f[l],w[i]+=f[l+1];else w[i]+=f[l],w[i+1]-=f[l+1];}}for(ll i=1;i<=n;i++)printf("%lld\n",w[i]);return 0; }

總結

以上是生活随笔為你收集整理的P7405-[JOI 2021 Final]雪玉【二分】的全部內容，希望文章能夠幫你解決所遇到的問題。

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