Sheikh (Easy version)

Pista 1

¿Cuál es el valor máximo de $f(l, r) = \operatorname{sum}(l, r) - \operatorname{xor}(l, r)$ ?

Pista 1 (respuesta)

Observemos que, como el XOR de dos números nunca puede crecer más que su suma, agregar otro número a nuestro rango nunca puede empeorar la respuesta.

Así, el valor máximo de $f(l, r)$ es $f(1, n)$ . ¡Ahora hemos reducido el problema a hallar el subsegmento de longitud mínima que alcanza este máximo!

Solución

Explicación

A partir de la pista, ahora solo tenemos que hallar el subsegmento de longitud mínima que alcanza el valor máximo de $f(l, r)$ .

Recordemos que, como el XOR de dos números nunca puede crecer más que su suma, incluir elementos extra nunca empeorará la respuesta. Por lo tanto, nuestra longitud es de hecho monótonamente creciente^{Si $x$ funciona, entonces $x + 1$ siempre funcionará.}!

Ahora, simplemente podemos hacer búsqueda binaria sobre la longitud y comprobar si existe un subsegmento de esa longitud cuyo costo sea igual a $f(1, n)$ . Lamentablemente, esto sigue siendo demasiado lento porque calcular los costos toma tiempo lineal.

Para arreglarlo, necesitamos algún método de calcular sumas de rango y XOR de rango en tiempo constante. ¡Aquí entran las sumas de prefijos y los XOR de prefijos! Como XOR y la adición son asociativos y tienen elementos identidad , ¡podemos usar el mismo concepto con ellos! Si hacemos $p_i = a_1 \oplus a_2 \oplus \dots \oplus a_i$ , entonces podemos calcular el XOR del rango $[l, r]$ como $p_r \oplus p_{l - 1}$ .

Implementación

Complejidad temporal: $\mathcal{O}(N \log N)$

C++JavaPython


#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
 
int main() {
	int tc;
	cin >> tc;
 
	for (int _ = 0; _ < tc; _++) {
		int n, q;
		cin >> n >> q;
		vector<ll> pref_sum(n + 1);
		vector<ll> pref_xor(n + 1);
 
		auto cost = [&](int l, int r) {
			return (pref_sum[r] - pref_sum[l - 1]) - (pref_xor[r] ^ pref_xor[l - 1]);
		};
 
		for (int i = 0; i < n; i++) {
			int x;
			cin >> x;
 
			pref_sum[i + 1] = x + pref_sum[i];
			pref_xor[i + 1] = x ^ pref_xor[i];
		}
 
		int L, R;
		cin >> L >> R;
 
		// búsqueda binaria sobre la longitud
		ll best_cost = cost(1, n);
 
		int lo = 1, hi = n;
		while (lo < hi) {
			int mid = lo + (hi - lo) / 2;
			bool possible = 0;
 
			for (int i = 1; i + mid - 1 <= n; i++) {
				// si este segmento tiene el costo más óptimo
				if (cost(i, i + mid - 1) == best_cost) {
					possible = 1;
					break;
				}
			}
 
			if (possible) {
				hi = mid;
			} else {
				lo = mid + 1;
			}
		}
 
		for (int i = 1; i + lo - 1 <= n; i++) {
			// este fue el segmento que encontramos
			if (cost(i, i + lo - 1) == best_cost) {
				cout << i << ' ' << i + lo - 1 << endl;
				break;
			}
		}
	}
}


import java.io.*;
import java.util.*;
 
public class Sheikh {
	public static void main(String[] args) {
		Kattio io = new Kattio();
		int tc = io.nextInt();
		for (int t = 0; t < tc; t++) {
			int n = io.nextInt();
			int q = io.nextInt();
			long[] prefSum = new long[n + 1];
			long[] prefXor = new long[n + 1];
 
			for (int i = 0; i < n; i++) {
				int x = io.nextInt();
				prefSum[i + 1] = x + prefSum[i];
				prefXor[i + 1] = x ^ prefXor[i];
			}
 
			int L = io.nextInt();
			int R = io.nextInt();
 
			long bestCost = cost(1, n, prefSum, prefXor);
 
			// búsqueda binaria sobre la longitud
			int lo = 1, hi = n;
			while (lo < hi) {
				int mid = lo + (hi - lo) / 2;
				boolean possible = false;
 
				for (int i = 1; i + mid - 1 <= n; i++) {
					// si este segmento tiene el costo más óptimo
					if (cost(i, i + mid - 1, prefSum, prefXor) == bestCost) {
						possible = true;
						break;
					}
				}
 
				if (possible) {
					hi = mid;
				} else {
					lo = mid + 1;
				}
			}
 
			for (int i = 1; i + lo - 1 <= n; i++) {
				if (cost(i, i + lo - 1, prefSum, prefXor) == bestCost) {
					System.out.println(i + " " + (i + lo - 1));
					break;
				}
			}
		}
	}
 
	private static long cost(int l, int r, long[] prefSum, long[] prefXor) {
		return (prefSum[r] - prefSum[l - 1]) - (prefXor[r] ^ prefXor[l - 1]);
	}
 
	// CodeSnip{Kattio}
}


for _ in range(int(input())):
	n, q = map(int, input().split())
 
	pref_sum = [0] * (n + 1)
	pref_xor = [0] * (n + 1)
 
	cost = lambda l, r: (pref_sum[r] - pref_sum[l - 1]) - (
		pref_xor[r] ^ pref_xor[l - 1]
	)
 
	a = list(map(int, input().split()))
	for i in range(n):
		pref_sum[i + 1] = a[i] + pref_sum[i]
		pref_xor[i + 1] = a[i] ^ pref_xor[i]
 
	_, _ = map(int, input().split())
 
	# búsqueda binaria sobre la longitud
	best_cost = cost(1, n)
 
	lo = 1
	hi = n
 
	while lo < hi:
		mid = lo + (hi - lo) // 2
		possible = False
 
		for i in range(1, n - mid + 2):
			# si este segmento tiene el costo más óptimo
			if cost(i, i + mid - 1) == best_cost:
				possible = True
				break
 
		if possible:
			hi = mid
		else:
			lo = mid + 1
 
	for i in range(1, n - lo + 2):
		# este fue el segmento que encontramos
		if cost(i, i + lo - 1) == best_cost:
			print(i, i + lo - 1)
			break