jasonnguyen.damn's blog

sqrt decompositon
By jasonnguyen.damn, history, 12 months ago, In English

sorry i don't know how to call this technique so I just named it sqrt decomposition. while I read tutorial of this problem: 797E - Array Queries, i just realize this problem use sqrt decomposition in the strange way that i have never seen before but i couldn't find it's in4 anywhere. can anyone give me this technique's in4 or like how to solve this type of problem. (sorry for my poor english ^^)

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

»
12 months ago, hide # |
 
Vote: I like it +2 Vote: I do not like it

I like to call it "heavy-light partitioning", a few problems can be found here: https://mirror.codeforces.com/blog/entry/139745?#comment-1248383. General strategy is to find a parameter that can be split to "heavy" and "light", in this case it's $$$k$$$ (process the "light" $$$k$$$'s ($$$\leq \sqrt{n}$$$) and the "heavy" ones separately then combine them somehow.)

→ Reply