RangeTree 2, classe segmentTree

Algoritmi
1

Parto dicendo che ho già risolto RangeTree2 svariati mesi fa, ma implementavo segment/lazy tramite gli array. Ho provato a risolvere so stesso esercizio rappresentando il segment tree con le classi, quello che non capisco è come vada in TLE utilizzando la stessa logica che ho usato quando l’ho risolto tramite la rappresentazione con gli array.

Facendo qualche test ho notato come sia la funzione update() ad utilizzare troppo tempo d’esecuzione, a questo punto penso che l’errore sia uno dei seguenti:

  1. Per una svista mia la funzione update() potrebbe andare in loop.

  2. Ho commesso un errore nella logica dell update.

  3. L’implementazione con le classi è troppo lenta.

Codice:

#include<bits/stdc++.h>
using namespace std;
ifstream in("input.txt");
ofstream out("output.txt");
#define cin in
#define cout out
int const MAXN=100001;
class segmentTree{
	public:
		int l, r, z, u, d, lazy;
		segmentTree *left, *right;
		segmentTree(int start, int end){
			l=start;
			r=end;
			lazy=0;
			if(start==end){
				z=1;
				u=d=0;
				right=left=nullptr;
			}
			else{
				int mid=(start+end)/2;
				left=new segmentTree(start,mid);
				right=new segmentTree(mid+1,end);
				z=left->z+right->z;
				u=d=0;
			}
		}
		void rotate(){
			int tmp=d;
			d=u;
			u=z;
			z=tmp;
		}
		void update(int start, int end){
			if(lazy!=0){
				lazy%=3;
				if(left) left->lazy+=lazy;
				if(right) right->lazy+=lazy;
				while(lazy--)
					rotate();
			}
			if(l>end || r<start)
				return;
			if(l>=start && r<=end){
				rotate();
				if(right) right->lazy++;
				if(left) left->lazy++;
				return;
			}
			left->update(start,end);
			right->update(start,end);
			z=left->z+right->z;
			u=left->u+right->u;
			d=left->d+right->d;
		}
		int query(int start, int end){
			if(lazy!=0){
				lazy%=3;
				if(left) left->lazy+=lazy;
				if(right) right->lazy+=lazy;
				while(lazy--)
					rotate();
			}	
			if(l>end || r<start)
				return 0;
			if(l>=start && r<=end)
				return z;
			return left->query(start,end)+right->query(start,end);
		}
};
int main(){
	int n, q;
	cin>>n>>q;
	segmentTree st(0,n-1);
	while(q--){
		int op, start, end;
		cin>>op>>start>>end;
		if(op==0)
			st.update(start,end);
		else
			cout<<st.query(start,end)<<"\n";
	}
}

UPDATE: risolto

1 Mi Piace