Rectangle Shrinking: A range-set based method, and an advertisement for CFStress!
Difference between en26 and en27, changed 8 character(s)
Problem: [Rectangle Shrinking](https://mirror.codeforces.com/problemset/problem/1782/e)↵

Part 1: **Notations**↵

$x$: A brick. $x_i$ denotes the part of $x$ belonging to the $i$-th floor. For example, if $x.u=1,\,x.d=2$, then $x_1.u=x_1.d=1$, $x_2.u=x_2.d=2$, and $x_1.l=x_2.l=x.l$, $x_1.r=x_2.r=x.r$.↵

$A_i,\,i=1,2$: The set of bricks whose $u=d=i$.↵

$B$: The set of bricks whose $u=1,\,d=2$.↵

$\texttt{Remove}$: Remove a brick $x$.↵

$\texttt{Shrink}$: Shrink a brick $x$ to another **non-empty** brick.↵

$\texttt{Keep}$: Keep a brick $x$ unchanged.↵

Note that in our solution we may operate on a part of brick. For example, for a brick $x \in B$, we may $\texttt{Keep}\,x_1$ while $\texttt{Remove}\,x_2$.↵

Part 2: **Idea**↵

I think $\texttt{Shrink}$ing $x \in B$ is troublesome. If you shrink $x_1$, you have to shrink $x_2$ in the same way, i.e., $x_1$ has to be aligned with $x_2$. So is there a solution that only performs $\texttt{Remove}$ and $\texttt{Keep}$ on every $x \in B$? But that is impossible, because the bricks $x, y \in B$ may overlap themselves even with considering $A$. So what if $B$ are pairwise non-overlapping (because we could perform some pre-$\texttt{Shrink}$ and pre-$\texttt{Remove}$ to make $B$ pairwise non-overlapping)? [Pre-computation]↵

In that case, we can consider each floor independently. Let ↵

$C_i := A_i \cup \\{x_i \mid x \in B \\}$. ↵

For example, if ↵

$A_1 = \\{[u=1, d=1, l=2, r=5], [u=1, d=1, l=7, r=10]\\}$, ↵

$B=\\{[u=1, d=2, l=2, r=2], [u=1, d=2, l=4, r=7]\\}$, then ↵

$C_1 = \\{[u=1, d=1, l=2, r=2], [u=1, d=1, l=2, r=5], [u=1, d=1, l=4, r=7], [u=1, d=1, l=7, r=10]\\}$. ↵

We sort $C_i$ w.r.t $l$, and traverse $C_i$ like $\texttt{for(auto x: C_i)}$. ↵

Case 1 ($\texttt{Keep}$): If $x$ is not overlapping now, then we add $x$ to the answer, no matter if $x$ is from $A_i$ or not. ↵

Case 2 ($\texttt{Remove}$): If $x$ is fully contained in the union of other rectangles, then we always remove $x$, no matter if $x$ is from $A_i$ or not. ↵

$\texttt{Keep}$ and $\texttt{Remove}$ are relatively easier, no matter $x \in A_i$ or $x \in \\{x_i \mid x \in B \\}$.↵

Case 3 ($\texttt{Shrink}$): If $x$ is partially overlapping with other bricks.↵

Case 3.1: If $x \in A_i$: $\texttt{Shrink} x$. Move the $x.l$ to the right to avoid overlapping.↵

Case 3.2: If $x \in \\{x_i \mid x \in B \\}$: $\texttt{Shrink}$ all bricks that overlap with $x$ by moving their right endpoints (i.e., *.r), to the left.↵

![ ](/predownloaded/0d/c7/0dc72e9de6a90534ebf9d2379001907567d7cadb.png)↵

It is guaranteed in Case 3.2 that every brick overlapping with $x$ is from $A_i$ because we have already performed pre-calculations in $B$ to make them non-overlapping. The complexity is not an issue, by amortized analysis, each $x \in A_i$ will do $\texttt{Remove}$ at most once and $\texttt{Remove}+\texttt{Shrink}$ at most twice (keep/move left endpoint+keep/move right endpoint). ↵

Part 3: **Implementation**↵

First I copy a range-set [implementation](https://atcoder.jp/contests/arc151/submissions/35725980) from [user:nok0,2023-01-18]. Basically, it maintains a set of intervals using $\texttt{std::set}$. When inserting/erasing a range, it can merge/split/erase intervals automatically, using binary search (Yes, stop learning useless algorithms, go to learn binary search!). It supports many APIs, here are some useful APIs in our implementation:↵

(1) $\texttt{Insert(l, r)}$: Insert an interval $[l, r]$.↵

(2) $\texttt{covered_by(l, r)}$: Return an interval covering $[l, r]$, if not exists, returning $(-\infty, \infty)$.↵

(3) $\texttt{covered(l, r)}$: Return a bool variable indication whether interval $[l, r]$ is fully covered. ↵

(4) $\texttt{right(x)}$: Return $\min \\{y|y \geq x, y \text{ is not covered}\\}$. Note that API could calculate the $\texttt{mex}$, so it is also useful for calculating the [Sprague-Grundy (SG) number](https://en.wikipedia.org/wiki/Sprague%E2%80%93Grundy_theorem). SG number is irrelevant to our topic.↵

(5) $\texttt{left(x)}$ (added by me): Return $\max \\{y|y \leq x, y \text{ is not covered}\\}$.↵

There are also APIs that we don't use in this implementation, but they are also beneficial:↵

(6) $\texttt{Erase(l, r)}$: Erase $[l, r]$. That may lead to interval splitting, for example, if we erase $[2, 3]$ from $[1, 4]$, we get two intervals remaining: $[1, 1]$ and $[4, 4]$.↵

(7) $\texttt{size}$: Get the size of intervals.↵

(8) $\texttt{dump}$: Output all intervals for debugging.↵

So, we implement the pre-computation step (first paragraph in Part2) as follows:↵

~~~~~↵
sort B w.r.t l (left endpoint).↵
Initial a range set named rs.↵
for(auto& x: B){↵
    int rightl = rs.right(x.l), leftr = rs.left(x.r);↵
    if(right <= rightr){↵
        rs.insert(rightl, leftr);↵
        for(int i = 1; i <= 2; ++i)  {↵
             Ci = Ai; Ci.push_back({x.u, x.rightl, x.d, x.leftr, x.id}); //push into Ci↵
        }↵
    }else{↵
        //Case 2, fully contained, remove it!↵
        //We actually do nothing here↵
    }↵
}  ↵
~~~~~↵

Then, how to calculate $C_i$ from each floor independently? We need another set that is sorted by $r$ in the ascending order, let's call it $\texttt{sortbyr}$, to maintain rectangles in $A_i \subseteq C_i$. If Case 3.2 happens, we need to find such $y \in \texttt{sortbyr}$ quickly by $\texttt{sortbyr.lower_bound(x.l)}$, i.e., find an interval $y \in A_i$ quickly, using binary search, such that the right endpoint of $y$ ($y.r$) is greater or equal than $x.l$. Note that when we find such an $y$, you need to iterate to the end of $\texttt{sortbyr}$, that's why my previous submissions WA at test15--I only handle **one of them**. Here is the sketch of the implementation:↵

~~~~~↵
for(int i = 1; i <= 2; ++i){↵
    Initialize sortbyr; //Remember to initialize because we handle each floor independently!↵
    sort(Ci.begin(), Ci.end());↵
    Initial a range set named rs.↵
    for(auto x: Ci){↵
         bool lcovered = rs.covered(l), rcovered = rs.covered(r);↵
         if(!lcovered && !rcovered){↵
             //Case 1, Keep↵
             if(u == d){↵
                sortbyr.insert({x.u, x.l, x.d, x.r, x.id});↵
             }↵
             ans[x.id].insert(node{j+1, x.l, j+1, x.r, x.id}); //No matter u == d or u != d, we only consider one floor here!↵
             rs.insert(x.l, x.r);↵
         }else if(lcovered && !recovered){↵
             if(u == d){↵
                 //Case 3.1↵
                 int rightl = rs.right(l);↵
                 ans[x.id].insert(x.u, x.rightl, x.d, x.r, x.id);↵
                 rs.insert(rightl, x.r);↵
                 sortbyr.insert(x.u, x.rightl, x.d, x.r, x.id});↵
             }else{↵
                 //Case 3.2↵
                 auto y = sortbyr.lower_bound({-1, -1, -1, x.l, -1});↵
                 while(y != sortbyr.end()){↵
                     //Here, we should deal with all overlaps! That's why my previous submissions WA on test15↵
                     auto [u2, l2, d2, r2, id2] = *y;↵
                     //Here l2 <= l because we sort Ci by l. So sortbyr only contains elements whose left endpoint <= l!↵
                     //By lower_bound, we have r2 >= x.l↵
                     ans[id2].erase({u2, l2, d2, r2, id2}); //We erase it from our answer↵
                     sortbyr.erase(y++);↵
                     ans[x.id].insert({j+1, x.l, j+1, x.r, x.id}); //We never shrink the splitted ones↵
                     rs.insert(x.l, x.r); //Although [l, r] overlaps with [l2, r2], range set will merge them automatically!↵
                     if(l2 <= l-1){ //Be careful! r2 may <= r, so y after shrinking may be empty!! ↵
                         ans[id2].insert({u2, l2, d2, x.l-1, id2});↵
                         sortbyr.insert({u2, l2, d2, x.l-1, id2});↵
                     }↵
                 }↵
             }//Case 3.2↵
         }//Case 3↵
    }//for↵
}↵
~~~~~↵

In the above implementation, it is not possible that $\texttt{!lcovered && rcovered}$, otherwise $[l, r]$ is covered by some $[l_1, r_1]$ which $l_1 > l$. But we have already sorted $C_i$ by $l$. And, if $l$ and $r$ are both covered, we just ignore and \texttt{Remove} this segment.↵

Finally, we need to output the answer, for this part please refer to the [code](https://mirror.codeforces.com/contest/1782/submission/189601171). Note that due to the implementation, we may insert two parts of bricks for $b \in B$. I mean, for $x = \\{1, l, 2, r, id\\} \in B$, the implementation might insert both $\\{1, l, 1, r, id\\}$ and $\\{2, l, 2, r, id\\}$ into $ans[id]$, so we need to merge them manually, that is dirty work.↵

Here is an advertisement for CFStress: Although my [previous submission](https://mirror.codeforces.com/contest/1782/submission/189433130) WA on case5 of test15, [CFStress](https://cfstress.com/status/16701) could still find a very small counterexample in a very short time! As mentioned [here](https://mirror.codeforces.com/blog/entry/110936), My debugging ability is really poor, so I don't use CFStress very frequently, as I often debug myself to improve my debugging ability. However, CFStress has saved me many times from insomnia. Thanks, [user:variety-jones,2023-01-18]!↵



 ↵



History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en28 English div4only 2023-01-19 10:07:25 11
en27 English div4only 2023-01-18 09:17:02 8 Tiny change: 'Idea**\n\nI think $\texttt{S' -> 'Idea**\n\n$\texttt{S'
en26 English div4only 2023-01-18 09:13:15 0 (published)
en25 English div4only 2023-01-18 09:12:44 308 (saved to drafts)
en24 English div4only 2023-01-18 07:43:04 62 (published)
en23 English div4only 2023-01-18 07:37:35 947
en22 English div4only 2023-01-18 07:26:22 1518
en21 English div4only 2023-01-18 07:16:13 1038
en20 English div4only 2023-01-18 07:05:57 359
en19 English div4only 2023-01-18 07:01:15 575
en18 English div4only 2023-01-18 06:52:37 715
en17 English div4only 2023-01-18 06:45:27 415
en16 English div4only 2023-01-18 06:40:31 289
en15 English div4only 2023-01-18 06:37:21 175
en14 English div4only 2023-01-18 06:33:17 392
en13 English div4only 2023-01-18 06:28:14 54
en12 English div4only 2023-01-18 06:26:31 133
en11 English div4only 2023-01-18 06:13:39 2 Tiny change: '\in A_i$: \texttt{Shrink} $x$. Move t' -> '\in A_i$: $\texttt{Shrink} x$. Move t'
en10 English div4only 2023-01-18 06:13:00 695
en9 English div4only 2023-01-18 06:06:09 24
en8 English div4only 2023-01-18 06:05:37 81
en7 English div4only 2023-01-18 06:02:02 271
en6 English div4only 2023-01-18 05:57:36 345
en5 English div4only 2023-01-18 05:51:57 287
en4 English div4only 2023-01-18 05:49:42 499
en3 English div4only 2023-01-18 05:45:33 779
en2 English div4only 2023-01-18 05:45:13 779
en1 English div4only 2023-01-18 05:36:49 304 Initial revision (saved to drafts)