https://codeforces.me/edu/course/2/lesson/5/4/practice/contest/280801/problem/F↵
↵
↵
↵
this the lst problem at edu >>segment tree >>part2 ↵
the submissions are closed so i need hint !↵
↵
↵
↵
UPD : ↵
finaly I got AC ! ↵
↵
i'm not good enough to write educational blogs but i write this part as i didn't a lot of sources that explain dynamic segtree .↵
↵
↵
this problem need a dynamic segtree . the idea is that when you have large array (1...1e9)↵
it's difficult to make the normal segment tree because this need large space but in the same time time complexity ↵
is ok and the number of nodes that i visit over all queries are q*(log N) so why we need all this space ?↵
↵
we can just start from the root nd and iterate on we just need and remark nodes by map such that u will give each node u visit unique id (if it doesn't have one ) and by this id u can for this nd all the information you need ↵
but this still take a lot of time and space ! ↵
↵
so we will do the same but making each nd holds :↵
↵
1. ( it's information , lft child pointer , rght pointer , lx , rx ) ↵
2. function extend that create the two child (lft , rght ) ↵
↵
so we can start our basic operation from the root ( it's informaion , lft ,rght , 0,sz) and each nd we visit we extend two childs from and update thier information ↵
↵
↵
code : ↵
struct node{↵
// description↵
bool op = 0 ;↵
int oper =0 ;↵
item val ;↵
↵
//intialize nd↵
node (){↵
oper = 0;↵
val = {0,0} ;↵
}↵
↵
node * lft =NULL , *rght=NULL ; //create my two childs↵
void extend() ↵
{↵
↵
int md = (lx+rx)/2;↵
if (lft==NULL){↵
lft = new node;↵
lft ->lx =lx;↵
lft->rx =md;↵
}↵
↵
if (rght==NULL){↵
rght = new node;↵
rght->lx= md;↵
rght->rx = rx;↵
↵
}↵
}↵
}↵
↵
my submission for the problem (it needs more optimiztion ) : ↵
https://www.ideone.com/mhb2PB↵
↵
↵
↵
this the lst problem at edu >>segment tree >>part2 ↵
the submissions are closed so i need hint !↵
↵
↵
↵
UPD : ↵
finaly I got AC ! ↵
↵
i'm not good enough to write educational blogs but i write this part as i didn't a lot of sources that explain dynamic segtree .↵
↵
↵
this problem need a dynamic segtree . the idea is that when you have large array (1...1e9)↵
it's difficult to make the normal segment tree because this need large space but in the same time time complexity ↵
is ok and the number of nodes that i visit over all queries are q*(log N) so why we need all this space ?↵
↵
we can just start from the root nd and iterate on we just need and remark nodes by map such that u will give each node u visit unique id (if it doesn't have one ) and by this id u can for this nd all the information you need ↵
but this still take a lot of time and space ! ↵
↵
so we will do the same but making each nd holds :↵
↵
1. ( it's information , lft child pointer , rght pointer , lx , rx ) ↵
2. function extend that create the two child (lft , rght ) ↵
↵
so we can start our basic operation from the root ( it's informaion , lft ,rght , 0,sz) and each nd we visit we extend two childs from and update thier information ↵
↵
↵
code : ↵
struct node{↵
// description↵
bool op = 0 ;↵
int oper =0 ;↵
item val ;↵
↵
//intialize nd↵
node (){↵
oper = 0;↵
val = {0,0} ;↵
}↵
↵
node * lft =NULL , *rght=NULL ; //create my two childs↵
void extend() ↵
{↵
↵
int md = (lx+rx)/2;↵
if (lft==NULL){↵
lft = new node;↵
lft ->lx =lx;↵
lft->rx =md;↵
}↵
↵
if (rght==NULL){↵
rght = new node;↵
rght->lx= md;↵
rght->rx = rx;↵
↵
}↵
}↵
}↵
↵
my submission for the problem (it needs more optimiztion ) : ↵
https://www.ideone.com/mhb2PB↵
