毁灭

对图染色。但是一个个地染会超时O(n^3)，显然我们要用O(n^2)的做法。
因为我们对每一行的染色是一段区间的操作，所以我们可以用差分来做。枚举弦心距（0~r，一定是0~r，为什么很显然），求出弦长，根据圆心的坐标，可以求出这一行的左右端点，就可以对这段区间进行差分了。时间复杂度：
O(n^2)。

#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
#define P(x) (x)*(x)
using namespace std;
int f[5009][5009],n,m,ans;
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int x,y,r;
        scanf("%d%d%d",&x,&y,&r);
        for(int j=0;j<=r;j++)
        {   
            int d=sqrt(r*r-j*j);
            int L=max(x-d,1);
            int R=min(x+d,n);
            int T=min(y+j,n);
            int B=max(y-j,1);
            f[T][L]+=1;f[T][R+1]-=1;
            f[B][L]+=1;f[B][R+1]-=1;
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            f[i][j]+=f[i][j-1];
            if(!f[i][j]) ans++;
        }
    }
    printf("%d",ans);
    return 0;
}