hint dynamic segmentree
Difference between en1 and en2, changed 2,068 character(s)
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 eductional blogs  but i write this part as i did'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 uniqe 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 space  ! ↵

so we will do the same but using  make 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 need more optimiztion ) : ↵
https://www.ideone.com/mhb2PB↵
   

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English _Halabi 2024-03-10 08:02:21 10 Tiny change: ' a lot of space ! \n\nso' -> ' a lot of time and space ! \n\nso'
en3 English _Halabi 2024-03-10 05:15:56 17
en2 English _Halabi 2024-03-10 05:12:48 2068
en1 English _Halabi 2024-03-10 00:07:11 189 Initial revision (published)