一見して端からDPすれば良さそうに見える。つまり、$\operatorname{dp}[x] :=$位置$x$から始まる最長の部分列の長さ、として$\operatorname{dp}[N-1]=1$から逆順に埋めていく方法が考えらえるが、単純に$\operatorname{dp}[x] \leftarrow 1+\max \{\operatorname{dp}[y] : x|yかつx < yかつA_x < A_y\}$と遷移すると間に合わない。
約数の数があまり多くないことを利用すると遷移の数を減らせそう。つまり、$A_y (< A_x)$が$A_x$の約数であるような$y( と遷移したい。ただ、これでは同一の約数がたくさん存在するときに遷移先の候補が減っていない。同一の約数についてはいちばん右のものだけ見ればよいから、 を最初に作っておいて、適当にポップしながらスタックの先頭にだけ遷移すればよい。
$C_q := a_1a_{q-1} + a_2a_{q-2} + ... +a_{q-1}a_1$とすると、漸化式は次のように書ける:
$$ \begin{aligned} C_q & = a_1a_{q-1} + a_2a_{q-2} + ... + a_{q-2}a_2 +a_{q-1}a_1 \\ & = a_1(pa_{q-2} + a_{q-3}) + a_2(pa_{q-3} + a_{q-4}) + ... a_{q-2}(pa_1 + a_0)+ a_{q-1}a_1 \\ & = p(a_1a_{q-2} + ... + a_{q-2}a_1) + (a_1a_{q-3}+...+a_{q-3}a_1) + a_{q-2} \\ & = pC_{q-1}+C_{q-2} + a_{q-2} \end{aligned} $$ただし$a_0 = 1$とする。
同一の直線は最初に除いておく。以下、$N$本の直線は相異なるとする。
平面走査的に考えてみる。つまり、十分に大きな正数$a$について$x$軸に平行な直線$L: y=a$を用意して、この直線を下に移動しながら領域の数を数える。$y=a$と平行な直線はないとしてよい。[1] 最初に直線$L$は$N$本の直線と交わっていて、これらに区切られた$N+1$個の領域にまたがっている。$L$を下に移動していくとき、$L$が新たな領域に出会うのは直線の交点に一致した瞬間である。このとき、交点を通る直線が2本なら領域が1つ増え、3本なら2つ増え、一般に$k$本の直線の交点では$k-1$本増えている。
以上の観察より、単に$l_1$から順に直線を追加していき、新しい直線を追加するたびにこれまで追加した各直線と交わる点を（平行でなければ）検出し、同じ交点を検出した回数を数えていけばよい。
$N$本の直線を処理したあと、ある交点$P$をちょうど$2$本の直線が通ったなら、$P$は$1$回数えられ、$3$本なら$1+2 = 3$回数えられる。一般に、$k+1$本の直線の交点は$1+2+...+k = k(k+1)/2$回数えられていて、そこで増えた領域は$k$個になっている。二次方程式を解くと、点$P$が$v$回数えられたならそこで増えた領域は$(-1+\sqrt{1+8v})/2$個である。計算量は${O}(N^2)$。
あったら、全体を適当に回転させたものを考えればよい。 ↩︎
$f(x) :=x$回目でONになっている確率とすると、漸化式は
$$ \begin{aligned} f(x) & = \sum_k^{x-1} k\text{回目でOFFで、あとはずっとONである確率} \\ & = \sum_k^{x-1}(1-f(k))p(1-p)^{x-k-1} \end{aligned}$$このままでは間に合わないので差分を計算すると、$f(x)-f(x-1) = p(1-2f(x-1))$になっていて、$f(x) = p + (1-2p)f(x-1)$という線形漸化式が従う。$f(x)-1/2 = (1-2p)(f(x-1) -1/2)$より、$f(x) = 1/2 + (1-2p)^x(f(0)-1/2) = 1/2 + (1-2p)^x\cdot(-1/2)$と表せて、これなら計算できる形になっている。
……と迂遠な導出をしてしまったが、よく見ると自明に$f(x) = p(1-f(x-1)) + (1-p)f(x-1)$だった。直前から求まるかどうかは常に最初に考えるべき。
$p=1$の場合に計算誤差が問題になるようだった。(expt -1d0 奇数)は-1になってほしいが、指数が大きいと1になる。手元だと境界はこの辺:
> (expt -1d0 9007199254740991)
-1.0d0
> (expt -1d0 9007199254740993)
1.0d0
前者($=2^{53}-1$)がdouble-floatで正確に表現できる最大の整数なので、そこを超えると精度が落ちるのは明らかとして、そこまではOKなのかは実装次第だが、たぶん普通はOK。
出現する整数が高々4000種類しかないので、4000個のcompact bit vectorを持ってすべてのクエリに対して累積和で計算する、みたいなムーブを最初にやってしまった。（部分点は取れる。） 結局、バケット法+bitset高速化をした。
簡単のために、数列$a$と$b$の長さは両方$N$とする。$a$と$b$を長さ$B$毎に区切って$k := N/B$個の区間に分解し、さらにそれぞれの区間に対して長さ$4000$のビット配列を保持する。このビット配列を$\alpha_1, ..., \alpha_k, \beta_1, ..., \beta_k$とする。それぞれの区間について、出現する整数の奇遇を数えて
$$ \alpha_i[x] := \begin{cases} 1 \qquad (整数xが区間内に奇数個ある場合) \\ 0 \qquad (整数xが区間内に偶数個ある場合) \end{cases} $$としておく。（$\beta_i$も同様）
各クエリの指定区間に含まれるバケット$\alpha_i, \beta_i$のXORを取って、端の部分は愚直に数えれば、立っているビットの数が答えになる。出現する値の最大値を$A$とすると、計算量は${O}(Q((N/B)\cdot(A/\log A) + B))$。$B= \Theta(\sqrt{NA/\log A})$なら${O}(Q\sqrt{NA/\log A)}$。（$/ \log A$の部分はいわゆるbitset高速化）
コンテスト中は深く考えずに$B=200$としたのだけど、計算量を見ると$\sqrt N$よりは大きいほうがよさそうだったので$B=1000$としてみたら遅くなった。なにか勘違いしてるかも。
tmwilliamlinさんの提出を見たら、単純なbitsetの累積和で処理していた。それはそうだった…… ${\mathcal O}((N+Q)A/ \log A)$。
Egorさんは出現する整数のほうを下位5ビットごとに分割して、bitsetなしで通している。
$x$枚目まで見たときに総和が$y$以上になるようなカードの集合の総数を$dp[x][y]$とすると、漸化式は
$$ \operatorname{dp}[x][y] = \operatorname{dp}[x-1][y] + \operatorname{dp}[x-1][y-a_{x}] $$となる。ここで、$N$番目のカードと$i$番目のカードを入れ替えて同じDPをしたものを$\operatorname{dp}_i$とする。$\operatorname{dp}_i$についても同じ漸化式が成立し
$$ \operatorname{dp}_i[N][y] = \operatorname{dp}_i[N-1][y] + \operatorname{dp}_i[N-1][y-a_i] $$順番を入れ替えても$N$枚処理すれば同じ結果になるはずだから$\operatorname{dp}[N][y] = \operatorname{dp}_i[N][y]$が成り立つ。したがって
$$ \operatorname{dp}[N][y] = \operatorname{dp}_i[N-1][y] + \operatorname{dp}_i[N-1][y-a_i] $$整理して
$$ \operatorname{dp}_i[N-1][y] = \operatorname{dp}[N][y] - \operatorname{dp}_i[N-1][y-a_i] $$という漸化式が立つ。$i$番目のカードを除いたとき和が$y$以上になるような集合の総数を$f[i][y]$とすると$f[i][y] = \operatorname{dp}_i[N-1][y]$だから
$$ f[i][y] = \operatorname{dp}[N][y] - f[i][y-a_i] $$$\operatorname{dp}$を求めた後、さらに$f$についてDPできる。
カード$i$が不必要
$\Leftrightarrow$ カード$i$を含む和が$K$以上になるような集合と、カード$i$を含まない和が$K$以上になるような集合が一対一対応する
$\Leftrightarrow f[i][K] = \operatorname{dp}[N][K] - f[i][K]$
だから、この等式が成立するような$i$を数えればよい。
$\operatorname{dp}$の値は64ビットに収まらないので、適当にmodをとって扱う。弱衝突耐性があれば十分なので32ビットでよさそう。だめなら複数modを組み合わせればよい。
戻すDPを覚えるために復習。
とりあえず「簡単すぎる」ほうの問題を解く。$\mathrm{dp}[x][y] :=$商品を最初の$x$種類からちょうど$y$個選ぶ方法の総数、とする。$\mathrm{dp}[x][y] = d[x-1][y] + \mathrm{dp}[x-1][y-1] + ... + \mathrm{dp}[x-1][y-a_{x}]$と遷移できるが、これでは間に合わないので累積和を考える。つまり$\mathrm{DP}[x][y] :=$商品を最初の$x$種類から$y$個以下選ぶ方法の総数としたとき、
$$ \mathrm{DP}[x][y] = \mathrm{dp}[x][0]+ \mathrm{dp}[x][1] + ... + \mathrm{dp}[x][y] $$ $$ \mathrm{DP}[x][y] = \mathrm{DP}[x][y-1] + \mathrm{dp}[x][y] $$ $$ \mathrm{dp}[x][y] = \mathrm{DP}[x-1][y] - \mathrm{DP}[x-1][y-a_x-1] $$が成り立つので、
$$ \mathrm{DP}[x][y] = \mathrm{DP}[x][y-1] + \mathrm{DP}[x-1][y] - \mathrm{DP}[x-1][y-a_x-1] $$という${O}(1)$の遷移を導ける。ここから$y$を一個ずらした漸化式$\mathrm{DP}[x][y-1] = \mathrm{DP}[x][y-2] + \mathrm{DP}[x-1][y-1] - \mathrm{DP}[x-1][y-a_x-2]$を引くと、$\mathrm{dp}$についても同じ形の漸化式が得られる:
$$ \mathrm{dp}[x][y] = \mathrm{dp}[x][y-1] + \mathrm{dp}[x-1][y] - \mathrm{dp}[x-1][y-a_x-1] $$これで簡単なほうの問題が解けた。
さて、ここで$N$番目の商品と$i$番目の商品を入れ替えて同じDPをすることを考える。この配列を$\mathrm{dp}_i$とするとき、$\mathrm{dp}_i$は$\mathrm{dp}$と同じ遷移で求まり、しかも$N$種類の商品を処理すると同じ値になるはずである。つまり、任意の個数$y$について$\mathrm{dp}[N][y] = \mathrm{dp}_i[N][y]$が成り立つ。したがって
$$ \mathrm{dp}_i[N][y] = \mathrm{dp}_i[N][y-1] + \mathrm{dp}_i[N-1][y] - \mathrm{dp}_i[N-1][y-a_i-1] $$という等式から
$$ \mathrm{dp}[N][y] = \mathrm{dp}[N][y-1] + \mathrm{dp}_i[N-1][y] - \mathrm{dp}_i[N-1][y-a_i-1] $$が導け、整理すると
$$ \mathrm{dp}_i[N-1][y] = \mathrm{dp}[N][y] - \mathrm{dp}[N][y-1] + \mathrm{dp}_i[N-1][y-a_i-1] $$となる。$i$番目の商品を除いた場合に全体でちょうど$y$個の商品を選ぶ方法の総数を$f[i][y]$とするとき、$f[i][y] = \mathrm{dp}_i[N-1][y]$であるから、
$$ f[i][y] = \mathrm{dp}[N][y] - \mathrm{dp}[N][y-1] + f[i][y-a_i-1] $$となり、$f$についてDPすればクエリに${O}(1)$で答えられることになる。${O}(NM + Q)$。
戻すDPというらしい。