差分
分为传递和作用两部分
本题而言,k的传递是线性的
k的作用是前一个点到这个点的斜率
code
#include<bits/stdc++.h>
using namespace std;
int height=0;//每个点的水高/水深
int k[1070000]={0};//会对x点前后v个区间产生影响
int start=30000;//最大3v
int main()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
{
int v,x;
cin>>v>>x;
x+=start;
k[x-3*v+1]++;//k[i]代表点i-1到点i直线的斜率
k[x-2*v+1]-=2;
k[x+1]+=2;
k[x+2*v+1]-=2;
k[x+3*v+1]++;
}
for(int i=1;i<=m+start;i++)
{
k[i]+=k[i-1];
height+=k[i]*1;
if(i>start)cout<<height<<" ";
}
return 0;
}
标签:斜率,int,Lycanthropy,++,start,P5026
From: https://www.cnblogs.com/pure4knowledge/p/18012049