这是一道差分套差分的题,我们先求出某点水位和其上一点水位的差值,很显然这个差值序列也符合差分。
那么我们只需要一次差分再跑两遍前缀和即可。(如何差分要自己手动算出规律)。
其次,由于要求的是每个人落水点的水位,而我们在跑前缀和的时候,下标可能为负,所以我们把水位宽度平移M个单位,确保所有下标为正数。
主要代码:
#include<bits/stdc++.h> using namespace std; const int N=1e6+5,M=3e4+3; int a[N+2*M],v[N],x[N]; int n,m; void setbuild(){ for (int i=1;i<=n;i++){ a[x[i]-3*v[i]+1+M]+=1; a[x[i]-2*v[i]+1+M]-=2; a[x[i]+1+M]+=2; a[x[i]+2*v[i]+1+M]-=2; a[x[i]+3*v[i]+1+M]+=1; } } void build(){ for (int i=1;i<=m+M;i++) a[i]+=a[i-1]; for (int i=1;i<=m+M;i++) a[i]+=a[i-1]; } int main(){ cin>>n>>m; for (int i=1;i<=n;i++) cin>>v[i]>>x[i]; setbuild(); build(); for (int i=1;i<=m;i++){ if (i!=1) cout<<" "<<a[i+M]; else cout<<a[i+M]; } return 0; }
标签:int,Lycanthropy,差分,水位,setbuild,P5026 From: https://www.cnblogs.com/purple123/p/18003509