有一个N*M的矩形，矩形中有K块涂黑了，给出涂黑的坐标，问完全白色的矩形有几个。

根据数据范围的不同，有多种做法。

Gym101350G 容斥

$1 ≤ N, M≤ 10^4$，$1 ≤K≤20$。

思路：

因为K比较小，N，M又比较大，所以可以考虑容斥。

对于一个N*M的矩形，它的子矩形有$C_{n+1}^2\times C_{m+1}^2=\frac{n(n+1)}{2}\times \frac{m(m+1)}{2}$个，就相当于在横的边里任意选两条，竖着的边里任意选两条，相当于选出了矩形的边界。

根据容斥原理，那就要算出包含涂黑的矩形有几个，奇加偶减，对于包含奇数个黑块的矩形，就减，对于包含偶数个黑块的矩形，就加。

如何算出包含黑块的矩形有几个？

只要知道minr,minc,maxr,maxc就可以了。

就相当于选矩形的四条边，最左边的那条边有minc种选法，最右边的那条边有m-maxc+1种选法，最上边的那条边有minr种选法，最下边的那条边有n-maxr+1种选法。个数为$minc*minr*(m-maxc+1)*(n-maxr+1)$。

所以二进制枚举容斥一下就可以了。

代码：

typedef long long ll;
#define INF 0x3f3f3f3f
struct point
{
    int r,c;
}p[25];
int main()
{
    int t,n,m,k;
    scanf("%d",&t);
    for(int kase=1;kase<=t;kase++)
    {
        scanf("%d%d%d",&n,&m,&k);
        for(int i=0;i<k;i++)
            scanf("%d%d",&p[i].r,&p[i].c);
        ll tot=1ll*n*(n+1)/2*m*(m+1)/2;
        //printf("%lld\n",tot);
        int minr,minc,maxr,maxc;
        for(int i=1;i<(1<<k);i++)
        {
            minr=INF;minc=INF;maxr=-INF;maxc=-INF;
            int cnt=__builtin_popcount(i);
            for(int j=0;j<k;j++)
            {
                if(i>>j&1)
                {
                    minr=min(minr,p[j].r);
                    minc=min(minc,p[j].c);
                    maxr=max(maxr,p[j].r);
                    maxc=max(maxc,p[j].c);
                }
            }
            //printf("%d %d %d %d\n",minr,minc,maxr,maxc);
            if(cnt%2==1)tot-=1ll*minr*minc*(n-maxr+1)*(m-maxc+1);
            else tot+=1ll*minr*minc*(n-maxr+1)*(m-maxc+1);
        }
        printf("Case #%d: %lld\n",kase,tot);
    }
    return 0;
}

南京网络赛B 单调栈

$1≤N≤10^5$，$1≤M≤100$，$0≤K≤10^5$。

思路：

K的范围明显不能容斥。

首先对于矩形中的每一块可以处理出它向上可以选几条边。

固定下面那条边，枚举每一块，处理出它左右可以扩展到哪里，即左右各可以选几条边（在上面选的边都可用的情况下）。

以向左扩展为例，如果左边的高度比它高或跟它相同的话，就肯定可以继续扩展过去，但是如果出现高度比它低的情况的时候，就不能扩展了。所以相当于找它的左边第一个比它低的块，这里就可以用单调栈了。如果当前元素小于等于栈顶元素的话，就把栈顶弹掉。类似于HDU1506。

向右扩展的话，要注意高度和它相同的不能再扩展了，因为扩展的话后面的往左边扩展会算进去这种情况，会造成重复。

所以对于每个块，完全空白的矩形为$h[i][j]*(j-l[j])*(r[j]-j)$。

代码：

typedef long long ll;
int g[100010][110];
int h[100010][110];
int l[110],r[110];
int main()
{
    int t,n,m,k,x,y;
    scanf("%d",&t);
    for(int kase=1;kase<=t;kase++)
    {
        scanf("%d%d%d",&n,&m,&k);
        memset(g,0,sizeof(g));
        while(k--)
        {
            scanf("%d%d",&x,&y);
            g[x][y]=1;
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                if(g[i][j]==1)h[i][j]=0;
                else h[i][j]=h[i-1][j]+1;
            }
        }
        ll ans=0;
        for(int i=1;i<=n;i++)
        {
            stack<int>s;
            for(int j=1;j<=m;j++)
            {
                l[j]=0;
                while(!s.empty()&&h[i][j]<=h[i][s.top()])
                    s.pop();
                if(!s.empty())l[j]=s.top();
                s.push(j);
            }
            while(!s.empty())s.pop();
            for(int j=m;j>=1;j--)
            {
                r[j]=m+1;
                while(!s.empty()&&h[i][j]<h[i][s.top()])
                    s.pop();
                if(!s.empty())r[j]=s.top();
                s.push(j);
            }
            /*for(int j=1;j<=m;j++)
                printf("i=%d j=%d:[%d %d]\n",i,j,j-l[j],r[j]-j);*/
            for(int j=1;j<=m;j++)
                ans+=1ll*h[i][j]*(j-l[j])*(r[j]-j);
        }
        printf("Case #%d: %lld\n",kase,ans);
    }
    return 0;
}