3683 - Predictor Machine

Cerinţa

După ce a văzut câti oameni au vrut să știe ce rating vor avea în viitor pe Codeforces, Ștefan s-a decis să își folosească abilitățile sale de programator pentru a găsi punctele importante din graficele ratingurilor de pe Codeforces. Pentru că nu are timp să adauge toate tehnicile sale, el se va ocupa doar de punctele de interes.

Astfel, el primește un vector de n numere, indexat de la 1 și o funcție continuă, astfel încât v[i] = f(i), unde v[i] e ratingul utilizatorului dupa i concursuri. Pentru că funcția e continuă, pentru fiecare linie dintre cele două puncte, graficul funcției va atinge toate punctele de coordonate întregi dintre valori.

De exemplu, daca f(1) = 3 și f(2) = 9, linia va atinge punctele de pe coordonatele întregi 3, 4, 5, 6, 7, 8 și 9.

De asemenea ni se dau q query-uri, unde la un query vom schimba valoarea unui punct din vector și după fiecare query, va trebui să afișăm punctul de interes al vectorului, care este punctul atins de cel mai mare număr de ori de către graficul funcției. De asemenea, trebuie afișat și numărul de ori în care este atins.

Dacă avem mai multe puncte de acest fel, vom afișa punctul cu cea mai mică valoare dintre ele.

Se garantează că cele n valori vor fi distincte atât la început, cât și de-a lungul actualizărilor.

Date de intrare

Programul citește de la tastatură pe prima linie numărul n. Pe următoarea linie, programul va citi cele n numere naturale, reprezentând valorile inițiale ale vectorului v.

Pe linia a treia, programul va citi numărul q, iar pe următoarele q linii, programul va citi câte două numere, pos și val, reprezentând poziția schimbată și valoarea nouă.

Date de ieșire

Programul va afișa pe ecran q linii, pe fiecare din cele q linii regăsindu-se cele două valori cerute de problemă, și anume punctul cu valoare minimă care este atins de numărul maxim de ori, precum și numărul de ori în care este atins.

Restricţii şi precizări

• 1 ≤ pos ≤ n ≤ 100 000
• 1 ≤ q ≤ 200 000
• 1 ≤ v[i], val ≤ 200 000
• Pentru teste în valoare de 30 de puncte, 1 ≤ n, q ≤ 1000

Exemplu

Intrare

5
4 2 6 1 7
5
1 3
4 4
2 1
5 2
3 5

Ieșire

3 4
5 3
5 3
2 3
2 3

Explicație

După ce s-au efectuat toate actualizăriile, vectorul va arăta astfel: 3 1 5 4 2.

Valoarea 2 e atinsă de 3 ori, între pozițiile 1 și 2, între pozițiile 2 și 3 precum și între pozițiile 4 și 5.

Rezolvare

<syntaxhighlight lang="python" line> class SegmentTree:

   def __init__(self, n):
       self.tree = [0] * (4 * n)
   
   def update(self, node, start, end, idx, val):
       if start == end:
           if start == idx:
               self.tree[node] = val
           return
       mid = (start + end) // 2
       if idx <= mid:
           self.update(2 * node, start, mid, idx, val)
       else:
           self.update(2 * node + 1, mid + 1, end, idx, val)
       self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1]
   
   def query(self, node, start, end, left, right):
       if start > right or end < left:
           return 0
       if left <= start and end <= right:
           return self.tree[node]
       mid = (start + end) // 2
       return self.query(2 * node, start, mid, left, right) + self.query(2 * node + 1, mid + 1, end, left, right)

def main():

   n = int(input())
   v = list(map(int, input().split()))
   
   # Construim arborele de segmente
   seg_tree = SegmentTree(n)
   for i in range(n):
       seg_tree.update(1, 1, n, v[i], 1)
   
   q = int(input())
   for _ in range(q):
       pos, val = map(int, input().split())
       # Actualizăm arborele de segmente
       seg_tree.update(1, 1, n, v[pos - 1], 0)
       seg_tree.update(1, 1, n, val, seg_tree.query(1, 1, n, val, val) + 1)
       v[pos - 1] = val
       
       # Căutăm punctul de interes
       left = 1
       right = n
       while left < right:
           mid = (left + right) // 2
           if seg_tree.query(1, 1, n, left, mid) >= seg_tree.query(1, 1, n, mid + 1, right):
               right = mid
           else:
               left = mid + 1
       print(left, seg_tree.query(1, 1, n, left, left))

if __name__ == "__main__":

   main()

</syntaxhighlight>