小 Z 最近撿到了一個棋盤，他想在棋盤上擺放 K 個皇后。他想知道在他擺完這 K 個皇后之后，棋盤上還有多少個格子是不會被攻擊到的。

注意：一個皇后會攻擊到這個皇后所在的那一行，那一列，以及兩條對角線。

第一行三個正整數 n,m,K，表示棋盤的行列，以及小 Z 擺放的皇后的個數。

接下來 K 行，每行兩個正整數 x,y，表示這個皇后被擺在了第 x行，第 y 列，數據保證任何兩個皇后都不會被擺在同一個格子里。

僅一個整數，表示棋盤上還有多少個格子是不會被攻擊到的。

• 對于 30% 的數據，1≤n,m≤5×10^3，1≤K≤500；
• 對于另外 10% 的數據  K=1；
• 對于 100% 的數據，1≤n,m≤2×10^4，1≤K≤500。

分析：

題目數據有那么億點點大，所以正經的暴力是不行了，我們每放置一個皇后，用四個數組x[N],y[N],dig[N],udig[N]，來儲存該皇后

所在的行，列，對角線以及反對角線的狀態，我們在圖上畫一個坐標系，給出任意幾個點放置皇后，如下圖：

 我們可以清楚的看到，點1的橫縱坐標為(2,4)，當點1放置一個皇后之后，第4行就被全被攻擊了，第2列全被攻擊，并且x+y=6上的點全被攻擊了，以及x-y=-2上的點全被攻擊了，所以在點(x,y)出放置一個皇后之后，我們更新所有的數組狀態:

x[i]=1,y[j]=1,dig[x+y]=1,udig[x-y+C]=1

這里的udig[x-y+C]中，下標x-y加上常數C的原因是放置數組下標溢出，這就是我們的核心函數了。

在寫核心函數之前，我們先寫一個初始化函數，將所有的輸入處理了

void init(){
    for(int i=1;i<=k;i++)
	{
        int a,b;
		scanf("%d%d",&a,&b);
		x[a]=1;
		y[b]=1;
		dig[a+b]=1;
		udig[a-b+C]=1;
	}
}

接著寫核心函數fac()

int fac(){
    int res=0;
    for(int i=1;i<=n;i++){
        if(x[i])continue;
        for(int j=1;j<=m;j++){
            if(y[j]||dig[i+j]||udig[i-j+C])continue;
            else res++;
        }
    }
    return res;
}

最后這幾個函數和程序基本框架結合起來

完整代碼如下：

 （PS:需要開啟氧氣優化O2優化）