### color_me_red's blog

By color_me_red, history, 4 years ago,

I have an array a of values +1 and -1 in random order, and a separate array s which is initialised with 0 in every position. I run through the array from left to right. At every index i, I add the value of a[i] across s[0], s[1], ... , s[i-1], s[i]. And at every index i, after doing the previous operation, I want to return the rightmost index in the range [0, i] with value 0. If no such index exists, I'll return some invalid number like -1.

The adding operation can be done using a Fenwick tree. But I have no clue to find the rightmost index in logarithmic complexity. I'm trying to do the entire process in O(n) or O(nlogn) complexity. Any idea would be much appreciated, thanks!

• +11

By color_me_red, history, 4 years ago,

With an array of size  ≤ 105, and with every a[i] in the range 1 ≤ a[i] ≤ 105, there are  ≤ 105 queries.

Each query is of the form [l, r, k], and the output should the number of elements that appear  ≥ k times in a[l]..a[j]. I've though on this for a while, and can't get any idea how to solve this. I've seen a similar problem before but can't find the statement anywhere.

I'm thinking squareroot decomposition could work, but have no clue to proceed. Thanks for any help!

• +15

By color_me_red, history, 4 years ago,

There is this code:

Function Find(integer n,function func) If n=1
For i = 1 to a do func()
Elseif n=2
For i = 1 to b do func()
Else Find(n-1,Find(n-2,func))

Function Main
Find(n,funny)


With given values of n, a, b and a modulus p, the question asks to output the number of times func() will be called. n can be upto 10^9. The direct recurrence would be f[n] = f[n-2]*(f[n-1] + 1) with base cases for 1, 2 I think. But since this isn't a linear recurrence how can I use matrix exponentiation to solve the problem? Thanks for any help!

• 0

By color_me_red, history, 4 years ago,

If I have a square of some area a, and n other squares of the same area a, how can I check if the union of the n squares contains the initial square completely? I think I read that there is an solution for this, could someone help? Thanks!

• 0

By color_me_red, history, 4 years ago,

Briefly, there is a tree with some values on each node. For each query a,b, I have to find the contiguous subarray with maximum sum in the path a — b. There are range updates a b v, which change the value of the nodes in a — b to some v.

My approach is to decompose the tree (heavy light) and then find the answer(I'll come to what I mean by this) for a -> lca(a,b), and then the same for b -> lca(a,b).

If the path from a -> lca(a,b) passes through five chains, I get all the answers for each chain in the range that belongs to the path a -> lca(a,b). The answer consists of max sum, max prefix sum, max postfix sum, total sum. I store these in a list. And do the same for b -> lca(a,b). I concatenate the two lists appropriately. Then on this final list, I calculate the final answer (exactly same as what's been done for the segment trees of the chains).

Is there a better way that doesn't involve joining all the answers of the involved chains and then finding the answer from them? I'll explain more if I needed.