Problem #238

Sumex

Time limit: 0.9s
Memory limit: 256MB
Input: stdin
Output: stdout

Se dă un șir \(a_1, \ldots, a_n\) și \(q\) query-uri independente. În cadrul fiecărui query, se dau 2 numere naturale \(l\) și \(r\). Se consideră secvența \(a_l, a_{l+1}, \ldots, a_{r}\). Sarcina ta este să calculezi suma celor mai mici numere excluse ale tuturor secvențelor de forma \(a_{i}, a_{i+1}, \ldots, a_{j}\), pentru \(l \leq i \leq j \leq r\).

Cel mai mic număr exclus al unei secvențe este cel mai mic număr natural care nu apare în secvență. De exemplu, pentru secvența \(0, 1, 4, 2\) acesta este \(3\), dar pentru secvența \(1, 2, 3, 4\) acesta este \(0\).

Date de intrare

Prima linie din input conține numerele \(n\) și \(q\). A doua linie conține \(n\) numere \(a_1, a_2, \dots, a_n\), care reprezintă șirul inițial. Fiecare dintre următoarele \(q\) linii conține două numere \(l\) și \(r\), care descriu, în ordine, fiecare query.

Date de ieșire

Output-ul trebuie să conțină răspunsurile celor \(q\) query-uri în ordine, fiecare pe câte un rând nou.

Restricții

  • \(1 \leq n, q \leq 2 \cdot 10^5\)
  • \(0 \leq a_i \leq n\)
  • \(1 \leq l \leq r \leq n\)

Subtask 1 (3 puncte)

  • \(1 \leq a_i \leq n\)

Subtask 2 (10 puncte)

  • \(1 \leq q \leq 200\)
  • \(r - l \leq 200\) pentru fiecare query

Subtask 3 (12 puncte)

  • \(1 \leq n \leq 5 \ 000\)

Subtask 4 (15 puncte)

  • Fiecare număr de la \(0\) la \(n - 1\) apare exact o dată în \(a_1, a_2 \dots, a_n\).

Subtask 5 (15 puncte)

  • \(0 \leq a_i \leq 100\)
  • Nu există două query-uri \(i\) și \(j\) astfel încât \(l_i < l_j\) și \(r_j < r_i\).

Subtask 6 (22 puncte)

  • \(l = 1\) pentru fiecare query.

Subtask 7 (23 puncte)

  • Fără restricții suplimentare.

Exemplu

stdin

6 3
0 1 2 0 1 3
1 2
3 5
1 6

stdout

3
7
39

Explicații

Explicații pentru primele două query-uri:



Explicație pentru al treilea query:

General info

Uploader: Matteo.Verz

Author: Matteo Verzotti, Alexandru Luchianov

Source: infO(1) Cup 2022, Day 1

Submissions