3. Vystupovanie vzorové riešenie

5 4
3 4 5 4 5
2 3 4 1
3 4 1 2
1 2 4 1
1 2 4 2

2
-1
2
-1

10 5
3 3 1 3 3 2 1 3 3 1
1 5 3 1
1 8 3 1
2 8 3 2
1 4 1 1
1 6 1 2

1
1
4
3
-1

Pomalé riešenie

Ako prvé si predstavíme priamočiare riešenie bez žiadnych trikov. Budeme jednoducho vstupné pole lineárne prehľadávať počnúc od indexu \(l\) a počítať, koľkokrát sme už narazili na zastávku v správnej vzdialenosti \(v\) od Jozefovho domu. Akonáhle narazíme na \(k\)-tu takú, vypíšeme jej index. Ak ale prekonáme index \(r\) pred tým, ako nájdeme odpoveď, odpovieme \(-1\). Toto riešenie by bolo optimálne, v prípade, keby sme dostali len \(q = 1\) otázok. To, že otázok môže byť veľa, nám ale napovedá, že sa asi dá najprv so vstupnými údajmi vykonať nejaká transformácia, ktorá nám potom umožní odpovede zisťovať rýchlejšie ako v lineárnom čase.

Vzorové riešenie

Kľúčový trik k riešeniu úlohy je nasledujúci: Pre každú vzialenosť \(v\) od domu si vytvoríme pole, v ktorom sa nachádzajú čísla (indexy) zastávok, ktoré majú túto vzdialenosť. Napríklad ak je na vstupe pole: \([3, 4, 5, 4, 5]\) tak by sme si vytvorili v pamäti štruktúru podobnú nasledujúcej:

X[3]: 1
X[4]: 2 4
X[5]: 3 5

Na jej uskladnenie môžeme použiť buď hash mapu (dict) alebo jednoduché pole veľkosti \(10^6\), pretože to je maximálna hodnota \(v\).

Všimnime si, že každé pole \(X[v]\) je usporiadané. Teraz vieme na otázky odpovedať nasledujúcim postupom: Pozrieme sa do poľa \(X[v]\) a nájdeme v ňom najmenšiu hodnotu väčšiu alebo rovnú \(l\). Ako na to? Postupné prechádzanie po jednom funguje, ale má zložitosť \(O(n)\), takže si moc nepomôžeme. Zachráni nás ale binárne vyhľadávanie, ktoré to spraví v \(O(\log n)\). Zastávka, ktorú takto nájdeme, je prvá taká, cez ktorú prejde autobus s Jozefom a je v správnej vzdialenosti od jeho domu. My chceme ale \(k\)-tu, nie prvú, takže sa v tomto poli \(X[v]\) pozrieme o \(k-1\) pozícii ďalej a nájdeme presne to, čo hľadáme. Ešte musíme ale vyriešiť dve prekážky: Ak by sme pri tomto procese vybehli z poľa, tak vieme, že taká zastávka neexistuje a odpovieme \(-1\). Druhý problém je \(r\) z otázky, no jednoducho sa stačí pozrieť na číslo zastávky, ktorú sme našli a ak je väčšie ako \(r\), tak opäť vypíšeme \(-1\), pretože zastávka už je mimo Jozefovej platnosti lístka.

Celková časová zložitosť riešenia (s použitím hash mapy) je \(O(n+q\log n)\). \(n\) pochádza z predpočítania štruktúry \(X\) a \(q\log n\) sú jednotlivé odpovede na otázky. Pamäťová zložitosť je \(O(n)\), pretože jediné čo si pamätáme je \(X\), pričom dokopy sa v ňom nachádza presne \(n\) prvkov. Keby sme pre \(X\) nepoužili hash mapu ale pole, zložitosti by boli trochu iné. Museli by sme na začiatku inicializovať pole veľkosti \(10^6\), čo je určite viac ako \(n\), pretože \(n\) dosahuje len \(10^5\). Taktiež si ho musíme pamätať. Ak by sme pomenovali \(w = 10^6\) maximálnu hodnotu \(v\), tak by časová zložitosť bola \(O(w+n+q\log n)\) a pamäťová \(O(w+n)\).

#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

int main() {
    int n, q;
    cin >> n >> q;
    vector<vector<int>> V(1000001);
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        V[x].push_back(i+1);
    }
    for (int i = 0; i < q; i++) {
        int l, r, v, k;
        cin >> l >> r >> v >> k;
        k--;
        int f = upper_bound(V[v].begin(), V[v].end(), l-1) - V[v].begin();
        if (f + k >= V[v].size() || V[v][f+k] > r)
            cout << -1 << '\n';
        else
            cout << V[v][f+k] << '\n';
    }
}

import bisect
from collections import defaultdict

def readints():
    return map(int, input().split())

n, q = readints()
X = list(readints())
# dict, ale ked pristupime k neexistujucemu prvku,
# tak automaticky vyrobi prazdny list
V = defaultdict(list)
for i, x in enumerate(X, 1):
    V[x].append(i)

for _ in range(q):
    l, r, v, k = readints()
    k-=1
    # Binarne vyhladavanie
    f = bisect.bisect(V[v], l-1)
    if f+k >= len(V[v]) or V[v][f+k] > r:
        print(-1)
    else:
        print(V[v][f+k])