题解 P5026 【Lycanthropy】

· · 题解

NOIP后趁还没出成绩发一篇水题题解。

首先，我们发现当仅有一人落水时，这题的水位增长如果看成一条曲线的话，其增减是线性的。也就是说水位线的变化在图上画出来是一条折线。它长这样：

（如图表示一个v=5的人在0处落水后的新水位）

这不珂学！！！水怎么还多了！！！

既然它递增/递减是均匀的，那么我们可以考虑先用差分维护某一点的水位与上一点的差值，很显然维护的差值也是一个差分。差分还原成原值需要求前缀和，所以第一次差分之后跑两遍前缀和即可。

这里只列举一人落水的情况，但手玩数据可发现，随便多少人都一样。

绿题貌似有点高估了此题难度？

注意落水处左边的坐标值可以为负。开两倍数组再搞个指针即可。

code：

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n,m;
int aa[2100000],bb[2100000];
#define isdigit(x) ((x)>='0'&&(x)<='9')
inline int read(){
    int a=0,flag=1;
    char c=getchar();
    while(!isdigit(c)){
        if(c=='-')flag=-1;
        c=getchar();
    }
    while(isdigit(c)){
        a=(a<<1)+(a<<3)+c-48;
        c=getchar();
    }
    return a*flag;
}
int main(){
    n=read(),m=read();
    int *a=aa+1000000,*b=bb+1000000;
    for(int i=1;i<=n;++i){
        int v=read(),x=read();
        a[x-3*v+1]++;
        a[x-2*v+1]-=2;
        a[x+1]+=2;
        a[x+2*v+1]-=2;
        a[x+3*v+1]++;
    }
    for(int i=-40000;i<=m+40000;++i)a[i]+=a[i-1],b[i]+=b[i-1]+a[i];
    for(int i=1;i<=m;++i)printf("%d ",b[i]);
    return 0;
}