_Halabi's blog

By _Halabi, history, 8 months ago, In English

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

  • Vote: I like it
  • +4
  • Vote: I do not like it

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

i read the comments but i didn't find enough hint and i searced on google but i found only code .

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by _Halabi (previous revision, new revision, compare).

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by _Halabi (previous revision, new revision, compare).

»
8 months ago, # |
  Vote: I like it +8 Vote: I do not like it

You can remove lx, rx coordinates from each node and calculate them during recursive calls. It will save memory

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    thanks ! thanks for the second time cause i realized that it will be solved using dynamic segtree from your comment on edu XD

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Like lazy propagation?

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by _Halabi (previous revision, new revision, compare).