Optymalizacja kodu: Policzenie XOR na podanym przedziale

**Oto treść zadania: **
Jankowi, dzięki intensywnym przygotowaniom, udało się dostać do finału OMJ. Oczywiście jako finalista Olimpiady umie już dodawać, więc w ramach przygotowań do finału wymyślił sobie nowe ćwiczenie: zapisuje na
kartce n liczb, a następnie wybiera dwie liczby całkowite a, b i oblicza XOR wszystkich zapisanych liczb od a-tej
do b-tej włącznie.
Niestety, finał OMJ został odwołany, więc Janek nie będzie miał możliwości sprawdzenia swoich umiejętności
na zawodach. Pomóż mu i napisz program obliczający poprawne odpowiedzi.
WEJŚCIE
W pierwszym wierszu wejścia znajdują się dwie liczby całkowite n i q (1 ¬ n, q ¬ 106
) oznaczające odpowiednio
ile liczb zapisał Janek na kartce i ile pytań chce zadać.
W drugim wierszu znajduje się n liczb całkowitych z przedziału h0, 106
i – liczby zapisane przez Janka na kartce.
W każdym z następnych q wierszy znajdują się dwie liczby całkowite a i b (1 ¬ a ¬ b ¬ n), które oznaczają
odpowiednio numer pierwszej i ostatniej liczby przedziału, na którym należy policzyć XOR.
WYJŚCIE
Należy wypisać odpowiedzi na kolejne pytania Janka, każde w oddzielnej linii.
PRZYKŁAD
Wejście:
6 2
31 13 16 21 0 1
1 6
2 5
Wyjście:
22
8

Oto mój kod, który otrzymuje 40 punktów:

#include <iostream>
using namespace std;

int main() {
	int n, m;
	cin >> n >> m;
	int t[n];
	for(int i = 0; i < n; i++){
		cin >> t[i];
	}
	int sp[n];
	sp[0] = t[0];
	for(int i = 1; i < n; i++){
		sp[i] = sp[i - 1] ^ t[i];
	}
	int a, b;
	while(m--){
		cin >> a >> b;
		if(a == 1){
			cout << sp[b-1] << endl;
		}
		else {
			cout << (sp[b-1] ^ sp[a-2]) << endl;
		}
	}
}

Przekroczony został limit czasu. Czy ktoś pomógłby mi zoptymalizować kod?

Na pewno każdy pomoże kiedy w kodzie masz a, b i sp które nikomu nic nie mówią. Kod pisze się dla ludzi, do czytania :)

1. Nie uzywaj cin/cout albo użyj jakiegoś sync with stdio, bo inaczej 90% czasu programu zejdzie ci na wczytanie i wypisanie danych. Zgaduje ze zmiana na scanf/printf wystarczy zebyś dostał max punktów.
2. Wracając do wyjsciowego pytania, myśle że tirk polega na tym ze a^b^c == (a^b)^c, więc na oko zrobiłeś to dobrze generujac sobie tablicę "prefixów". Szybiciej niz liniowo to nie pójdzie. Mógłbyś ewentalnie generować tablicę prefixów od razu kiedy czytasz kolejne t[i] bo na dobrą sprawę ta tablica t w ogóle ci nie potrzebna do niczego. Wtedy masz tylko jedną zamiast dwóch pętli.

Problem pierwszy, to zdanie ma dość duże dane wejściowe, ergo musisz optymalnie czytać i wypisywać dane.
W tej chwili ciągle opóźniasz bufor zapisu co strasznie spowalnia program.
Poprawki optymalizujące twój kod pod tym kątem (innych rzeczy nie poprawiam):

#include <iostream>

using namespace std;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    int t[n];
    for(int i = 0; i < n; i++){
        cin >> t[i];
    }
    int sp[n];
    sp[0] = t[0];
    for(int i = 1; i < n; i++){
        sp[i] = sp[i - 1] ^ t[i];
    }
    int a, b;
    while(m--){
        cin >> a >> b;
        if(a == 1){
            cout << sp[b-1] << '\n';
        }
        else {
            cout << (sp[b-1] ^ sp[a-2]) << '\n';
        }
    }
}

Generalnie

• rozsynchronizuj strumienie C++ z stdin stdout pochodzące z C - std::ios::sync_with_stdio(false);
• rozłącz std::cin i std::cout (odczyt na std::cin wymusza opróżnienie bufora na std::cout) - std::cin.tie(nullptr);
• nie używaj endl (to też wymusza opróżnienie bufora)

Drugi problem, to groźba przepełnienia stosu i używanie rozszerzenia do C++ (nie ma tego w standardzie) pochodzące z C99 Variable Length Array (VLA).
Zmień to na std::vector.

@Michał F: Niestety mimo zmian w dalszym ciągu 40 pkt :/

znalazłem to zadanko https://sio2.mimuw.edu.pl/c/zwo21/p/omj/
Użyj enigmatycznej struktury, uwielbianej przez wszystkich początkujących algorytmików i osób tworzących zadania do OI i OIJ, zwanej drzewo przedziałowe. Musisz znać teorię robiąc zadania z OIJ. Przekroczenie limitu czasu dostajesz prawdopodobnie przez brak std::ios::sync_with_stdio(false);. Złożoność n+q*log(n) w zupełności wystarczy.
Tutaj dobry poradnik dla drzew przedziałowych od OKI.
Jeśli chcesz na poważnie zająć się Olimpiadami i konkursami to bardzo polecam ci OKI.

EDIT:
Przepraszam za błąd. Oczywiście najlepsze w tym wypadku będą sumy prefiksowe, używanie drzewa przedziałowego miałoby sens tylko gdyby wartości się zmieniały.

Моże drobna uwaga:
XOR liczb od 5000000 do 10000000 - ostatni bit będzie 1 ponieważ ilość liczb jest nieparzysta więc ostatni bit to (abs(b-a)+1)&1
Prędkość obliczenia około miliona razy większa niż xorowanie kilku milionów liczb.

UWAGA: Oczywiście dla drugiego (oraz pozostałych) bita sprawa będzie bardziej skomplikowana.

EDIT:
Może bardziej precyzyjna uwaga:
Dla obliczenia N-tego bitu można bez problemu pominąć X*(1<<N) ostatnich XOR'ów

_13th_Dragon napisał(a):

Моże drobna uwaga:

XOR liczb od 5000000 do 10000000 - ostatni bit będzie 1 ponieważ ilość liczb jest nieparzysta więc ostatni bit to (abs(b-a)+1)&1
Prędkość obliczenia około miliona razy większa niż xorowanie kilku milionów liczb.

Eeee. to raczej nie zadziała (w sensie nie pasuje do zadania), bo w zadaniu nie mamy ciągu arytmetycznego tylko dowolny ciąg podawany w całości na wejściu (tzn. element po elemencie).

Po zrozumieniu treści zadania (dzięki @Wibowit):

#include <algorithm>
#include <iostream>
#include <iterator>
#include <sstream>
#include <vector>
using namespace std;

int main()
{
	//*///
	istream_iterator<int> iin(cin);
	/*/
	stringstream sin("6 2\n31 13 16 21 0 1\n1 6\n2 5\n");
	istream_iterator<int> iin(sin);
	//*///
	int size=*(iin++),tests=*(iin++);	
	vector<int> values(size+1);
	copy_n(iin,size,begin(values)+1);
	for(int part=0,i=1;i<=size;++i) values[i]^=values[i-1];
	for(int t=0;t<tests;++t) cout<<(values[*(++iin)-1]^values[*(++iin)])<<endl;
	return 0;
}

pro tip: wczytywanie można połączyć z xorowaniem :)
mniej więcej tak:

vector<int> values(n + 1);
values[0] = 0;
for (int i = 1; i <= n; i++) {
  int value;
  cin >> value;
  values[i] = values[i - 1] ^ value;
}

Wtedy mamy jeden przebieg i jesteśmy szybsi o 0.01%. /s

Hej wszystkim! Dzięki wielkie za pomoc ale ehh ... okazało się że testy były złe i jednak wchodzi na 100. Jeszcze raz dzięki wszystkim