[ABC221D] Online games

[ABC221D] Online games

难度：\(832\)
标签：差分 离散化
\(\mathtt{blog}\)

有 \(n\) 个区间 \([a_i,a_i+b_i)\)，问各被 \(1\sim n\) 个区间覆盖的数字个数有多少个。

\(n\le2\times10^5,1\le a_i,b_i\le 10^9\)

老套路题了。

对于一个区间 \(p_{l\sim r}+1\) 就用差分改变为 \(s_l+1,s_{r+1}-1\) 然后前缀和求解 \(p_i=\sum_{j=1}^is_j\)。

但是对于这题能发现 \(a_i,b_i\le 10^9\)，枚举肯定会 T，发现 \(n\le 2\times 10^5\)，离散化即可。

\(\mathtt{Code}\)