题目链接
题意：求n*m的区域中不含有黑色格子的矩形数量。
这题给了2s的时限，m只给了100，暴力复杂度可以是O(n*m*m)，接近1e9，能过，大概1300+ms。。。因为高中的时候懒得学组合数学，导致现在对计数的东西一窍不通，连没有黑色格子的情况居然都想不清楚QAQ
这是一篇讲解本题的博客
看了上面链接的博客后，有种恍然大明白的感觉，现在开始讲讲我理解的做法。
首先，假设没有黑色格子，暴力计数的话可以先枚举右下角的坐标(i,j)，然后枚举左下角的列号k，对于每一个不同（i,j,k），新增的矩形个数就是行号i（即左上角可能的取值个数）——左下角和右下角确定的情况下理解这个计数应该还是挺简单的。枚举完后，得到的值就是总的矩形数。
如果有黑色格子，会对计数产生什么影响呢？我们需要在枚举左下角的时候，同时更新从右下角到左下角的列里最接近当前行黑色格子的行号，因为这个黑色格子限制了左上角可能的取值个数。至于怎么更新，可以枚举行时先维护出每一列最接近当前行的黑色格子的行号。
（PS：除了暴力外还研究了一下同校聚聚的分治代码，发现在极限数据下也会退化成O(n*m*m)，不过思路还是巧妙哇
代码如下：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int up[110];
struct node{int x,y;friend bool operator<(node a,node b){return a.x<b.x;}
}b[100005];
int main(){int T, cas=0;scanf("%d", &T);while(T--){int n, m, K;scanf("%d%d%d", &n, &m, &K);memset(up,0,sizeof(up));for(int i=0; i<K; i++){scanf("%d%d", &b[i].x, &b[i].y);}ll ans=0;int tt=0;for(int i=1; i<=n; i++){while(tt<K&&b[tt].x<=i){//维护每一列中最接近当前行的黑色格子的行号 up[b[tt].y]=max(up[b[tt].y],b[tt].x),tt++;}for(int j=1; j<=m; j++){int minn=i;for(int k=j; k>0; k--){if(i-up[k]<minn)minn=(i-up[k]);ans+=minn;}}}printf("Case #%d: %lld\n", ++cas, ans);}return 0;
}