正经题解

非常显然，这题用二维差分可以轻松解决，时间复杂度为 $O(n^2)$ 。

#include <iostream>
using namespace std;
int f[510][510];  //定义差分数组
int a[510][510];  //定义原数组
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int x,y,d,t;
        cin>>x>>y>>d>>t;
        t=t*2-1;  //狮子用-1表示，老虎用+1表示
        int lx=max(1,x-d/2);
        int rx=min(n,x+d/2);
        int uy=max(1,y-d/2);
        int dy=min(n,y+d/2);  //计算四角坐标
        f[lx][uy]+=t;
        f[lx][dy+1]-=t;
        f[rx+1][uy]-=t;
        f[rx+1][dy+1]+=t;  //修改差分数组
    }
    int ln=0,tg=0;  //统计领地数量
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            a[i][j]=f[i][j]+a[i-1][j]+a[i][j-1]-a[i-1][j-1];  //利用差分数组推出原数组
            if(a[i][j]<0)
                ln++;
            if(a[i][j]>0)  //判断是否为领地
                tg++;
        }
    }
    cout<<ln<<" "<<tg;
    return 0;
}