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!

With an array of size  ≤ 10⁵, and with every a[i] in the range 1 ≤ a[i] ≤ 10⁵, there are  ≤ 10⁵ 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!

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!

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!

Here is a link to the problem.

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.