RangreTree1 (Flipping Coin)

Aiuto
1

Dopo aver studiato bene e a fondo il segment tree e le sue applicazioni (lazypropagation) ho cercato di risolvere il problema RangeTree.
Inizialmente ho sfruttato il segment tree per prendere il minimo possibile di punti (40/100) utilizzando il segment tree con la funzione di update O(N) dove N è il numero dei nodi dell’albero.
Poi ho scritto il codice della lazy propagation per portare la complessità scritta sopra a O(logN).
L’unico “piccolo” intoppo è che riesco ad ottenere solo 5 punti.
Questo è il codice che ho scritto.

#include <bits/stdc++.h>

#define MAXN 200100

using namespace std;

int N, Q;
int tree[MAXN], lazy[MAXN];

void update_tree_lazy(int tree[], int lazy[], int nodo, int inizio_seg, int fine_seg, int inizio_query, int fine_query)
{
	if(lazy[nodo] != 0)
	{
		tree[nodo] = (fine_seg - inizio_seg + 1) - tree[nodo];
		
		if(inizio_seg != fine_seg)
		{
			lazy[nodo*2+1] = 1;
			lazy[nodo*2+2] = 1;
		}
		
		lazy[nodo] = 0;
	}
	
	if(fine_seg < inizio_query || inizio_seg > fine_query)
		return;
	
	if(inizio_seg >= inizio_query && fine_seg <= fine_query)
	{
		tree[nodo] = (fine_seg - inizio_seg + 1) - tree[nodo];
		
		if(inizio_seg != fine_seg)
		{
			lazy[nodo*2+1] = 1;
			lazy[nodo*2+2] = 1;
		}
		
		return;
	}
	
	int mid = (inizio_seg + fine_seg)/2;
	
	update_tree_lazy(tree, lazy, nodo*2+1, inizio_seg, mid, inizio_query, fine_query);
	update_tree_lazy(tree, lazy, nodo*2+2, mid+1, fine_seg, inizio_query, fine_query);
	
	tree[nodo] = tree[nodo*2+1] + tree[nodo*2+2];
	return;
}

int sum_tree_lazy(int tree[], int lazy[], int nodo, int inizio_seg, int fine_seg, int inizio_query, int fine_query)
{
	if(lazy[nodo] != 0)
	{
		tree[nodo] = (fine_seg - inizio_seg + 1) - tree[nodo];
		
		if(inizio_seg != fine_seg)
		{
			lazy[nodo*2+1] = 1;
			lazy[nodo*2+2] = 1;
		}
		
		lazy[nodo] = 0;
	}
	
	if(inizio_seg > fine_query || fine_seg < inizio_query)
		return 0;
			
	if(inizio_seg >= inizio_query && fine_seg <= fine_query)	
		return tree[nodo];
		
	int mid = (inizio_seg + fine_seg)/2;
	
	return sum_tree_lazy(tree, lazy, nodo*2+1, inizio_seg, mid, inizio_query, fine_query) +
		   sum_tree_lazy(tree, lazy, nodo*2+2, mid+1, fine_seg, inizio_query, fine_query);
}

int potenza_vicina(int N)
{
	int i;
	for(i = 1; i < N; i += i)
		;
	return i;
}

//4 7
//1 0 3
//0 1 2
//1 0 1
//1 0 0
//0 0 3
//1 0 3
//1 3 3

int main()
{
//	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
	
	cin >> N >> Q;
	
	int n = potenza_vicina(N);
	
	for(int i = 0; i < Q; i++)
	{
		int tipo, da, a;
		cin >> tipo >> da >> a;
		
		if(tipo == 0)
			update_tree_lazy(tree, lazy, 0, 0, n-1, da, a);
		else
			cout << sum_tree_lazy(tree, lazy, 0, 0, n-1, da, a) << endl;
	}
}

Nel codice io utilizzo il lazy tree per tener conto degli update da effettuare. Se il nodo corrente è settato a 1 allora aggiorno il nodo dell’albero con la seguente formula: tree[nodo] = inizio_seg - fine_seg + 1 - tree[nodo]

2

Come non detto :disappointed_relieved:. Sono riuscito a risolvere il problema. Per chi interessa l’errore era nell’utilizzo di questa espressione:

lazy[nodo*2+1] = 1;
lazy[nodo*2+2] = 1;

anzichè questa:

if(lazy[nodo*2+1] == 1)
	lazy[nodo*2+1] = 0;
else
	lazy[nodo*2+1] = 1;

if(lazy[nodo*2+2] == 1)
	lazy[nodo*2+2] = 0;
else
	lazy[nodo*2+2] = 1;

Mi spiego meglio: quando vado a modificare un range, al posto di settare a 1 i figli, controllo se sono 1 o 0 e in base a quello inverto i valori dei nodi.

1 Mi Piace
3

Una maniera più compatta di fare la stessa cosa è usando lo xor:

lazy[nodo * 2 + 1] ^= 1;
lazy]nodo * 2 + 2] ^= 1;

Facendo lo xor con 1 inverti il valore del primo bit, che alla fine è l’unico che usi.

Dario

2 Mi Piace