My learning note on AGC061C based on Little09's (Simplified) Chinese Blog
Разница между en46 и en47, 150 символ(ов) изменены
I admit that [AGC061C](https://atcoder.jp/contests/agc061/tasks/agc061_c) is too hard for me, and I don't even understand its [official editorial](https://atcoder.jp/contests/agc061/editorial/5695). Today I see a [Luogu blog](https://www.luogu.com.cn/blog/LJA001111/agc061c-first-come-first-serve) with a very genius and clear idea on this problem. I learned a lot from it, and I would like to share it to you now. The writer of this blog is possibly [user:little09,2023-02-15], but I am not quite sure.↵

**Part1: Problem Statement and Constraints**↵

There are $N$ customers named $1$, ..., $N$ visiting a shop. Customer $i$ arrives at time $A_i$ and leaves at time $B_i$ ↵
The queue order is first in first out, so $A_i$ and $B_i$ are both increasing. Additionally, all $A_i$ and $B_i$ are pairwise distinct.↵

At the entrance, there's a list of visitors to put their names in. Each customer will write down their name next in the list exactly once, either when they arrive or when they leave. How many different orders of names can there be in the end? Find the count modulo $998244353$.↵

Constraints:↵

$\cdot 1 \leq N \leq 500000$.↵

$\cdot 1 \leq A_i \leq B_i \leq 2N$.↵

$\cdot A_i < A_{i+1}\,(1 \leq i \leq N-1)$.↵

$\cdot B_i < B_{i+1}\,(1 \leq i \leq N-1)$.↵

$\cdot A_i \neq B_j \,(i \neq j)$.↵

$\cdot \text{All values in the input are integers}$.↵

**Part2: Idea in the blog**↵

Consider two dynamic programming tables named $f$ and $g$ ($dp$ in the original blog). The blog computes $f,\,g$ in the **reverse** order. Formally,↵

$f(i)\,(1 \leq i \leq n)$: The number of permutations when we have already considered persons $i,\,i+1,\,...,\,n$.↵

$g(i)\,(1 \leq i \leq n)$: The number of permutations when we have already considered persons $i,\,i+1,\,...,\,n$, and the person $i$ is forced to sign her (or his) name on $B_i$.↵

The blog defines $c(i)$ as:↵

$c(i) := max\\{j|A_j < B_i\\}$. (1)↵

Obviously $i \in \\{j|A_j < B_i\\}$ and $c(i) \geq i$.↵

![ ](/predownloaded/94/9a/949a53d0200623be160967cc32379496f8aaf30d.png)↵

First, we consider $f(i)$. If $i$ signs on $A_i$, then no matter when $i+1,\,i+2,\,...\,n$ sign their name, $i$ is always placed in front of them. It is a bijection, given a permutation $p$ of $[i+1,\,i+2\,...\,n]$, just add $i$ in the front of $p$. The number of distinct permutations when $i$ signs on $A_i$ is just $f(i+1)$. If $i$ signs on $B_i$, then $i$ **must not be placed the first** among $\\{i,\,i+1,\,...,\,n\\}$, otherwise it is overlapped with a situation where $i$ signs on $A_i$. Now we consider the number of permutations that $i$ is placed the first among $\\{i,\,i+1,\,...,\,n\\}$. In this case ($i$ is the first), $x \in \\{i+1,\,i+2\,...,\,c(i)\\}$ should all sign on $B_x$ because $A_x < B_i$ (according to the definition of $c$ in Eq.(1)), and the choices of $x \in \\{c(i)+1,\,...,\,n\\}$ are not important. The number of the permutations that $i$ signs on $B_i$ and $i$ is placed the first among $\\{i,\,i+1,\,...,\,n\\}$ is $g(c(i))$, because $c(i)$ must chooses $B_{c(i)}$ and $\\{c(i)+1,\,j+2\,...,\,n\\}$ can choose freely. Therefore, the situation where $i$ signed on $B_i$ contributes $g(i) - g(c(i))$ to $f(i)$. $f(i)$ depends on $g$: ↵

 $f(i) = f(i+1) + g(i) - g(c(i))$. (2)↵

![ ](/predownloaded/2c/f1/2cf16abdf1d82e4f6f87ee556f9e2870462f7ef2.png)↵

Second, we consider $g(i)$. To count $g(i)$, an important idea is to divide it into non-overlapping cases. The blog consider ↵

$P_j$ := The set of permutations where $j$ is the least integer among $\\{i+1,\,i+2\,...,\,c(i)\\}$ such that $j$ chooses $B_j$. In other words, $i$ chooses $B_i$, $\\{i+1,\,i+2\,...,\,j-1\\}$ all choose $A$, and $j$ chooses $B_j$. Also, we should **not** forget $P_{c(i)+1}$, because $\\{i+1,\,i+2\,...,\,c(i)\\}$ might all choose $A$!↵

(1)Do these $P_j$ (including $P_{c(i)+1}$) overlap? No! Because the permutations in $P_j$ has a unique prefix: $[i+1\,i+2\,...,\,j-1]$.↵

(2)Do these $P_j$ cover all situations? Yes, this is obvious.↵

(3)How to calculate the size of $P_j$, i.e., $|P_j|$? For $j \leq c(i)$, since the prefix is fixed ($[i+1\,i+2\,...,\,j-1]$ mentioned in (1)), there is a bijection from the set $g(j)$ to $P_j$ by adding the fixed prefix to the element in $g(j)$. So the size of $|P_j|$ is just $g(j)$. For $j=c(i)+1$, $|P_j|=f(c(i)+1)$ because all $\\{i+1,\,i+2\,...,\,c(i)\\}$ have to choose $A$.↵

Therefore, ↵

$g(i) = \sum\limits_{j=i+1}^{c(i)} g(j) + f(c(i)+1)$ (3)↵

Although we consider $f$ first, we should calculate $g$ first because $f$ depends on $g$.↵

**Part3: Implementation details**↵

(1) You can use two pointers to calculate $c$.↵
Therefore, ↵

$g(i) = \sum\limits_{j=i+1}^{c(i)} g(j) + f(c(i)+1)$ (3)↵


(2) To make the computation of $g$ faster, you can use the prefix sum trick.↵

(3) The original blog considers two cases: $c(i)=i$ and $c(i)<i$. They can be unified into equations (2) and (3), i.e., there is actually not necessary to consider two cases.↵

(4) In the original blog [user:Little09,2023-02-15] calculates from $n$ to $1$. You can also calculate from $1$ to $n$. Symmetrically, you should define $c(i)$ as $min\\{j|B_j > A_i\\}$, and define $g(i)$ as "The number of permutations when we have already considered persons $1,\,2,\,...,\,i-1$, and the person $i$ is forced to sign her (or his) name on $A_i$". [Here is my implementation](https://atcoder.jp/contests/agc061/submissions/38908757) that calculates from $1$ to $n$.↵

**Part4: What I have learned**↵

(1) The most important idea in counting is dividing into non-overlapping sets whose unions are the whole set. Besides, the counting of each set should be much simpler.↵

(2) The most important thing of dp is defining states.↵

(3) Bijections are really important in combinatorics. For example, the [Dyck path](https://math.mit.edu/~apost/courses/18.204-2016/18.204_Gabriella_Baracchini_final_paper.pdf).↵

(4) Achieving (1) and (2) requires high IQ and talent. For example, the definition of $f$ in the blog is normal, while the definition of $g$ is genius!↵

**Part5: The last**↵

If you have any questions, please don't hesitate to ask me. It is beneficial for both of us. For you, I might resolve your confusion. For me, I can check whether I make a typo in the blog or not and whether I really understand this blog or not.↵


История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en55 Английский CristianoPenaldo 2023-02-18 13:01:26 4 Tiny change: ' and $c(i)<i$. They c' -> ' and $c(i) > i$. They c'
en54 Английский CristianoPenaldo 2023-02-15 19:06:57 5 Tiny change: '{c(i)+1,\,j+2\,...,\,' -> '{c(i)+1,\,c(i)+2\,...,\,'
en53 Английский CristianoPenaldo 2023-02-15 19:06:01 1 Tiny change: 'fix: $[i+1\,i+2\,...' -> 'fix: $[i+1,\,i+2\,...'
en52 Английский CristianoPenaldo 2023-02-15 19:00:40 9
en51 Английский CristianoPenaldo 2023-02-15 18:26:48 58
en50 Английский CristianoPenaldo 2023-02-15 18:06:47 4 Tiny change: 'rt2: Idea in the blog*' -> 'rt2: Idea of the blog*'
en49 Английский CristianoPenaldo 2023-02-15 17:36:32 14 Tiny change: '3), i.e., there is actually not neces' -> '3), i.e., it is not neces'
en48 Английский CristianoPenaldo 2023-02-15 17:31:03 1 Tiny change: 'their name, $i$ is a' -> 'their names, $i$ is a'
en47 Английский CristianoPenaldo 2023-02-15 17:19:57 150
en46 Английский CristianoPenaldo 2023-02-15 17:11:30 2 Tiny change: '\n\n**Part4: The last' -> '\n\n**Part5: The last'
en45 Английский CristianoPenaldo 2023-02-15 17:09:23 62
en44 Английский CristianoPenaldo 2023-02-15 17:05:53 32 Tiny change: 'he first**, otherwis' -> 'he first** among $\\{i,\,i+1,\,...,\,n\\}$, otherwis'
en43 Английский CristianoPenaldo 2023-02-15 17:04:42 4 Tiny change: 'dd $i$ in front of ' -> 'dd $i$ in the front of '
en42 Английский CristianoPenaldo 2023-02-15 17:03:34 6
en41 Английский CristianoPenaldo 2023-02-15 17:02:11 11 Tiny change: 'e $A$.\n\nFinally, although we' -> 'e $A$.\n\nAlthough we'
en40 Английский CristianoPenaldo 2023-02-15 17:01:24 11 Tiny change: 'th a very clear ide' -> 'th a very genius and clear ide'
en39 Английский CristianoPenaldo 2023-02-15 17:00:40 178
en38 Английский CristianoPenaldo 2023-02-15 16:52:57 216
en37 Английский CristianoPenaldo 2023-02-15 16:48:30 1 Tiny change: 'i \neq j)$\n\n$\cdot' -> 'i \neq j)$.\n\n$\cdot'
en36 Английский CristianoPenaldo 2023-02-15 16:48:07 6
en35 Английский CristianoPenaldo 2023-02-15 16:47:40 272 (published)
en34 Английский CristianoPenaldo 2023-02-15 16:44:14 651
en33 Английский CristianoPenaldo 2023-02-15 16:32:35 2 Tiny change: 'j=i+1}^{c(j)} g(j) + ' -> 'j=i+1}^{c(i)} g(j) + '
en32 Английский CristianoPenaldo 2023-02-15 16:25:16 4
en31 Английский CristianoPenaldo 2023-02-15 16:06:22 74 Tiny change: '\geq i$.\n\n![ ](htt' -> '\geq i$.\n![ ](htt'
en30 Английский CristianoPenaldo 2023-02-15 16:05:39 64
en29 Английский CristianoPenaldo 2023-02-15 16:03:18 60
en28 Английский CristianoPenaldo 2023-02-15 16:01:46 149
en27 Английский CristianoPenaldo 2023-02-15 15:51:47 56
en26 Английский CristianoPenaldo 2023-02-15 15:50:00 2 Tiny change: 's_{j=i+1}^c(j) g(j) + f(' -> 's_{j=i+1}^{c(j)} g(j) + f('
en25 Английский CristianoPenaldo 2023-02-15 15:48:45 191
en24 Английский CristianoPenaldo 2023-02-15 15:45:44 542
en23 Английский CristianoPenaldo 2023-02-15 15:36:54 6
en22 Английский CristianoPenaldo 2023-02-15 15:36:08 44
en21 Английский CristianoPenaldo 2023-02-15 15:34:44 139
en20 Английский CristianoPenaldo 2023-02-15 15:30:07 742
en19 Английский CristianoPenaldo 2023-02-15 15:22:23 8
en18 Английский CristianoPenaldo 2023-02-15 15:20:53 327
en17 Английский CristianoPenaldo 2023-02-15 15:17:02 241
en16 Английский CristianoPenaldo 2023-02-15 15:12:05 355
en15 Английский CristianoPenaldo 2023-02-15 15:05:27 708
en14 Английский CristianoPenaldo 2023-02-15 14:57:22 153
en13 Английский CristianoPenaldo 2023-02-15 14:55:41 359
en12 Английский CristianoPenaldo 2023-02-15 14:52:52 75 Tiny change: 'eq i$.\n\n\n' -> 'eq i$.\n\n![ ](https://codeforces.me/633ccf/blog.png)\n\n\n'
en11 Английский CristianoPenaldo 2023-02-15 14:41:38 55
en10 Английский CristianoPenaldo 2023-02-15 14:33:54 279
en9 Английский CristianoPenaldo 2023-02-15 14:28:39 696
en8 Английский CristianoPenaldo 2023-02-15 14:20:37 15 Tiny change: '\text{All inputs are integ' -> '\text{All values in the input are integ'
en7 Английский CristianoPenaldo 2023-02-15 14:19:48 214
en6 Английский CristianoPenaldo 2023-02-15 14:16:46 46 Tiny change: '98244353$.' -> '98244353$.\n\nConstraints:\n$\cdot 1 \leq N \leq 500000$'
en5 Английский CristianoPenaldo 2023-02-15 14:16:07 30
en4 Английский CristianoPenaldo 2023-02-15 14:14:35 565
en3 Английский CristianoPenaldo 2023-02-15 14:11:37 116
en2 Английский CristianoPenaldo 2023-02-15 14:10:18 278
en1 Английский CristianoPenaldo 2023-02-15 13:31:51 165 Initial revision (saved to drafts)