Obviously, you can sort the queries to solve the problem offline and use prefix sums to covert the question to "longest subarray with S[l] = S[r], L ≤ l ≤ r ≤ R.

Then, you can increase R and keep the answers for all L; it's just a matter of updating these answers when R is incremented. It can be done in .

First we use this Mo's algorithm to sort Query.

http://mirror.codeforces.com/blog/entry/7383

Let's call each group is a "bucket"

For each Query, we have to find i j which s[i] = s[j] and L<=i<=j<=R

Each i j has 3 cases :

1. i and j in bucket, so we can for, just O(sqrt(n))

2. i in bucket, j out of bucket. Let's call id1[s[j]]=j is the max position of s[j]. So answer is max(id1[s[i]]-i)

3. i and j out of bucket. Similar, call id2[s[j]]=j is the min position of s[j], so answer is max(id1[s[j]]-id2[s[j]])

I have solved it with MO's algorithm + segment tree for keeping track of the maximum value . Complexity is O( (N + M) * ROOT(N) * LOG (N) ) .

Here is the implementation http://ideone.com/YayNX7.

It would be good is someone can tell how to solve without the segment tree in O( (N + M) * ROOT(N) ).

Here is a editorial to a different problem with a similar solution.

WOW a post from 11 years ago. But I have a brute force like solution using SQRT decomposition.

1. Let's build a prefix sum of the array. Then we have to find max(j - i) where pref[i] = pref[j] holds for every l - 1 <= i < j <= r in each query.

2. Let's add N too every pref[i]. Since pref[i] is either 1 or -1, after adding N, 0 <= pref[i] <= 2 * N holds for every i. (We basically did a coordinate compression)

3. Let S be sqrt(N). And we will divide the array pref into S blocks. (Each block contains S numbers.) And we are constructing 2D array len with size S x S as follows: for every 0 <= I <= J < S, len[I][J] denotes max value of j - i where pref[i] = pref[j] and i, j belongs to Ith, Jth block respectively. This can be done using vector<int> index[2 * N + 1] where index[value] contains every i such that pref[i] = value in increasing order. TIME COMPLEXITY will be N * sqrt(N) * log(N).

4. Denote MAX(I, J) as maximum of len[x][y] where I <= x <= y <= J. And we are updating our len[I][J] to 'MAX(I, J)for each0 <= I <= J < Ssimultaneously. This can be done using Floyd Warshall. TIME COMPLEXITY will besqrt(N)^3orN * sqrt(N)`.

5. Finally, let's answer our queries. Let l - 1, r belongs to Lth, Rth block respectively and j - i be our optimal answer. If none of i and j belongs to block L and block R then the answer is simply len[L + 1][R - 1]. (if x > y then len[x][y] = 0) If i belongs to L or j belongs to R then we can just compute the answer in sqrt(N) * log(N) time using the vector<int> index[].

Therefore, overall time complexity will be N * sqrt(N) * log(N).

the code will be something like: for pre-queries: ~~~~~ pref[0] = n; for(int i = 1; i <= n; i++) { pref[i] += a[i]; index[pref[i]].push_back(i); }

for(int J = 0; J < S; J++) for(int I = 0; I < J; I++) { for(int i : block[I]) { int val = pref[i]; auto it = upper_bound(index[val].begin(), index[val].end(), block(J).back()); if(it != index[val].begin()) { len[I][J] = max(len[I][J], *prev(it) — i); } } }

for(int M = 0; M < S; M++) for(int L = 0; L < S; L++) for(int R = 0; R < S; R++) { if(L <= M && M <= R) { len[L][R] = max(len[L][R], len[L][M]); len[L][R] = max(len[L][R], len[M][R]); } } ~~~~~ for queries: ~~~~~ for(auto [l, r] : query) { l--; int L = block_id(l), R = block_id(r); int ans = 0; if(L + 1 <= R — 1) ans = max(ans, len[L + 1][R — 1]);

for(int i = l, i <= block[L].back(); i++) {
    int val = pref[i];
    auto it = upper_bound(index[val].begin(), index[val].end(), r);
    if(it != index[val].begin()) {
        ans = max(ans, *prev(it) - i);
    }
}

for(int i = block[R][0], i <= r; i++) {
    int val = pref[i];
    auto it = lower_bound(index[val].begin(), index[val].end(), l);
    if(it != index[val].end()) {
        ans = max(ans, i - *it);
    }
}
cout << ans << endl;

} ~~~~~