spotify

Cerință

Ai o listă de $N$ melodii pe Spotify (deși probabil ar trebui să folosești YouTube Music... ). De vreme ce foamea este mare, cei de la Spotify au decis să adauge reclame înainte și după fiecare melodie. Mai precis, vei avea $A_{i}$ secunde de reclame după melodia $i$, respectiv $B_{i}$ secunde de reclame înainte de melodia $i$.

Ai descoperit că, dacă asculți piesele în playlist-uri, aplicația Spotify are bug-uri și ajungi să primești mai puține reclame (bineînțeles că e un bug, doar nu te gandeai că ar face asta pentru ca sunt ei prea drăguți, nu???). Mai exact, dacă formezi un playlist din melodiile $i_0, i_1, \dots, i_{k-1}$, vei primi $min(A_{i_0}, B_{i_1}) + min(A_{i_1}, B_{i_2}) + \dots + min(A_{i_{k-2}}, B_{i_{k-1}}) + min(A_{i_{k-1}}, B_{i_0})$ secunde de reclame.

Acum, tu vrei să împarți cele $N$ melodi în playlist-uri astfel încât numărul total de secunde în care asculți reclame să fie cât mai mic. A se nota că poți asculta melodiile în ce ordine vrei.

De vreme ce ești destul de șomer, ai decis să rezolvi această problemă pentru $Q$ scenarii de forma $(l, r)$ - dacă consider doar melodiile $l, l+1, \dots, r$, care este numărul minim de secunde pe care le voi petrece ascultând reclame?

Această problemă trebuie rezolvată online, prin urmare, scenariile trebuie rezolvate în ordine. Mai exact, veți primi un parametru numit $state$ (acesta fiind un seed), iar query-urile se vor genera de concurenți folosind următoarea clasă.

#include <cstdint>
#include <utility>
#include <algorithm>

class QueryGenerator {
public:
  QueryGenerator(int N, uint64_t seed) 
    : N(N), state(seed) {}

  inline std::pair<int, int> next_query(int64_t last_answer) {
    state ^= (uint64_t)last_answer + 0x9e3779b97f4a7c15ULL + (state << 6) + (state >> 2);
    auto l = split_mix_64(state) % N;
    auto r = split_mix_64(state) % N;
    return {std::min(l, r), std::max(l, r)};
  }

private:
  uint64_t split_mix_64(uint64_t &x) {
    uint64_t z = (x += 0x9e3779b97f4a7c15ULL);
    z = (z ^ (z >> 30)) * 0xbf58476d1ce4e5b9ULL;
    z = (z ^ (z >> 27)) * 0x94d049bb133111ebULL;
    return z ^ (z >> 31);
  }

  int N;
  uint64_t state;
};

Un exemplu de cum trebuie folosită această clasă:

uint64_t state;
std::cin >> state;
QueryGenerator generator(N, state);

int64_t last_answer = 0;
for (int q = 0; q < Q; q++) {
  const auto query = generator.next_query(last_answer);
  answer = solve(query.first, query.second);
  std::cout << answer << "\n";
  last_answer = answer;
}

În caz că doriți să vedeți un exemplu mai detaliat, aveți la atașamentele problemei (în dreapta) încă un exemplu de folosire.

Date de intrare

Pe prima linie se găsesc două numere naturale, $N$ și $Q$. Pe a doua linie se găsesc $N$ numere naturale separate prin spații, reprezentând șirul $A$. Pe a treia linie este descris in mod analog șirul $B$.

Pe ultima linie se găsește numărul $state$, indicât parametrul de stare al clasei de generare a query-urilor.

Date de ieșire

Se vor afișa $Q$ numere, al $i$-lea dintre ele fiind răspunsul pentru cel de al $i$-lea scenariu, în ordinea în care acestea apar în fișierul de intrare.

Restricții și precizări

• $1 \leq N \leq 2 \cdot 10^5$.
• $1 \leq Q \leq 5 \cdot 10^5$.
• Parametrul $state$ se încadrează pe 64 de biți fără semn (uint64_t / unsigned long long).
• Valorile $l$ și $r$ vor fi în intervalul $[0, N - 1]$.
• $0 \leq A_{i}, B_{i} \leq 10^9$.
• Pentru teste în valoare de 7 puncte, $N, Q \leq 5$.
• Pentru teste în valoare de alte 6 puncte, $A_{i}, B_{i} \leq 1$.
• Pentru teste în valoare de alte 14 puncte, $Q = 1, N \leq 100$.
• Pentru teste în valoare de alte 19 puncte, $N \leq 100$.
• Pentru teste în valoare de alte $15$ puncte, $Q = 1$.
• Pentru teste în valoare de alte $20$ de puncte, $1 \leq N, Q \leq 5 \cdot 10^4$.

Exemplul 1

stdin

3 3
1 4 7
2 6 3 
37835487345

stdout

3
7
3

Query-urile care sunt generate sunt $(0, 1)$, $(1, 2)$, $(0, 1)$.
Pentru primul query, vom forma playlist-ul $(0, 1)$ -» $(min(A_0, B_1) + min(A_1, B_0)) = min(1, 6) + min(4, 2) = 1 + 2 = 3$.
Pentru al doilea query, vom forma două playlist-uri: $(1)$ și $(2)$ -» $min(A_1, B_1) + min(A_2, B_2) = min(4, 6) + min(3, 7) = 4 + 3 = 7$.