Problem Miguel și Baza 2


Cerința

Miguel a învățat cum să scrie numere în baza 2 și cum merg operațiile pe biți, așa că a inventat următorul joc:

Ai primit un șir de \(N\) numere \(v_1\), \(v_2\), ..., \(v_n\) și \(Q\) interogări. Pentru fiecare interogare, ai la dispoziție două numere naturale \(A\) și \(B\) cu semnificația că \(v_A\) devine egal cu \(B\). După fiecare interogare, trebuie să afișezi numărul magic corespunzător noului șir. De menționat că după afișarea numărului magic, șirul nu revine la starea inițială.

Numărul magic al unui șir \(V\) de lungime \(N\) este egal cu suma tuturor numerelor din șirurile \(a_1\), \(a_2\), ..., \(a_n\). Pentru \(i=1\), \(a_i\) este egal cu \(V\) iar pentru fiecare \(i \gt 1\), \(a_i\) conține rezultatele operației pe biți AND între oricare două numere consecutive din \(a_{i-1}\), păstrând ordinea relativă a perechilor. De menționat că șirul \(a_i\) conține \(N-i+1\) elemente.

De exemplu, dacă \(V=\{1,3,5,7\}\), atunci \(a_1=\{1,3,5,7\}, a_2=\{1,1,5\}, a_3=\{1,1\}, a_4=\{1\} \) iar numărul magic al lui \(V\) este egal cu \((1+3+5+7)+(1+1+5)+(1+1)+(1)=26\).

Date de intrare

De pe prima linie se citesc numerele naturale \(N\) și \(Q\). A doua linie conține \(N\) numere întregi \(v_1\), \(v_2\), ..., \(v_n\). Pe următoarele \(Q\) linii se află câte o interogare, de forma A B.

Date de ieșire

Se vor afișa cele \(Q\) numere magice, dispuse pe câte o linie.

Restricții și Precizări

  • \(1 \leq N, Q \leq 100.000\)
  • \(0 \leq a_i \leq 100.000\) pentru oricare \(1 \leq i \leq N\)
  • \(0 \leq B \leq 100.000\)
  • \(1 \leq A \leq N\)

Exemplu

stdin

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

stdout

35
31
24
32

Explicație

După prima interogare, șirul devine \(1,5,3,7,3\) iar numărul magic este egal cu \((1+5+3+7+3)+(1+1+3+3)+(1+1+3)+(1+1)+(1)=35\). Pentru a obține \(a_2\) vom efectua următoarele operații: \(1\&5\), \(5\&3\), \(3\&7\), \(7\&3\).

General info

ID: 74

Upload: AlexVasiluta

Input: Console Input

Memory limit: 64MB/16MB

Time limit: 2s

Author: Popa Sebastian

Source: Miguel's Summer Challenge

Submissions

Special Submissions