Problema segtree. 40/100 output errato

Aiuto
1

Sto provando ad implementare la lazy propagation sul problema segtree, ma purtroppo mi da output errato su gran parte dei casi di test dopo il subtask 3. È da 3 ore che sto provando a capire perchè…

Questo è il mio codice:

#include <bits/stdc++.h>

using namespace std;

// Valori neutri rispettivamente per somma e minimo.
const long long NEUTRO = 0;
const long long NEUTRO_MIN = LLONG_MAX;

struct Nodo {
	long long val;
	long long mi;
	long long lazySet;
	long long lazyAdd;
	Nodo() : val(NEUTRO), mi(NEUTRO_MIN), lazySet(LLONG_MIN), lazyAdd(0) {};
	// Nodo tiene valore della somma e minimo.
	void join(Nodo &a, Nodo &b) {
		val = a.val + b.val;
		mi = min(a.mi, b.mi);
	}
};

int n, realSize;
vector<Nodo> segTree;

void isLazy(int u, int left, int right) {
	if (segTree[u].lazySet != LLONG_MIN) {
		// Sei lazy! Impostati!
		segTree[u].val = (right - left) * segTree[u].lazySet;
		segTree[u].mi = segTree[u].lazySet;
		if ((u * 2) + 1 < segTree.size()) {
			segTree[u * 2].lazySet = segTree[u].lazySet;
			segTree[(u * 2) + 1].lazySet = segTree[u].lazySet;
		}
		segTree[u].lazySet = LLONG_MIN;
	}
	if (segTree[u].lazyAdd != 0) {
		// Sei lazy! Impostati!
		segTree[u].val += (right - left) * segTree[u].lazyAdd;
		segTree[u].mi += segTree[u].lazyAdd;
		if ((u * 2) + 1 < segTree.size()) {
			segTree[u * 2].lazyAdd += segTree[u].lazyAdd;
			segTree[(u * 2) + 1].lazyAdd += segTree[u].lazyAdd;
		}
		segTree[u].lazyAdd = 0;
	}
}

void build(int u, int l, int r, vector<long long> &dati);
void init(vector<long long> a) {
	n = a.size();
	realSize = 1;
	while (realSize < n) {
		// grandezza del vettore deve essere una potenza di due.
		realSize *= 2;
	}
	// prima metà si tiene l'albero binario, seconda metà i dati.
	segTree.assign(realSize * 2, Nodo());
	build(1, 0, realSize, a);
}

void build(int u, int l, int r, vector<long long> &dati) {
	if (r - l <= 1) {
		// Sono una foglia, quindi imposto il valore direttamente
		// Se elemento è effettivamente un elemento, essendo dati non per forza una potenza di 2
		if (l < dati.size()) {
			segTree[u].val = dati[l];
			segTree[u].mi = dati[l];
		}
	} else {
		// Non sono una foglia, ricorro...
		build(u * 2, l, (l + r)/2, dati);
		build((u * 2) + 1, (l + r)/2, r, dati);
		// joino i risultati
		segTree[u].join(segTree[u * 2], segTree[u * 2 + 1]);
	}
}

long long get_min(int u, int left, int right, int l, int r) {
	if (r <= left || l >= right) {
		// Non compreso nel mio insieme. Mi fermo quì!
		return NEUTRO_MIN;
	}
	if (left >= l && right <= r) {
		// Mi piace, mi fermo quì
		return segTree[u].mi;
	}
	isLazy(u, left, right);

	// Devo ricorrere 😭
	return min(
			get_min(u * 2, left, (left + right) / 2, l, r),
			get_min((u * 2) + 1, (left + right) / 2, right, l, r)
			);
}
long long get_sum(int u, int left, int right, int l, int r) {
	if (r <= left || l >= right) {
		// Non compreso nel mio insieme. Mi fermo quì!
		return NEUTRO;
	}
	if (left >= l && right <= r) {
		// Mi piace, mi fermo quì
		return segTree[u].val;
	}
	isLazy(u, left, right);

	// Devo ricorrere 😭
	return (
			get_sum(u * 2, left, (left + right) / 2, l, r) +
			get_sum((u * 2) + 1, (left + right) / 2, right, l, r)
			);
}

long long get_min(int l, int r) {return get_min(1, 0, realSize, l, r); }
long long get_sum(int l, int r) {return get_sum(1, 0, realSize, l, r); }

void set_range(int u, int left, int right, int l, int r, long long x) {
	isLazy(u, left, right);
	if (l >= right || r <= left) return;
	if (left >= l && right <= r) {
		// Sono interamente contenuto, aggiorno il valore
		// e metto lazy i figli
		segTree[u].val = (right - left) * x;
		segTree[u].mi = x;
		if ((u * 2) + 1 < segTree.size()) {
			segTree[u * 2].lazySet = x;
			segTree[(u * 2) + 1].lazySet = x;
		}
	} else {
		// Non sono una foglia, ricorro...
		set_range(u * 2, left, (left + right)/2, l, r, x);
		set_range((u * 2) + 1, (left + right)/2, right, l, r, x);
		// joino i risultati
		segTree[u].join(segTree[u * 2], segTree[u * 2 + 1]);
	}
}
void set_range(int l, int r, long long x) {set_range(1, 0, realSize, l, r, x);}

void add(int u, int left, int right, int l, int r, long long x) {
	isLazy(u, left, right);
	if (l >= right || r <= left) return;
	if (left >= l && right <= r) {
		// Sono interamente contenuto, aggiorno il valore
		// e metto lazy i figli
		segTree[u].val += (right - left) * x;
		segTree[u].mi += x;
		if ((u * 2) + 1 < segTree.size()) {
			segTree[u * 2].lazyAdd += x;
			segTree[(u * 2) + 1].lazyAdd += x;
		}
	} else {
		// Non sono una foglia, ricorro...
		add(u * 2, left, (left + right)/2, l, r, x);
		add((u * 2) + 1, (left + right)/2, right, l, r, x);
		// joino i risultati
		segTree[u].join(segTree[u * 2], segTree[u * 2 + 1]);
	}
}
void add(int l, int r, long long x) {
	if (x == 0) return;
	add(1, 0, realSize, l, r, x);
}

int lower_bound(int u, int left, int right, int l, int r, long long x) {
	isLazy(u, left, right);
	if ((r <= left || l >= right) || segTree[u].mi > x) {
		// NON VA BENE 😭
		return -1;
	}
	if (right - left <= 1) {
		// Che bello! Sono una foglia 😁
		return left;
	}

	int le = lower_bound(u * 2, left, (left + right) / 2, l, r, x);
	if (le != -1) return le;

	int ri = lower_bound((u * 2) + 1, (left + right) / 2, right, l, r, x);
	return ri;
}

int lower_bound(int l, int r, long long x) {
	return lower_bound(1, 0, realSize, l, r, x);
}
2

Ho trovato il problema, praticamente quando stavo pushando un’operazione set range, non eliminavo l’add di prima, e quindi li faceva comunque sballando i risultati.

3

puoi spiegarti meglio?

4

Sto avendo lo stesso problema con questo codice, non saprei come sistemarlo. Ho provato ad unire i due update nella lazy propagation, ma continua a non funzionare.

#include <bits/stdc++.h>
#include <climits>

using namespace std;

static long long MAX = LLONG_MAX;

struct Node{
	long long mi;
	long long val;
    long long lazy_set;
    long long lazy_add;

	Node() : mi(MAX), val(0), lazy_add(0), lazy_set(LLONG_MIN) {};

	void join(Node &l, Node &r) {
        mi = min(l.mi, r.mi);
		val = l.val + r.val;
	}
};

int n, real_size;	// real_size è anche l'indice del primo nodo dell'ultimo livello
vector<Node> nodes;

void is_lazy(int u, int l, int r) {
	if(nodes[u].lazy_add == 0 && nodes[u].lazy_set == LLONG_MIN) return;

	if(nodes[u].lazy_add != 0) {
		// aumento direttamente il nodo e propago ai figli nel lazy
		nodes[u].mi += nodes[u].lazy_add;
		// se aggiungo n a tutte le foglie in un range, il singolo nodo aumenta di n*range
		nodes[u].val += nodes[u].lazy_add*(r-l);

		// non sono in una foglia, ho dei figli
		if(2*u+1 < nodes.size()) {
			// non si devono stackare lazy_updates
			// SE AGGIUNGO QUALCOSA DOPO UN SET DEVOTENERE CONTO DEL SET
			if(nodes[2*u].lazy_set != LLONG_MIN) {
				nodes[2*u].lazy_set += nodes[u].lazy_add + nodes[2*u].lazy_add;
				nodes[2*u].lazy_add = 0;
			}
			else {
				nodes[2*u].lazy_add += nodes[u].lazy_add;
			}

			if(nodes[2*u+1].lazy_set != LLONG_MIN) {
				nodes[2*u+1].lazy_set += nodes[u].lazy_add + nodes[2*u+1].lazy_add;
				nodes[2*u+1].lazy_add = 0;
			}
			else {
				nodes[2*u+1].lazy_add += nodes[u].lazy_add;
			}
		}

		nodes[u].lazy_add = 0;

		// NON SERVE in lazy prop
		// while(u > 1) {
		// 	u /= 2;
		// 	nodes[u].join(nodes[2*u], nodes[2*u+1]);
		// }

		// se ha lazy_add != 0, non può avere lazy_set != 0 perché lo avrei risolto in add()
		return;
	}

	// aumento direttamente il nodo e propago ai figli nel lazy
	nodes[u].mi = nodes[u].lazy_set;	
	// se cambio l'interno range di numeri in n --> la somma dei numeri sarà il numero di nodi incluso nel range * n
	nodes[u].val = nodes[u].lazy_set*(r-l);

	if(2*u+1 < nodes.size()) {
		// non voglio che si stackino lazy updates
		nodes[2*u].lazy_add = 0;
		nodes[2*u+1].lazy_add = 0;
		
		nodes[2*u].lazy_set = nodes[u].lazy_set;
		nodes[2*u+1].lazy_set = nodes[u].lazy_set;
	}

	nodes[u].lazy_set = LLONG_MIN;

	// while(u > 1) {
	// 	u /= 2;
	// 	nodes[u].join(nodes[2*u], nodes[2*u+1]);
	// }

	return;
}

void build(int u, int l, int r, vector<long long> &a) {
	// se il range è = 1, sono in una foglia
	if(r-l <= 1) {
		if(l<a.size()) {	// il numero esiste e non è solo un -INF
			nodes[u].mi = a[l];	// l è incluso, r no --> il nodo è l
			nodes[u].val = a[l];
		}
	}
	// se non sono in una foglia calcolo ricorsivamente i due figli
	else {
		build(u*2, l, (l+r)/2, a);
		build(u*2+1, (l+r)/2, r, a);
		nodes[u].join(nodes[2*u], nodes[2*u+1]);
	}
}

void init(vector<long long> a) {
	// n è la lunghezza della sequenza di numeri, realsize la potenza di due subito dopo
	n = a.size();

	real_size = 1;
	while(real_size < n) {
		real_size *= 2;
	}

	nodes.assign(2*real_size, Node());

	build(1, 0, real_size, a);
}

long long get_sum(int u, int l, int r, int x, int y) {
	// tengo conto del nodo, quindi mi serve che sia up-to-date
	is_lazy(u, l, r);

	// controllo se è completamente escluso
	if(l >= y || r <= x) return 0;

	// completamente incluso
	if(l>=x && r<=y) return nodes[u].val;

	// parzialmente incluso, somma dei due figli
	return (get_sum(2*u, l, (r+l)/2, x, y) + get_sum(2*u+1, (l+r)/2, r, x, y));
}

long long get_sum(int l, int r) {
	return get_sum(1, 0, real_size, l, r);
}

void add(int u, int l, int r, int x, int y, long long n) {
	// tengo conto del nodo, quindi mi serve che sia up-to-date
	is_lazy(u, l, r);

	// no overlap, nothing to do
	if(l >= y || r <= x) return;

	// full overlap, update node & lazy children
	// sia la somma che il minimo aumenteranno di x
	if(l >= x && r <= y) {
		// aumento direttamente il nodo e propago ai figli nel lazy
		nodes[u].mi += n;
		// se aggiungo n a tutte le foglie in un range, il singolo nodo aumenta di n*range
		nodes[u].val += n*(r-l);

		if(2*u+1 < nodes.size()) {
			// non si devono stackare lazy_updates
			// SE AGGIUNGO QUALCOSA DOPO UN SET DEVOTENERE CONTO DEL SET
			if(nodes[2*u].lazy_set != LLONG_MIN) {
				nodes[2*u].lazy_set += nodes[u].lazy_add + nodes[2*u].lazy_add;
				nodes[2*u].lazy_add = 0;
			}
			else {
				nodes[2*u].lazy_add += n;
			}

			if(nodes[2*u+1].lazy_set != LLONG_MIN) {
				nodes[2*u+1].lazy_set += nodes[u].lazy_add + nodes[2*u+1].lazy_add;
				nodes[2*u+1].lazy_add = 0;
			}
			else {
				nodes[2*u+1].lazy_add += n;
			}
		}

		// NON SERVE PERCHE DOVUNQUE C'E UN PARZIALE OVERLAP FACCIO GIA IL JOIN
		// while(u > 1) {
		// 	u /= 2;
		// 	nodes[u].join(nodes[2*u], nodes[2*u+1]);
		// }

		return;
	}

	// partial overlap
	add(2*u, l, (l+r)/2, x, y, n);
	add(2*u+1, (l+r)/2, r, x, y, n);
	nodes[u].join(nodes[2*u], nodes[2*u+1]);

	return;
}

void add(int l, int r, long long x) {
	add(1, 0, real_size, l, r, x);
}

void set_range(int u, int l, int r, int x, int y, int n) {
	// tengo conto del nodo, quindi mi serve che sia up-to-date
	is_lazy(u, l, r);

	// no overlap, nothing to do
	if(l >= y || r <= x) return;

	// full overlap, update node & lazy children
	// sia la somma che il minimo aumenteranno di x
	if(l >= x && r <= y) {
		// aumento direttamente il nodo e propago ai figli nel lazy
		nodes[u].mi = n;	
		// se cambio l'interno range di numeri in n --> la somma dei numeri sarà il numero di nodi incluso nel range * n
		nodes[u].val = n*(r-l);

		// non sono una foglia --> ho dei figli
		if(2*u+1 < nodes.size()) {
			// non voglio che si stackino lazy updates
			nodes[2*u].lazy_add = 0;
			nodes[2*u+1].lazy_add = 0;
			
			nodes[2*u].lazy_set = n;
			nodes[2*u+1].lazy_set = n;
		}
		
		// NON SERVE PERCHE DOVUNQUE C'E UN PARZIALE OVERLAP FACCIO GIA IL JOIN
		// while(u > 1) {
		// 	u /= 2;
		// 	nodes[u].join(nodes[2*u], nodes[2*u+1]);
		// }

		return;
	}

	// partial overlap
	set_range(2*u, l, (l+r)/2, x, y, n);
	set_range(2*u+1, (l+r)/2, r, x, y, n);
	nodes[u].join(nodes[2*u], nodes[2*u+1]);

	return;
}

void set_range(int l, int r, long long x) {
	set_range(1, 0, real_size, l, r, x);
}

long long get_min(int u, int l, int r, int x, int y) {	// y escluso
	// tengo conto del nodo, quindi mi serve che sia up-to-date
	is_lazy(u, l, r);

	// controllo se i limiti sono completamente esclusi
	if(l >= y || r <= x) return MAX;

	// sono completamente inclusi, ritorno il valore del nodo corrente
	if(l >= x && r <= y) return nodes[u].mi;

	// se sono inclusi a metà prendo il minimo della chiamata ricorsiva ai due figli
	return min(
		get_min(2*u, l, (l+r)/2, x, y),
		get_min(2*u+1, (l+r)/2, r, x, y)
	);
}

long long get_min(int l, int r) {
	return get_min(1, 0, real_size, l, r);
}

int lower_bound(int u, int l, int r, int x, int y, long long bound) {
	// tengo conto del nodo, quindi mi serve che sia up-to-date
	is_lazy(u, l, r);
	
    // controllo se i limiti sono completamente esclusi
    if(l >= y || r <= x) return -1;

	// sono almeno parzialmente inclusi, controllo se il valore del nodo corrente è minore di bound
    if(nodes[u].mi <= bound) {
        // sono una foglia
        if(r-l<=1) return l;

        // non sono una foglia, prima controllo sx poi dx
        int sx = lower_bound(2*u, l, (l+r)/2, x, y, bound);
        if(sx != -1) return sx;
        return lower_bound(2*u+1, (l+r)/2, r, x, y, bound);
    }
    return -1;
}

int lower_bound(int l, int r, long long x) {
	// returns the index to the left most element <= x
	return lower_bound(1, 0, real_size, l, r, x);
}```
5

quanti e dove fai i punti?

6

Faccio 40/100, completando i subtasks 2 e 3. Degli altri riesco a fare giusto il primo testcase prima che dia output errato.

7

Esattamente come me, penso che sia un errore della lazy propagation del set, perchè se la tolgo, mi da fuori tempo ma i primi due testcase giusti, ma non sono troppo sicuro. Se arrivi a una soluzione dimmi qualcosa, farò lo stesso