# Aiuto con rangetree1

**URL:** <https://forum.olinfo.it/t/aiuto-con-rangetree1/8468>\
**Category:** Aiuto\
**Created:** [19 Agosto 2023, 4:17pm UTC](https://forum.olinfo.it/t/aiuto-con-rangetree1/8468 "2023-08-19T16:17:56Z")\
**Posts on this page:** 4\
**Page:** 1

<div class="post-metadata">

**Author:** ![jhon06](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/j/8797f3/32.png) [@jhon06](https://forum.olinfo.it/u/jhon06)\
**Post date:** [19 Agosto 2023, 4:17pm UTC](https://forum.olinfo.it/t/aiuto-con-rangetree1/8468/1 "2023-08-19T16:17:56Z")

</div>

Ciao, stavo provando a svolgere rangetree1 ma ottengo un output errato in tutti i test tranne il primo,  
l’idea è molto semplice, uso un segment tree e in ogni nodo mantengo il conteggio delle teste, quando avviene un flip inverto il numero di teste e di croci. Ho ricontrollato varie volte il codice e  
sospetto sia un errore di implementazione, tuttavia non riesco a trovarlo, qualcuno ha qualche suggerimento?

```auto
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;

struct SegmentTree{
	int sz;
	vector <bool> array;
	struct Node{
		ll sum;
		int lzset;
		int nodi;
		Node(){
			sum=0;
			lzset=-1;
		}
		void set(bool a){
			sum=a;
			nodi=1;
			lzset=-1;
		}
		void merge(Node a,Node b){
			sum=a.sum+b.sum;
			nodi=a.nodi+b.nodi;
		}
	};
	vector <Node> segTree;
	void make(vector <bool> a){
		array=a;
		sz=1;
		while(sz<a.size())sz*=2;
		segTree.resize(sz*2);
		build(1,0,sz-1);
	}
	void build(int p,int l,int r){
		if(r==l){
			segTree[p].set(array[l]);
		}
		else{
			int mid=(l+r)/2;
			build(p*2,l,mid);
			build(p*2+1,mid+1,r);
			segTree[p].merge(segTree[p*2],segTree[p*2+1]);
		}
	}
	int get_sum(int l,int r){
		return get_sum2(1,l,r,0,sz-1);
	}
	void propagate(int p){
		if(segTree[p].lzset==-1)return;
		if(segTree[p].nodi==1){
			segTree[p].lzset=-1;
			return;
		}
		else{
			segTree[p*2].sum=segTree[p*2].nodi-segTree[p*2].sum;
			segTree[p*2+1].sum=segTree[p*2+1].nodi-segTree[p*2+1].sum;
			segTree[p*2].lzset=segTree[p].lzset;
			segTree[p*2+1].lzset=segTree[p].lzset;
			segTree[p].lzset=-1;
		}
	}
	void flip2(int p,int l,int r,int tl,int tr){
		if(tr<l || tl>r) return ;
		propagate(p);
		if(tl>=l && tr<=r){
			segTree[p].sum=segTree[p].nodi-segTree[p].sum;
			segTree[p].lzset=1;
			return;
		}
		else{
			int mid=(tl+tr)/2;
		    flip2(p*2,l,r,tl,mid);
		    flip2(p*2+1,l,r,mid+1,tr);
		}
		segTree[p].merge(segTree[p*2],segTree[p*2+1]);
	}
	void flip(int l,int r){
		flip2(1,l,r,0,sz-1);
	}
	int get_sum2(int p,int l,int r,int tl,int tr){
		if(tl>tr) return 0;
		if(tr<l || tl>r) return 0;
		propagate(p);
		if(tl>=l && tr<=r){
			return segTree[p].sum;
		}
		int mid=(tl+tr)/2;
		return get_sum2(p*2,l,r,tl,mid)+get_sum2(p*2+1,l,r,mid+1,tr);
	}
};
void compute(){
	ll n,q;
	cin>>n>>q;
	vector <bool> a;
	for(int i=0;i<n;i++)a.pb(0);
	SegmentTree si;
	si.make(a);
	for(int i=0;i<q;i++){
		int t;
		cin>>t;
		if(t==0){
			int a,b;
			cin>>a>>b;
			si.flip(a,b);
		}
		else{
			int a,b;
			cin>>a>>b;
			cout<<si.get_sum(a,b)<<'\n';
		}
	}
}

```

---

<div class="post-metadata">

**Author:** ![qwfwq](https://forum.olinfo.it/user_avatar/forum.olinfo.it/qwfwq/32/2974_2.png) [@qwfwq](https://forum.olinfo.it/u/qwfwq)\
**Post date:** [20 Agosto 2023, 5:43pm UTC](https://forum.olinfo.it/t/aiuto-con-rangetree1/8468/2 "2023-08-20T17:43:16Z")

</div>

Sono solo queste le 2 righe di codice che devi rivedere:

```auto
segTree[p*2].lzset = segTree[p].lzset;
segTree[p*2+1].lzset = segTree[p].lzset;

```

per risolvere il task.

Tuttavia per prendere 100/100 devi anche rivedere il valore di sz nella funzione make() perché il tuo segment tree non opera propriamente con intervalli di potenza di 2.

---

<div class="post-metadata">

**Author:** ![jhon06](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/j/8797f3/32.png) [@jhon06](https://forum.olinfo.it/u/jhon06)\
**Post date:** [21 Agosto 2023, 7:55am UTC](https://forum.olinfo.it/t/aiuto-con-rangetree1/8468/3 "2023-08-21T07:55:28Z")

</div>

ciao, innanzitutto grazie per la risposta, per quanto riguarda il primo suggerimento ho corretto il codice considerando anche il caso in cui il nodo verso cui devo propagare abbia già lzset attivo, correggendo questo prendo 100/100, a questo punto quindi credo che il valore di sz sia calcolato correttamente?

---

<div class="post-metadata">

**Author:** ![qwfwq](https://forum.olinfo.it/user_avatar/forum.olinfo.it/qwfwq/32/2974_2.png) [@qwfwq](https://forum.olinfo.it/u/qwfwq)\
**Post date:** [21 Agosto 2023, 8:56am UTC](https://forum.olinfo.it/t/aiuto-con-rangetree1/8468/4 "2023-08-21T08:56:47Z")

</div>

Va bene così. È solo con la modifica adottata che mi dava errore:  
Execution killed (could be triggered by violating memory limits).

```auto
segTree[p*2].lzset = -segTree[p*2].lzset;
segTree[p*2+1].lzset = -segTree[p*2+1].lzset;

```