https://blog.csdn.net/bbbbswbq/article/details/82354425
#include<bits/stdc++.h>
using namespace std;
struct node
{
int p,x;
bool operator <(const node&a)const
{
return x<a.x;
}
};
int col[500];
int tu[20010][250];
int main()
{
int n,m,k,p1,p2;
int T;
cin>>T;
int cases =0 ;
while(T--)
{
cases++;
cin>>n>>m>>k;
memset(tu,0,sizeof tu);
for(int i=1;i<=k;i++)
{
cin>>p1>>p2;
tu[p1][p2] = 1;
}
memset(col,0,sizeof col);
long long ans = 0;
int sum[400]={0};
for(int i =1; i<=n; i++)
{
stack<node>o;
o.push(node{0,n+1});
sum[0] = 0;
for(int j=1;j<=m;j++)
{
if(tu[i][j]==1)col[j] = i;
while(!o.empty()&&o.top().x<=col[j])
{
o.pop();
}
sum[j]+=sum[o.top().p]+(i-col[j])*(j-o.top().p+1) ;
ans += sum[j];
o.push(node{j,col[j]});
}
}
cout<<"Case #"<<cases<<" "<<ans<<endl;
}
return 0;
}