divide n=2 and m=6 equally between them

# Code Invicta Discussion

literally I do not understand how you are talking about division between n = 2 and m = 6

can you please tell briefly. I don’t know why I am not getting it

I passed CHRIST02 with a sketchy sqrt-decomp that probably shouldn’t have passed.

First, optimize the naive O(NQ) with LCA (specifically binary lifting), making it so you only traverse exactly the vertices on the path. Then the solution looks roughly like:

```
while (u != lca) {
if (l <= arr[u] && arr[u] <= r) ++ans;
u = par[u];
}
# do the same for v
```

Then fix some power of 2, call it C. For each node with depth >= C, store its first C ancestors in a sorted array. For a query, if the node is at least C depth below the LCA, binary search on how many values are between L and R for the query in the sorted values. Then use the jump-pointer from the binary lifting to advance C ancestors of the current node. This becomes O(Q\log(N)(C + \frac{N}{C})) overall, which passed in 1.9s with C = 256.

Submission (code is quite ugly though)

Seems like other people used persistent segment trees or heavy-light decomposition.

I don’t know how to do CHRIST01.

what time it takes to printing all 6 digit numbers in python?

Isn’t it O(n \sqrt{n \log(n)}) with optimal C?

Oh true, that does become slightly better.

Well, I think my solution is quite short and simple to understand. https://www.codechef.com/viewsolution/30743229 I think it is O(nlog^3n), but I use lower_bound which is quite fast. Also, you could make this solution faster by using Fenwick tree like so: https://www.codechef.com/viewsolution/30749047 HLD is based on this: https://codeforces.com/blog/entry/53170 and this can solve almost all tree query problems.

You declared n as integer , it should be long long .

What will be the approach in order to minimise the answer ?

Check the 2nd section in in the solution sketch to of Jeremy and bearimy problem

My approach was similar to yours can you see why i am getting WA?

https://www.codechef.com/viewsolution/30743684

nxt[h] stores the next house having zero

Can you please explain how you solve the " Bring Positivity " Question !

Please share a tag for " Bring Positivity ". Thanks