Joker1010123's blog

SQRT decomposition
By Joker1010123, history, 8 years ago, In English

Hi everybody. I'm learning about SQRT decomposition and I want some problems. Can you give me? Thanks very much. ♥♦♣♠

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

Comments Comments (9)
| Write comment?
»
8 years ago, # |
← Rev. 2   Vote: I like it +9 Vote: I do not like it

You can try to solve 3 problems below:

DQUERY

Sherlock and Inversions

Powerful array

→ Reply
»
8 years ago, # |
  Vote: I like it -9 Vote: I do not like it

Ummmm...

LINK

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

This one has many solutions, but SQRT decomposition is one of them: 242E - XOR on Segment
If you're stuck, then here is the code: 24227961

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    szawinis can u explain the solution ..help would be appreciated!

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You solve for each of the possible bits separately, then combine them later, since the query asks for sums. The reason why we do this is to make it more straightforward when applying the first query. This problem can also be solved using lazy segment tree which IMO is easier to code than SQRT decomp.

      → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

This link might help you.

→ Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Here's another one that can be solved with SQRT decomposition http://codeforces.net/problemset/problem/13/E and with some SQRT heuristics this one too http://codeforces.net/contest/797/problem/E

→ Reply