题目概述

有 $n$ 个矩阵，问多少三元组 $(i,j,k),i<j<k$ 满足三个矩阵至少有一个相交的格子。

解题报告

我怎么连计数题都不会……这种题目肯定要考虑枚举相交的格子来统计贡献，但是不可能枚举相交的矩阵，我们再观察一下就会发现只需要枚举相交矩阵的一个角就行了。

然后开始疯狂分类讨论，只要按照一定顺序枚举所有方案并判断该方案是否可行就行了，我们先记录：

$S_{1,i,j}$ ：左下角为 $(i,j)$ 的矩阵个数。$S_{2,i,j}$ ：左边界包含 $(i,j)$ 的矩阵个数（不含左下角）。

$S_{3,i,j}$ ：下边界包含 $(i,j)$ 的矩阵个数（不含左下角）。$S_{4,i,j}$ ：包含 $(i,j)$ 的矩阵个数（不含左边界下边界）。

这些用容斥和差分就可以 $O(1000^2)$ 求出来了，接下来列举所有情况（前面的数字表示选了几个），自己推去吧，我根本没想让你们看懂：

[3S_1];[2S_1,S_2];[2S_1,S_3];[2S_1,S_4];[2S_2,S_1];[2S_2,S_3];[2S_3,S_1];[2S_3,S_2];[2S_4,S_1];[S_1,S_2,S_4];[S_1,S_2,S_4];[S_1,S_3,S_4];[S_2,S_3,S_4]

示例程序

#include<cstdio>
#include<cctype>
#include<cstring>
using namespace std;
typedef long long LL;
const int maxn=100000,maxm=1000;

int te,n,s[4][maxm+5][maxm+5];LL ans;

#define Eoln(x) ((x)==10||(x)==13||(x)==EOF)
inline char readc(){
    static char buf[100000],*l=buf,*r=buf;
    if (l==r) r=(l=buf)+fread(buf,1,100000,stdin);
    if (l==r) return EOF;return *l++;
}
inline int readi(int &x){
    int tot=0;char ch=readc(),lst='+';
    while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
    while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
    return (lst=='-'?x=-tot:x=tot),Eoln(ch);
}
#define C2(x) ((LL)(x)*((x)-1)/2)
#define C3(x) ((LL)(x)*((x)-1)*((x)-2)/6)
int main(){
    freopen("program.in","r",stdin);
    freopen("program.out","w",stdout);
    for (readi(te);te;te--,memset(s,0,sizeof(s)),ans=0){
        for (int i=(readi(n),1);i<=n;i++){
            int xl,yl,xr,yr;readi(xl);readi(yl);readi(xr);readi(yr);
            s[0][xr][yl]++;s[3][xl][yl+1]++;s[3][xl][yr+1]--;s[3][xr][yl+1]--;s[3][xr][yr+1]++;
            s[1][xl][yl]++;s[1][xr][yl]--;s[2][xr][yl+1]++;s[2][xr][yr+1]--;
        }
        for (int j=1;j<=1000;j++) for (int i=1;i<=1000;i++) s[1][i][j]+=s[1][i-1][j];
        for (int i=1;i<=1000;i++) for (int j=1;j<=1000;j++) s[2][i][j]+=s[2][i][j-1];
        for (int i=1;i<=1000;i++) for (int j=1;j<=1000;j++) s[3][i][j]+=s[3][i-1][j]+s[3][i][j-1]-s[3][i-1][j-1];
        for (int i=1;i<=1000;i++)
            for (int j=1;j<=1000;j++){
                ans+=C3(s[0][i][j]);
                ans+=C2(s[0][i][j])*(s[1][i][j]+s[2][i][j]+s[3][i][j]);
                ans+=C2(s[1][i][j])*(s[0][i][j]+s[2][i][j]);
                ans+=C2(s[2][i][j])*(s[0][i][j]+s[1][i][j]);
                ans+=C2(s[3][i][j])*s[0][i][j];
                ans+=(LL)s[0][i][j]*s[1][i][j]*(s[2][i][j]+s[3][i][j]);
                ans+=(LL)s[2][i][j]*s[3][i][j]*(s[0][i][j]+s[1][i][j]);
            }
        printf("%lld\n",ans);
    }
    return 0;
}