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
i read the comments but i didn't find enough hint and i searced on google but i found only code .
Auto comment: topic has been updated by _Halabi (previous revision, new revision, compare).
Auto comment: topic has been updated by _Halabi (previous revision, new revision, compare).
You can remove
lx, rx
coordinates from each node and calculate them during recursive calls. It will save memorythanks ! thanks for the second time cause i realized that it will be solved using dynamic segtree from your comment on edu XD
Like lazy propagation?
Like lazy propagation, but you always propagate the same values — [lx, m] for left child and [m, rx] for right. Like you do this in classic segment tree
Auto comment: topic has been updated by _Halabi (previous revision, new revision, compare).