赣州市南康建设局网站公司seo是指什么意思

问题描述

老蛤有一堆真正的粉丝。
老蛤年迈了。不过好在他有特别多忠实粉丝，愿意献出自己寿命的1s等价交换为他的寿命+1s。
老蛤与粉丝们在一个面积为 的城市中。老蛤可以吸收距离不超过s的粉丝所提供的寿命。老蛤所在的十字路口(a,b)与粉丝所在的十字路口(c,d)之间距离是|a-c|+|b-d|。
老蛤的洪荒之力会不断变化q次，导致s的值也会变化多次。现在要求你，最聪明的粉丝，计算出对于这q个s，每次最多增加多少秒的寿命。

输入格式

第一行四个整数n,k,q代表城市面积为n*n，粉丝数目k，q次功力变化；
接下来k行，每行两个整数，为粉丝坐标 x_i，y_i；
接下来q行，每行一个整数，为当前最大距离s。

输出格式

对于每次询问，输出一行。每一行只包含一个整数，代表最多增加多少秒的寿命。

样例输入

样例输出

数据范围

题解

老蛤可以吸收的寿命就是老蛤可以吸收的范围内所有粉丝的数量。

枚举中心点，发现老蛤可以吸收的范围是一个菱形。

把直角坐标系旋转45°，菱形就变成了矩形。

维护二维前缀和，O(1)统计答案。

 

#include <cstdio>
const int maxn=1000;
int n,K,Q,p[10000005][2],sum[2005][2005],pt,s;
int min(int x,int y)
{
    return x<y?x:y;
}
int max(int x,int y)
{
    return x>y?x:y;
}
int main()
{
    int i,j,x,y,x1,x2,y1,y2;
    scanf("%d%d%d",&n,&K,&Q);
    for (i=1;i<=K;i++)
      scanf("%d%d",&x,&y),
      sum[x+y][x-y+n]++;
    for (i=1;i<=n;i++)
      for (j=1;j<=n;j++)
        p[++pt][0]=i+j,
        p[pt][1]=i-j+n;
    int n2=n*2;
    for (i=1;i<=n2;i++)
      for (j=1;j<=n2;j++)
        sum[i][j]+=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
    int ans=0;
    while (Q--)
    {
        scanf("%d",&s);
        if (s>n+1)
        {
            printf("%d\n",K);
            continue;
        }
        ans=0;
        for (i=1;i<=pt;i++)
          x1=max(p[i][0]-s-1,0),y1=max(p[i][1]-s-1,0),
          x2=min(p[i][0]+s,n2),y2=min(p[i][1]+s,n2),
          ans=max(ans,sum[x2][y2]-sum[x2][y1]-sum[x1][y2]+sum[x1][y1]);
        printf("%d\n",ans);
    }
    return 0;
}