メモ

この問題のスコア順位はこちらをご覧ください。 https://yukicoder.me/problems/no/5011/score

この問題は、Advent Calendar Contest 2022 17日目の 問題2 です。
難易度は、Advent Calendar Contest 用に付けられたものです。正当な出力を行うことが出来ればコンテストで得点を獲得できます。

ルール

Advent Calendar Contest 2022 17日目 (Better Mo's Algorithm is Needed!!) は、2つの問題からなります。

• 問題1: Better Mo's Algorithm is Needed!! (Unweighted)
• 問題2: Better Mo's Algorithm is Needed!! (Weighted)

• $2 \le WT \le 5$ です。
• $W$ は $4$ 種の方法で生成され、各生成法に対してテストケースが $30$ 個存在します。
• 全てのテストケースについて、 $W$ の期待値は約 $50$ です。
• 問題1 の $W$ は全要素が $100$ で固定です。そのため、 問題2 は 問題1 の $2$ 倍かそれ以上のスコアを期待することができます。

• (問題1の得点) + (問題2の得点) の合計が高い方が上位である。
• ここまでで順序がつかなければ、同順位とする。

• 解法に直接かかわらない部分(ローカルテストの方法等)について、議論や相談を認めます。
• ビジュアライザを有志で作成し公開するなどしても構いません。
• さらに、自身の解法を直接言及することも、コードを共有することも認めます。
• ただし、そのことによって他の方が解を改良した場合、その得点は改良したコードの提出者のものとなります。

問題文

重み $W=(W_1,W_2,\dots,W_N)$ が長さ $N$ の数列として与えられる。
また、 $1 \le L_i \le R_i \le N$ を満たす区間 $[L_i,R_i]$ が $Q$ 個与えられる。
この問題の目的は、 $(1,2,\dots,Q)$ の順列である $P=(P_1,P_2,\dots,P_Q)$ を適切に定め、以下で定義する実行時間 $T$ を最小化することである。

実行時間 $T$ は、以下のように定義される。

• まず、 $\displaystyle T=\sum^{R_{P_1}}_{k = L_{P_1}} W_k$ とする。
• 次に、 $i=1,2,\dots,Q-1$ に対して、以下を行う。
• $[a,b]=[L_{P_i},R_{P_i}],[c,d]=[L_{P_{i+1}},R_{P_{i+1}}]$ とする。
• $\alpha = \min(a,c), \beta = \max(a,c)$ とし、 $T$ に $\displaystyle \sum^{\beta-1}_{k=\alpha} W_k$ を加算する。 $a=c$ であるとき加算される値は $0$ である。
• $\gamma = \min(b,d), \delta = \max(b,d)$ とし、 $T$ に $\displaystyle \sum^{\delta}_{k=\gamma+1} W_k$ を加算する。 $b=d$ であるとき加算される値は $0$ である。

得点

この問題にはテストケースが 120 個存在します。
各テストケースに対する得点は $\min \left( \rm{round} \displaystyle \left( \frac{10^{18}}{T} \right) , 10^{16} \right)$ です。
この問題に対する最終的な得点は、全てのテストケースの得点の総和です。

入力

$N$ $Q$ $WT$ $ST$
$W_1$ $W_2$ $\dots$ $W_N$
$L_1$ $R_1$
$L_2$ $R_2$
$\vdots$
$L_Q$ $R_Q$

制約

• 入力は全て整数
• $N = 200000$
• $Q = 200000$
• $\color{red}{2 \le WT \le 5}$
• $1 \le ST \le 3$
• $\color{red}{1 \le W_i \le 998244353}$
• $1 \le L_i \le R_i \le N$

出力

順列 $P$ を以下の形式で出力せよ。

$P_1$ $P_2$ $\dots$ $P_Q$

入力生成方法

$l$ 以上 $r$ 以下の整数を返す一様乱数を $\rm{rnd}$$(l,r)$ と書きます。
$l$ 以上 $r$ 未満の実数を返す一様乱数を $\rm{Rernd}$$(l,r)$ と書きます。
$N=200000,Q=200000$ は固定です。
この問題では、 $2 \le WT \le 5$ です。テストケースには各 $WT$ が同数含まれます。
各 $WT$ について、 $W$ の生成法は以下です。
$WT=2$ ... $W_i =$ $\rm{rnd}$$(1,99)$ で生成されます。
$WT=3$ ... 各 $W_i$ について、 99% の確率で $W_i=40$ 、 1% の確率で $W_i=1040$ となります。
$WT=4$ ... 偏角 $\alpha = \rm{Rernd}$$(0,2\pi)$ を決め、 $W_i=$ $\rm{round}$$\left ( 50+49 \cos(\alpha + \frac{2 \pi i}{N}) \right )$ とします。
$WT=5$ ...
最初 $w=25$ から始め、以下で定める $n$ が正である限り以下の手順を繰り返します。
$W$ のうち今まで選出されたことがない要素の数を $n$ とし、その $n$ 要素の中から $\left \lceil \frac{3n}{4} \right \rceil$ 要素を一様ランダムに選出し、 $W_i=w$ とする。
その後、 $w$ を $2$ 倍する。
また、 $ST$ は $1,2,3$ いずれかの値を取ります。テストケースには各 $ST$ が同数含まれます。
$ST=1$ であるとき、区間 $[L_i,R_i]$ は必ず 方法1 によって生成されます。
$ST=2$ であるとき、区間 $[L_i,R_i]$ は必ず 方法2 によって生成されます。
$ST=3$ であるとき、区間 $[L_i,R_i]$ は 方法1 と 方法2 のどちらかが等確率で区間ごとに独立に選択され、その方法で生成されます。

方法1:

• $x=$ $\rm{rnd}$$(1,N),y=$ $\rm{rnd}$$(1,N)$ で生成する。
• もし $x>y$ なら $x,y$ を交換する。
• 生成される区間は $[x,y]$ である。

• $l=$ $\rm{rnd}$$(1,N)$ で生成する。
• $x=$ $\rm{rnd}$$(1,N-l+1)$ で生成し、 $y=x+l-1$ とする。
• 生成される区間は $[x,y]$ である。

配布物等

こちらから配布物(zip)を入手してください。
この配布物を解答に用いたり、この配布物を他言語に翻訳したものを再配布しても構いません。

サンプル

5 6 1 1
100 200 300 400 500
1 3
4 4
2 5
1 5
3 5
2 4

6 5 4 3 1 2