例题

1147. Shaping Regions @ Timus Online Judge

大意：一坨有颜色的矩阵依次覆盖，最后每个颜色有多少种面积。

坑点：矩阵不一定在白布上。

做法

讲讲做法，对于一个矩阵 $X$ 覆盖在另外一个矩阵 $Y$ 上，我们可以尝试把 $Y$ 没有被覆盖的部分分成好几份。

但是要怎么切割，怎样切割会比较优秀呢？（切的尽量的少）

我们记 $X$ 左下角 $x,y$ 坐标为 $X(x_1)$ 和 $X(y_1)$ ，右上角是 $X(x_2)$ 和 $X(y_2)$ ，$((a,b),(c,d))$为以 $(a,b)$ 为左下角，$(c,d)$ 为右上角的矩阵。

我们不妨考虑 $X$ （红色）和 $Y$ （蓝色）在 $x$ 轴投影的位置关系：

matrixcut-1
如果 $X$ 的左边的 $x$ 坐标在 $Y$ 的 $x$ 轴投影内，即：$Y(x_1)<X(x_1)<Y(x_2)$，那么 $Y$ 在 $[Y(x_1),X(x_1)]$ 上的矩阵都没有被覆盖，即：$((Y(x_1),Y(y_{1}),(X(x_1),Y(y_{1}))$ 没有被覆盖，右边同理。

但是还有中间的情况，$X,Y$ 在 $x$ 轴投影重叠部分的上方（红色框住的位置）：这个区间既包括 $Y$ 矩阵，也包括 $X$ 矩阵未被覆盖的部分（可能没有），这个时候分 $y$ 轴讨论就行了。

不难发现，这样在任何情况下都是最优的割法。

给上一份代码，网上抄的，当时学的拿来用了，现在不知道是谁的了QAQ，如果知道是谁的通知一声，我马上标注，放上这份代码的原因是和上面讲的比较符合，比较好理解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <climits>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#include <list>
#define rep(i,m,n) for(i=m;i<=n;i++)
#define rsp(it,s) for(set<int>::iterator it=s.begin();it!=s.end();it++)
#define mod 1000000007
#define inf 0x3f3f3f3f
#define vi vector<int>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ll long long
#define pi acos(-1.0)
#define pii pair<int,int>
#define Lson L, mid, rt<<1
#define Rson mid+1, R, rt<<1|1
const int maxn=3e3+10;
using namespace std;
ll gcd(ll p,ll q){return q==0?p:gcd(q,p%q);}
ll qpow(ll p,ll q){ll f=1;while(q){if(q&1)f=f*p;p=p*p;q>>=1;}return f;}
int n,m,k,t,ans[maxn];
struct node
{
    int x1,x2,y1,y2,c;
    node(){}
    node(int _x1,int _x2,int _y1,int _y2,int _c)
    {
        x1=_x1,x2=_x2,y1=_y1,y2=_y2,c=_c;
    }
}op[maxn];
int get(node p,int nt)
{
    int ans=0;
    while(nt<=k&&((p.x1>=op[nt].x2)||(p.x2<=op[nt].x1)||(p.y1>=op[nt].y2)||(p.y2<=op[nt].y1)))//如果两个矩阵没有相交，直接进入下一层
        nt++;
    if(nt>k)return (p.x2-p.x1)*(p.y2-p.y1);
    if(p.x1<op[nt].x1)
        ans+=get(node(p.x1,op[nt].x1,p.y1,p.y2,op[nt].c),nt+1),p.x1=op[nt].x1;//如果左边存在一整个块都没有被覆盖，就切割下来。
    if(p.x2>op[nt].x2)
        ans+=get(node(op[nt].x2,p.x2,p.y1,p.y2,op[nt].c),nt+1),p.x2=op[nt].x2;//如果右边存在一整个块都没有被覆盖，就切割下来。
    if(p.y1<op[nt].y1)
        ans+=get(node(p.x1,p.x2,p.y1,op[nt].y1,op[nt].c),nt+1),p.y1=op[nt].y1;//如果中间下面存在块，切下来
    if(p.y2>op[nt].y2)
        ans+=get(node(p.x1,p.x2,op[nt].y2,p.y2,op[nt].c),nt+1),p.y2=op[nt].y2;//如果中间上面存在块，切下来
    return ans;
}
int main()
{
    int i,j;
    scanf("%d%d%d",&n,&m,&k);
    ans[1]=n*m;
    rep(i,1,k)scanf("%d%d%d%d%d",&op[i].x1,&op[i].y1,&op[i].x2,&op[i].y2,&op[i].c);
    for(i=k;i>=1;i--)
    {
        ans[op[i].c]+=(j=get(op[i],i+1));
        ans[1]-=j;
    }
    rep(i,1,2500)if(ans[i])printf("%d %d\n",i,ans[i]);
    //system("Pause");
    return 0;
}

当然，这份代码有几个细节可以优化一下：

1
2
3
4
5
6
7
8
9
10
11
12
if(p.x1<op[nt].x1)
        ans+=get(node(p.x1,op[nt].x1,p.y1,p.y2,op[nt].c),nt+1),p.x1=op[nt].x1;//如果左边存在一整个块都没有被覆盖，就切割下来。

这个相当于什么？不就相当于对两个 $x1$ 取 max 吗？

因此可以化成这样：

​```cpp
int x=max(p.x1,op[nt].x1);
if(p.x1<x)
        ans+=get(node(p.x1,x,p.y1,p.y2,op[nt].c),nt+1);//如果左边存在一整个块都没有被覆盖，就切割下来。
//然后后面的p.x1全部用x代替。

然后，其实四个元都可以如此去做，然后我就自己打了一份代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
//这份代码其实参考了参考链接中的代码
#include<cstdio>
#include<cstring>
#define N 1100
using namespace std;
struct node
{
    int x1,y1,x2,y2,co;
}a[N];
inline int mymin(int x,int y){return x<y?x:y;}
inline int mymax(int x,int y){return x>y?x:y;}
int n,m,q;
inline int dfs(int x1,int y1,int x2,int y2,int k)
{
    if(k>q)return (x2-x1)*(y2-y1);
    if(a[k].x1>=x2 || a[k].x2<=x1 || a[k].y1>=y2 || a[k].y2<=y1)return dfs(x1,y1,x2,y2,k+1);
    int k1=mymax(x1,a[k].x1);
    int k2=mymin(x2,a[k].x2);
    int ans=0;
    if(x1<k1)ans+=dfs(x1,y1,k1,y2,k+1);
    if(k2<x2)ans+=dfs(k2,y1,x2,y2,k+1);
    int k3=mymax(y1,a[k].y1),k4=mymin(y2,a[k].y2);
    if(y1<k3)ans+=dfs(k1,y1,k2,k3,k+1);
    if(k4<y2)ans+=dfs(k1,k4,k2,y2,k+1);
    return ans;
}
int ans[2600];
int main()
{
    scanf("%d%d%d",&n,&m,&q);
    q++;a[1].x2=n;a[1].y2=m;a[1].co=1;
    for(int i=2;i<=q;i++)scanf("%d%d%d%d%d",&a[i].x1,&a[i].y1,&a[i].x2,&a[i].y2,&a[i].co);
    for(int i=1;i<=q;i++)ans[a[i].co]+=dfs(a[i].x1,a[i].y1,a[i].x2,a[i].y2,i+1);
    for(int i=1;i<=2500;i++)
    {
        if(ans[i])printf("%d %d\n",i,ans[i]);
    }
    return 0;
}

时间空间消耗等会说。

另外的做法

此题另一种矩阵切割的实现方式

观察就会发现，实际上上面的实现方法，是对一个矩阵，用后面的矩阵对其进行切割，但实际上，我们可以换个角度出发，从可用面积的角度出发，即将背景墙扔进去，从后往前切割，每个矩阵会对背景墙割掉一块，其实这就相当于对每一个矩阵找其没有被后面矩阵覆盖的部分。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include<cstdio>
#include<cstring>
#define N 1100
using namespace std;
struct node
{
    int x1,y1,x2,y2,co;
}a[N];
int ans[2600];
inline int mymin(int x,int y){return x<y?x:y;}
inline int mymax(int x,int y){return x>y?x:y;}
inline void dfs(int x1,int y1,int x2,int y2,int k)
{
    if(!k)return ;
    if(a[k].x1>=x2 || a[k].x2<=x1 || a[k].y1>=y2 || a[k].y2<=y1)
    {
        dfs(x1,y1,x2,y2,k-1);
        return ;
    }
    int k1=mymax(x1,a[k].x1);
    int k2=mymin(x2,a[k].x2);
    if(x1<k1)dfs(x1,y1,k1,y2,k-1);
    if(k2<x2)dfs(k2,y1,x2,y2,k);
    int k3=mymax(y1,a[k].y1),k4=mymin(y2,a[k].y2);
    if(y1<k3)dfs(k1,y1,k2,k3,k-1);
    if(k4<y2)dfs(k1,k4,k2,y2,k-1);
    ans[a[k].co]+=(k2-k1)*(k4-k3);
}
int n,m,q;
int main()
{
    scanf("%d%d%d",&n,&m,&q);
    q++;a[1].x2=n;a[1].y2=m;a[1].co=1;
    for(int i=2;i<=q;i++)scanf("%d%d%d%d%d",&a[i].x1,&a[i].y1,&a[i].x2,&a[i].y2,&a[i].co);
    dfs(0,0,10000,10000,q);
    for(int i=1;i<=2500;i++)
    {
        if(ans[i])printf("%d %d\n",i,ans[i]);
    }
    return 0;
}

这确实是一个不错的转化思路，从每个矩阵最后在背景板的占地面积出发做题。

关于两种做法的空间以及效率问题，空间上的消耗比较小，空间复杂度 $O(q)$ ，但是时间上的消耗就比较玄学了，这个实现方法封顶是 $O(背景板面积)$ ，而上面的做法封顶应该是 $O(所有矩阵面积)$ ，但是实际远小于这个上限，都可以通过该题。

但是呢，我们来比较一下这两个做法：

不难发现，在小规模下，矩阵之间并未相交多次时，这个实现方法对背景板的切割次数较多，较慢，上面的方法因为相交不多，所以会较快，但实际因为规模小，可能不痛不痒，但是在超大规模下，背景板被占满好几次，那么这个方法要远远快于上面的方法，因为这个方法封顶背景板面积，而上面每个矩阵都要计算每个矩阵对其的影响，因此要慢上不少。

但是在中等的规模的数据下呢，鉴于我比较菜，没有时间没有实力去从理论分析（或者实验分析）其在随机数据下的时间表现，也不知道这两个做法较好的卡法，所以希望如果有读者知道，私信我一下，我会写在博客内。当然，我们还是可以阿巴一下的，不难发现，背景板切割只用对一个矩阵切一次（虽然这种切割比较大型），而上面的做法对每个矩阵都要去用后面矩阵切割一次，理论来讲上面做法应该会更慢一点，而在做此例题也确实如此，上面的方法我改了一下每个矩阵后面矩阵的切割顺序（从后往前改成从前往后），超时了，但是即使不改，其依旧比该方法满了一倍的时间。再阿巴一下卡法，显然，很容易构造出一个使上面做法时间超过这个做法时间的数据（把整个背景板加入到数据中）。因此，这道题目方法的选择，我更推荐这种做法。

当然，矩阵切割本身就是暴力算法，优点就是代码好打，比较灵活，空间占用小，缺点就是时间玄学，因此在使用的时候，应该根据题目，主动去思考常数更加小的实现方法，从而骗到更多的分数或者更快的AC题目。

关于例题线段树做法

当然，这道题目我一开始的做法是线段树做法，首先离散化，那么 $n,m$ 范围便只剩下了 $2000$ ，接着，类似最早的思考，考虑每个矩阵被其余矩阵覆盖了多少，类似扫描线一样扫过去就行。

时间复杂度：$O(q^2\log{q})$

空间复杂度：$O(q)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#define M 2100
#define MM 4100
using namespace std;
inline int mymin(int x,int y){return x<y?x:y;}
inline int mymax(int x,int y){return x>y?x:y;}
int be1[M],to1,cn1,cn2,to2,be2[M];
struct Tree
{
    int lc,rc;
    int min,minsum,lazy;
}tr[MM];int len;
inline void pushlazy(int x,int k){tr[x].min+=k;tr[x].lazy+=k;}
inline void updata(int x)
{
    if(tr[tr[x].lc].min<tr[tr[x].rc].min)tr[x].min=tr[tr[x].lc].min,tr[x].minsum=tr[tr[x].lc].minsum;
    else if(tr[tr[x].lc].min>tr[tr[x].rc].min)tr[x].min=tr[tr[x].rc].min,tr[x].minsum=tr[tr[x].rc].minsum;
    else tr[x].min=tr[tr[x].rc].min,tr[x].minsum=tr[tr[x].lc].minsum+tr[tr[x].rc].minsum;
}
inline void pushdown(int x)
{
    if(tr[x].lazy)
    {
        pushlazy(tr[x].lc,tr[x].lazy);pushlazy(tr[x].rc,tr[x].lazy);
        tr[x].lazy=0;
    }
}
void bt(int l,int r)
{
    int x=++len;
    tr[x].min=0;tr[x].minsum=be1[r]-be1[l];tr[x].lazy=0;tr[x].lc=tr[x].rc=0;
    if(l+1<r)
    {
        int mid=(l+r)>>1;
        tr[x].lc=len+1;bt(l,mid);
        tr[x].rc=len+1;bt(mid,r);
    }
}
void change(int x,int l,int r,int ll,int rr,int k)
{
    if(l==ll && r==rr){pushlazy(x,k);return ;}
    pushdown(x);
    int mid=(l+r)>>1;
    if(rr<=mid)change(tr[x].lc,l,mid,ll,rr,k);
    else if(mid<=ll)change(tr[x].rc,mid,r,ll,rr,k);
    else change(tr[x].lc,l,mid,ll,mid,k),change(tr[x].rc,mid,r,mid,rr,k);
    updata(x);
}
struct Query
{
    int x/*在[x,x+1]期间进行该操作*/,l,r,k,tim/*覆盖时间*/;
}qu[M];int cnt;
inline bool cmp1(Query x,Query y){return x.x<y.x;}
struct Ver
{
    int x1,y1,x2,y2,co;
}a[M];
struct node
{
    int *x,val;
}b1[M],b2[M];
inline bool cmp2(node x,node y){return x.val<y.val;}
int n,m,q;
int ans[MM];
int main()
{
    scanf("%d%d%d",&n,&m,&q);
    q++;a[1].x1=a[1].y1=0;a[1].x2=n;a[1].y2=m;a[1].co=1;
    b1[++to1].x=&a[1].x1;b1[to1].val=a[1].x1;
    b1[++to1].x=&a[1].x2;b1[to1].val=a[1].x2;
    b2[++to2].x=&a[1].y1;b2[to2].val=a[1].y1;
    b2[++to2].x=&a[1].y2;b2[to2].val=a[1].y2;
    for(int i=2;i<=q;i++)
    {
        scanf("%d%d%d%d%d",&a[i].x1,&a[i].y1,&a[i].x2,&a[i].y2,&a[i].co);
        b1[++to1].x=&a[i].x1;b1[to1].val=a[i].x1;
        b1[++to1].x=&a[i].x2;b1[to1].val=a[i].x2;
        b2[++to2].x=&a[i].y1;b2[to2].val=a[i].y1;
        b2[++to2].x=&a[i].y2;b2[to2].val=a[i].y2;
    }
    sort(b1+1,b1+to1+1,cmp2);
    sort(b2+1,b2+to2+1,cmp2);
    *b1[1].x=*b2[1].x=cn1=cn2=1;be1[1]=b1[1].val;be2[1]=b2[1].val;
    for(int i=2;i<=to1;i++)
    {
        if(b1[i-1].val!=b1[i].val)cn1++,be1[cn1]=b1[i].val;
        if(b2[i-1].val!=b2[i].val)cn2++,be2[cn2]=b2[i].val;
        *b1[i].x=cn1;*b2[i].x=cn2; 
    }
    for(int i=1;i<=q;i++)
    {
        qu[++cnt].x=a[i].y1;qu[cnt].l=a[i].x1;qu[cnt].r=a[i].x2;qu[cnt].tim=i;qu[cnt].k=1;
        qu[++cnt].x=a[i].y2;qu[cnt].l=a[i].x1;qu[cnt].r=a[i].x2;qu[cnt].tim=i;qu[cnt].k=-1;
    }
    sort(qu+1,qu+cnt+1,cmp1);
    for(int i=1;i<=q;i++)
    {
        len=0;
        if(a[i].x1<a[i].x2)bt(a[i].x1,a[i].x2);
        int now=1;
        for(int j=a[i].y1;j<a[i].y2;j++)
        {
            while(now<=cnt && qu[now].x<=j)
            {
                if(qu[now].tim>i)
                {
                    int l=mymax(a[i].x1,qu[now].l),r=mymin(a[i].x2,qu[now].r);
                    if(l<r)change(1,a[i].x1,a[i].x2,l,r,qu[now].k);
                }
                now++;
            }
            if(!tr[1].min)ans[a[i].co]+=(be2[j+1]-be2[j])*tr[1].minsum;
        }
    }
    for(int i=1;i<=2500;i++)
    {
        if(ans[i])printf("%d %d\n",i,ans[i]);
    }
    return 0;
}

当然，你也可以用线段树实现矩阵切割第二种方法类似的思路（每个矩阵在背景板的占地面积），但是貌似这样子常数更大。QMQ

总结

介绍了矩阵切割算法，一个灵活的、空间小的、代码好打的、好想的、但时间玄学的算法，在范围在千以内的时候可以试着使用一下，万以上就不知道了。（其实我也就用过一次，什么时候可以用还是你们自己去摸索吧。）

参考资料

<模板> 矩形分割_无奈滴微笑-CSDN博客

题解 P6432 【[USACO3.1]形成的区域 Shaping Regions】 - blog-lhm - 洛谷博客 (luogu.com.cn)