### tzc_wk's blog

By tzc_wk, history, 6 months ago, ,

Recently I'm learning network flow. Could anyone give me a list of problems of network flow on Codeforces & Gym & Atcoder. Not too hard, just with difficulty 2300~2700. Thanks a lot.

• +10

By tzc_wk, history, 7 months ago, ,

I've thought of another solution of problem D during the contest, which may also be possible.

Let $S_{i,0}$ be the set of intervals that overlaps with interval in venue A, and $S_{i,1}$ be the set of intervals that overlaps with interval in venue B. Then we only need to check $S_{i,0}!=S_{i,1}$.

As a set is hard to express, we can express them in the binary form, i.e. the $2^0$ digit of the binary form is $1$ if the $i$-th interval overlaps with interval $1$, $0$ otherwise; the $2^1$ digit of the binary form is $1$ if the $i$-th interval overlaps with interval $1$, $2$ otherwise and so on. As the number is rather large, we may modulo with a large number, for example $993244853$. Then the only thing we need to do is calculate $S_{i,0}$ and $S_{i,1}$.

Take venue A as an example. We may find that $S_{i,0}$ equals to the whole set $-$ the set of intervals that do not intersect with them. Suppose there is an interval $[a,b]$, then interval $[c,d]$ do not intersect with it if and only if $d<a$ or $c>b$. To calculate the first situation, we can sort the intervals by left bound non-decreasing order, add $2^{id_i}$ on position $y_i$ using BIT, where $id_i$ is the original index of the interval, and the set of the first situation equals to $sum(x_i-1)$. To calculate the second situation, we can sort the intervals by right bound non-increasing order, add $2^{id_i}$ on position $x_i$ using BIT, where $id_i$ is the original index of the interval, and the set of the first situation equals to $sum(1e9)-sum(y_i)$. Then we use $2^n-1$ minus the two sets and we can get $S_{i,0}$. As the bounds may be large, we need to discrete it.

Total time complexity: $O(nlogn)$.