ABC222 D - Between Two Arrays (400)
$ dp[i][j] でi番目の要素をjとした時の条件を満たす場合の数とする
単純に実装すると、$ dp[i][j] = \sum_{k=0}^{j-1} dp[i-1][k] ただし、$ a_i \le j \le b_i
$ \mathcal{O}(\max B)かかるので全体では$ \mathcal{O}(N (\max B)^2)になってしまう
和を求める部分をセグ木にすると一個あたりが$ \mathcal{O}(\log \max B)になる
累積和を使うと全体で$ \mathcal{O}(N \max B)