---
# System prepended metadata

title: Untitled

---

想定解は以下の通りです
A :
  in[i] : 左端がiであるようなchmin処理の値が詰まってる
  out[i] : 右端がiであるようなchmin処理の値が詰まってる
  というのを前処理で用意しておいて左端から走査して今の場所に適用されるchmin処理の値全てをmultisetで管理します。
  inとoutを見てmultisetから出し入れし、*multiset.begin()でその最小値を見ることでその場所に適用されてる最小のchminが求められるので解けます
  O(N + QlogN)
B :
  setかmapに、同じ値をまとめた区間の列を保持します
  区間代入は、setの中で範囲に完全に含まれている区間は消して、端は適当に定数回のinsert/eraseで処理します
  この際、「setの中で範囲に完全に含まれている区間を消」す際に最悪$\Theta(N)$回のeraseをしますがsetへのinsertはO(N + Q)回なのでeraseもO(N + Q)です
  O((N + Q) logN)
C :
  map<int, vector<int> >の変数xを用意します
  各A[i]についてx[A[i]].push_back(i)をします
  するとx[k] : 値がkであるようなインデックスが(昇順に)詰まってる  となります
  するとクエリごとにx[V[i]]の中でL[i],R[i]が入る境界を二分探索することでその差が答えとなります
  O((N + Q) logN)
D :
  定数倍高速化。
  まずpragmaでコンパイルのavx2自動vectorizeを付けます
  Aを64bitにするとTLEするので32bitにして10000回に1回くらい10^9くらいでmodを取って商を別のところに保管しときます(商の方は累積和取っておいてO(1)で区間sumが求まるようにします。)
  想定解は1.9sです(🔥🔥🔥)
  BIT3本とか遅延セグ木とかでO((N + Q)logN)とかでも解けます


Cで非本質TLEたくさん出てたのごめんなさい、一応想定解は400msだったけど入出力が重いのかな...
セグ木はC以外解けるんじゃないかな
平方分割はだいたい全部解けます

