世间百态，尝遍万千。🚀️ 精华取之不尽，也用不尽。🎉️

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<map>
using namespace std;
long long r[1001000],c[1001000];
long long n,k;
long long ans,h,l;
int px(long long a,long long b){
    return a<b;
}
int main(){
    scanf("%lld%lld",&n,&k);
    for(int i=1;i<=k;i++){
        scanf("%lld%lld",&r[i],&c[i]);
    }
    sort(r+1,r+1+k,px);
    sort(c+1,c+1+k,px);
    for(int i=1;i<=k;i++){
        if(r[i]!=r[i+1]){
            h++;
        }
        if(c[i]!=c[i+1]){
            l++;
        }
    }
    printf("%lld\n",n*n-(n-h)*(n-l));
    return 0;
}

开完清表示一下对这篇文章的称赞❤️

世界上最好的题解😁 解析都在代码里了哟😝

#include<bits/stdc++.h>
using namespace std;
long long n,k,x[1000000]={0},y[1000000]={0},a=0,b=0;
//n是棋盘的边长，k是小汽车的数量，x和y是行数组与列数组，a是行不重复的列数，b是列不重复的个数
int main(){
    cin>>n>>k;//输入边长和小汽车的数量
    for(int i=1;i<=k;i++)cin>>x[i]>>y[i];//输入行数组和列数组
    //运用sort排序将所有的小汽车集合在左上角
    sort(x+1,x+k+1);
    sort(y+1,y+k+1);
    //去除重复的部分
    for(int i=1;i<=k;i++){
        if(x[i]!=x[i+1])a++;
        if(y[i]!=y[i+1])b++;
    }
    cout<<n*n-(n-a)*(n-b);//利用刚才算出的公式进行输出
    return 0;
}

各位大佬看完题解千万不要忘记给我点赞哟😊

思路

假设所有车一共覆盖了$r$行$c$列，不考虑重复的情况下，共有$(r+c)N$个格子被车攻击；而$r$行$c$列会产生$rc$个交点，所以合计有$(r+c)N-rc$个格子被攻击。

实现

整个程序的难点实际上在计算$r$和$c$上面。注意到$N$的范围极大，使用vis数组存出现过的行和列显然会MLE。于是，我们考虑去重，即用rows和cols数组保存每个车的行和列，最后用sort和unique进行去重。时间复杂度为 $O(n\log{n})$，瓶颈在排序上。

#include <iostream>
#include <algorithm>

using namespace std;

long long n, k, r, c;
int rows[1000001], cols[1000001];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);

	cin >> n >> k;
	for (int i = 1; i <= k; ++i) {
		int row, col;
		cin >> row >> col;
		rows[i] = row, cols[i] = col;
	}
	sort(rows + 1, rows + k + 1), sort(cols + 1, cols + k + 1);
	r = unique(rows + 1, rows + k + 1) - rows - 1;
	c = unique(cols + 1, cols + k + 1) - cols - 1;
	cout << (r + c) * n - r * c << endl;

	return 0;
}