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