题解 CF685D【Kay and Eternity】

· · 题解

CF685D Kay and Eternity解题报告：

更好的阅读体验

题意

网格中有n个格子被涂黑，对于 x\in[1,n] ，求大小为 k\times k 且能覆盖 x 个黑色格子的正方形数量。（ 1\leqslant n\leqslant 10^5,1\leqslant k\leqslant 300 ，值域范围 [-10^9,10^{9}] ）

分析

考虑答案的范围是很广的，显然不能枚举每个答案并检验其覆盖黑色格子数量。

正难则反，我们发现每个黑色格子 (x,y) 被覆盖当且仅当正方形的右下角在 ([x,x+k-1],[y,y+k-1]) 范围内，也就是在一个以 (x,y) 为左上角，边长为 k 的正方形内。

问题被转化成对于 x\in[1,n] ，求有多少个整点被 x 个矩形覆盖，这是经典问题，扫描线的同时暴力统计一下就好了，复杂度 O(nk) 。

代码

扫描线注意细节。

#include<stdio.h>
#include<algorithm>
#include<map>
using namespace std;
const int maxn=100005;
int n,k,tot;
int cnt[maxn<<1],num[maxn<<1],val[maxn<<1];
long long ans[maxn];
map<int,int>mp;
struct line{
    int x,ya,yb,opt;
}l[maxn<<1];
inline int cmp(line a,line b){
    return a.x<b.x;
}
int main(){
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++){
        int a,b;
        scanf("%d%d",&a,&b);
        l[2*i-1]=line{a,b,b+k-1,1},l[2*i]=line{a+k,b,b+k-1,-1};
        num[2*i-1]=b,num[2*i]=b+k;
    }
    sort(num+1,num+1+2*n),sort(l+1,l+1+2*n,cmp);
    for(int i=1;i<=2*n;i++)
        if(i==1||num[i]!=num[i-1])
            mp[num[i]]=++tot,val[tot]=num[i];
    for(int i=1;i<=2*n;i++){
        int ya=mp[l[i].ya],yb=mp[l[i].yb+1],opt=l[i].opt,len=l[2*n].x-l[i].x;
        for(int j=ya;j<yb;j++){
            ans[cnt[j]]-=1ll*len*(val[j+1]-val[j]);
            cnt[j]+=opt;
            ans[cnt[j]]+=1ll*len*(val[j+1]-val[j]);
        }
    }
    for(int i=1;i<=n;i++)
        printf("%lld%c",ans[i],i==n? '\n':' ');
    return 0;
}

整场比赛的题解