题意
有一个n*m的矩形，里面有k个炸弹，给出每个炸弹的坐标，计算在n*m的矩形中有多少子矩形内是不包含炸弹的。
分析
场上很是懵逼，赛后问学长说是容斥定理？一脸懵逼。。容斥不是初中奥数用在集合上的东西吗（雾
先贴一下容斥的学习博客（貌似是我学长?):https://blog.csdn.net/usher_ou/article/details/68927439
还有这个题的参考博客：https://blog.csdn.net/lyg_air/article/details/77606691
侵删。
首先我们来看一个预备知识：
对于一个n*m的矩阵，它的子矩阵有多少个？我们可以看作一个组合的问题：在横着的n+1条边里选出两条来，从竖着的m+1条边里选出两条一共有多少选法？显然是C(2,n+1)*C(2,m+1)=n(n+1)/2*m(m+1)/2。
容斥定理就是通过加加减减来求一个并集。对于这个题我们可以通过考虑它的逆问题来用容斥定理，它的逆问题显然是:有多少子矩阵包含至少一个炸弹。那么就是先把只含有一个炸弹的加起来，再减去含有两个炸弹的，再加上含有三个炸弹的····
这是这个题的主要思路。那么还有两个小问题
1 怎么枚举炸弹的数量？因为K最多只要20那么可以通过二进制进行枚举
2 怎么计算包含某些数目炸弹的矩阵数？和上面计算n*m子矩阵的方法类似（一样），也是通过组合的方法。来看这张图
比如要计算包含这三个点的举行数目，我们可以通过计算这三个点最大最小的横纵坐标确定一个范围，然后从这个范围外选边就可以了，写出来就是：minx*miny*(n-maxx+1)*(m-maxy+1);
嗯，就是这样~A掉人生第一个容斥~
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm> using namespace std;
typedef long long LL;
typedef unsigned long long ull;
const int maxn=+;
const int INF=;
struct Node{
long long x,y;
}node[maxn];
long long T,n,m,k; int main(){
scanf("%d",&T);
for(int t=;t<=T;t++){
scanf("%lld%lld%lld",&n,&m,&k);
for(int i=;i<k;i++){
scanf("%d%d",&node[i].x,&node[i].y);
}
LL ans=n*(n+)/*m*(m+)/;
for(int i=;i<(<<k);i++){
LL minx=INF,miny=INF,maxx=-INF,maxy=-INF;
int cnt=;
for(int j=;j<k;j++){
if(<<j&i){
cnt++;
minx=min(minx,node[j].x);
miny=min(miny,node[j].y);
maxx=max(maxx,node[j].x);
maxy=max(maxy,node[j].y);
}
}
LL res=minx*miny*(n-maxx+)*(m-maxy+);
//cout<<res<<endl;
if(cnt%)
ans-=res;
else
ans+=res;
}
printf("%lld\n",ans);
}
return ;
}