There is a square grid of size 𝑛×𝑛. Some cells are colored in black, all others are colored in white. In one operation you can select some rectangle and color all its cells in white. It costs min(ℎ,𝑤) to color a rectangle of size ℎ×𝑤. You are to make all cells white for minimum total cost.

The square is large, so we give it to you in a compressed way. The set of black cells is the union of 𝑚 rectangles.

#### 链接 🔗

「CodeForces 1198E」 Rectangle Painting 2

#### 题解 ❓

$1198D$的升级版，不过是两个问题

#### 代码

struct
{
ll x,y,r,c;
}a[maxd];
ll fx[maxd],fy[maxd],tot,sx,sy;
int main()
{
//    __IN;__OUT;
ll n,m; RLL(m);RLL(n); init();
F(n)
{
RLL(fx[sx]);a[i].x = fx[sx++];
RLL(fy[sy]);a[i].y = fy[sy++];
RLL(fx[sx]);a[i].r = ++fx[sx++];
RLL(fy[sy]);a[i].c = ++fy[sy++];
}
sort(fx,fx+sx);sort(fy,fy+sy);
sx =  unique(fx,fx+sx) - fx;
sy =  unique(fy,fy+sy) - fy;
s = 0, t = sx+sy+1;
FOR(i,1,sy-1) addedge(sx - 1 + i,t,fy[i] - fy[i-1]);
F(n)
{
a[i].x = lower_bound(fx, fx + sx, a[i].x) - fx;
a[i].y = lower_bound(fy, fy + sy, a[i].y) - fy;
a[i].r = lower_bound(fx, fx + sx, a[i].r) - fx;
a[i].c = lower_bound(fy, fy + sy, a[i].c) - fy;
for (int x = a[i].x; x < a[i].r; x++)
for (int y = a[i].y; y < a[i].c; y++)  addedge(x + 1, sx + y, 2e9);
}
PLN(maxflow());

return 0;
}