UNSQUERS - Editorial

PROBLEM LINK:

Practice
Div-2 Contest
Div-1 Contest

Author: Andrii Orap
Tester: Istvan Nagy
Editorialist: Andrii Orap

DIFFICULTY:

HARD?

PREREQUISITES:

Persistent segment tree with lazy propagation

PROBLEM:

Given an integer array A of length N and M queries of type L and R. For each query find maximum F(A[i..j]) for some L \leq i \leq j \leq R, where F(B) of array B is the number of changes of maximum on prefixes of array B.

QUICK EXPLANATION:

Offline solution: Iterate i from left to right, for each position j maintain the number of maximum changes on subarray A[j..i]. For queries L, R that ends in i find maximum on range from L to R.
Online solution: use persistent segment tree with lazy propagation.

EXPLANATION:

SUBTASK 1

Let’s dp_{i,j}~- answer for subarray A[i..j], using that we can answer the queries in O(1).

We can precalculate this array in O(N^2). Initial value of dp_{i,j} is the number of maximum changes on prefices of subarray A[i..j]. Notice, that initially dp_{i,j} \leq dp_{i,j+1}. After that we can make transitions: dp_{i,j}=max(dp_{i,j}, dp_{i+1,j}).

Time complexity is O(N^2+Q).

SUBTASK 2

Suppose that A_0=\infty (very big number).
For each position i find the largest 0 \leq j \leq i such that A_j \geq A_i using stack in O(N). Let’s call this value pos_i.

Process queries offline. For each query (L_i,R_i) add pair (L_i,i) to some vector for position R_i. Iterate i from 1 to N. For each j (1 \leq j \leq i) maintain the number of maximum changes on subarray A[j..i], call this value as val_j. Then if we stay at i, we must add +1 in array val on range from pos_i+1 to i. We can do it using segment tree with lazy propagation. After that process queries at position i, for each pair (R_j, j) the answer is maximum on range from L_j to i in array val (using segment tree).

Time complexity is O((N+Q)logN).

SUBTASK 3

Do the same as in previous subtask, but using persistent segment tree with lazy propagation (online queries). E.g root_i contains segment tree for val[1..i] at state-position i. After that for each query (L,R) the answer is maximum on range from L to R in root_R.

Time complexity is O((N+Q)logN).

SOLUTIONS:

Setter's Solution, first subtask
#include<bits/stdc++.h>
using namespace std;


const int N = 1e3 + 5;


int n, m, a[N], dp[N][N];


int main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t = 1;
    while (t--) {
        int n, m, s;
        cin >> n >> m >> s;
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
        }
        for(int i = 1; i <= n; i++){
            int cur = 0, mx = 0;
            for(int j = i; j <= n; j++){
                if(a[j] > mx){
                    mx = a[j];
                    cur++;
                }
                dp[i][j] = cur;
            }
        }
        for(int sz = 2; sz <= n; sz++){
            for(int i = 1; i + sz - 1 <= n; i++){
                int j = i + sz - 1;
                dp[i][j] = max(dp[i][j], dp[i + 1][j]);
            }
        }
        int lst = 0;
        for (int i = 1; i <= m; i++) {
            int l, r;
            cin >> l >> r;
            l = (l + s * 1LL * lst - 1) % n + 1;
            r = (r + s * 1LL * lst - 1) % n + 1;
            if(l > r) swap(l, r);
            cout << (lst = dp[l][r]) << "\n";
        }
    }
}
Setter's Solution, second subtask
#include<bits/stdc++.h>
using namespace std;


const int N = 1e5 + 5;


int n, m, a[N], ans[N], t[4 * N], ob[4 * N];
vector < pair < int, int > > q[N];

void bld(int v, int l, int r) {
    t[v] = ob[v] = 0;
    if (l == r) return;
    int mid = (r + l) >> 1;
    bld(v + v, l, mid);
    bld(v + v + 1, mid + 1, r);
}
void push(int v) {
    if (ob[v]) {
        ob[v + v] += ob[v];
        t[v + v] += ob[v];
        ob[v + v + 1] += ob[v];
        t[v + v + 1] += ob[v];
        ob[v] = 0;
    }
}

void update(int v, int l, int r, int tl, int tr) {
    if (l > r || l > tr || tl > r) {
        return;
    }
    if (tl <= l && r <= tr) {
        t[v] += 1;
        ob[v] += 1;
        return;
    }
    push(v);
    int mid = (r + l) >> 1;
    update(v + v, l, mid, tl, tr);
    update(v + v + 1, mid + 1, r, tl, tr);
    t[v] = max(t[v + v], t[v + v + 1]);
}

int get(int v, int l, int r, int tl, int tr) {
    if (l > r || l > tr || tl > r) {
        return 0;
    }
    if (tl <= l && r <= tr) {
        return t[v];
    }
    push(v);
    int mid = (r + l) >> 1;
    return max(get(v + v, l, mid, tl, tr), get(v + v + 1, mid + 1, r, tl, tr));
}

int main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t = 1;
    while (t--) {
        int s;
        cin >> n >> m >> s;
        bld(1, 1, n);
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
        }
        for (int i = 1; i <= m; i++) {
            int l, r;
            cin >> l >> r;
            if(l > r) swap(l, r);
            q[r].push_back(make_pair(l, i));
        }
        vector < int > st;
        st.push_back(0);
        a[0] = 1e9;
        for (int i = 1; i <= n; i++) {
            while(a[st.back()] < a[i]){
                st.pop_back();
            }
            update(1, 1, n, st.back() + 1, i);
            for (auto it : q[i]) {
                int l = it.first,
                    num = it.second;
                ans[num] = get(1, 1, n, l, i);
            }
            st.push_back(i);
        }
        for (int i = 1; i <= m; i++) {
            cout << ans[i] << "\n";
        }
        for(int i = 1; i <= n; i++){
            q[i].clear();
        }
    }
}
Setter's Solution, third subtask
#include<bits/stdc++.h>
using namespace std;


const int N = 1e5 + 5;


int n, m, s, a[N];

struct item{
    int val, ob;
    item *l, *r;
    item(){
        val = ob = 0;
        l = r = nullptr;
    }
    item(const item* other){
        if(other == nullptr){
            val = ob = 0;
            l = r = nullptr;
        }
        else{
            val = other->val;
            ob = other->ob;
            l = other->l;
            r = other->r;
        }
    }
};


void push(item*& v, int l, int r){
    v->l = new item(v->l);
    v->r = new item(v->r);
    if(v->ob){
        v->val += v->ob;
        if(l < r){
            v->l->ob += v->ob;
            v->r->ob += v->ob;
        }
        v->ob = 0;
    }
}

void update(item*& v, int l, int r, int tl, int tr){
    push(v, l, r);
    if(l > r || tl > r || l > tr){
        return;
    }
    if(tl <= l && r <= tr){
        v->val++;
        v->l->ob++;
        v->r->ob++;
        return;
    }
    int mid = (r + l) >> 1;
    update(v->l, l, mid, tl, tr);
    update(v->r, mid + 1, r, tl, tr);
    v->val = max(v->l->val, v->r->val);
}

int get(item* v, int l, int r, int tl, int tr){
    if(!v) return 0;
    push(v, l, r);
    if(l > r || tl > r || l > tr){
        return 0;
    }
    if(tl <= l && r <= tr){
        return v->val;
    }
    int mid = (r + l) >> 1;
    return max(get(v->l, l, mid, tl, tr), get(v->r, mid + 1, r, tl, tr));
}


item* rt[N];

mt19937 rnd(time(nullptr));
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n >> m >> s;
    vector < int > st;
    st.push_back(0);
    a[0] = 1e9;
    rt[0] = new item();
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        while(a[st.back()] < a[i]){
            st.pop_back();
        }
        rt[i] = new item(rt[i - 1]);
        update(rt[i], 1, n, st.back() + 1, i);
        st.push_back(i);
    }
    int lst = 0;
    while(m--){
        int x, y;
        cin >> x >> y;
        int l = (x + s * 1LL * lst - 1) % n + 1,
            r = (y + s * 1LL * lst - 1) % n + 1;
        if(l > r){
            swap(l, r);
        }
        cout << (lst = get(rt[r], 1, n, l, r)) << "\n";
    }
}

VIDEO EDITORIAL:

4 Likes

This can also be solved with sqrt decomposition and simple segment tree.
Let block_size be K
Time Complexity : O( N*N/K + Q*K*\log_2(N)*\log_2(N) )
Space Complexity : O( N*N/K )
Implementation : https://www.codechef.com/viewsolution/39653517 ( passes in 1.91 secs)
The expression is minimum for K = 25

Idea:

  • We store the answers for all L,R where L is a multiple of K and L<= R <= N.
    Now we can get these answers in O(1).
  • Now for each query [L,R] break the range into two parts [L,M] and [M+1,R] such that M+1 is a multiple of K
  • Length of [L,M] should be as small as possible and hence it will be at most K-1. Now since we have answer for range [M+1,R], the only part left is all when Chef starts his journey in range [L,M].
  • Build a segment tree which can for each query [L1,R1], find the maximum length of increasing sequence starting at index L1 ( That is l=L ). It can be proved that such a sequence will always be unique. So we can build a merge sort kind of tree and answer queries in O( \log_2(N)*\log_2(N) )
13 Likes

So for what max value of K does this logic AC ?

Was this a problem of longest increasing subsequence ? I was getting WA for some when I used LIS algo in my code. Please someone help me regarding this

1 Like

No, It wasn’t the LIS problem. Please read the problem carefully.

I’m hitting my head for 3 days to understand the actual problem statement. How is it different from LIS can you please explain ? I’m new to competitive programming

1 Like

LIS will fail.
Example :
{ 1, 100, 2, 101, 3, 102, 4, 5, 6, 7, 8, 9, 10 }

LIS will give answer = 10 ( 1, 2, 3, …,10)
But you can easily check that answer is 7 ( 4, 5, … ,10)

1 Like

I think maybe upto 40 it will AC. You can verify though.

Consider the array [1, 2, 5, 3, 4]. Here the LIS is [1, 2, 3, 4], But according to
problem if you start with 1 the sequence will be [1, 2, 5].

1 Like

I solved this problem without using segment tree. I just used array and stack, I think the test files was not so strong.
My Solution - https://www.codechef.com/viewsolution/39581726

3 Likes

No, you can’t use LIS concept in this question suppose you chose a sub array 1 2 1000 3 4
So for LIS concept the longest sequence will be (1 2 3 4) but for the question the longest will be (1 2 1000) only as u dont have choice for 1000 to take it or not if you encounter a no. Greater than prev you have to take it . Hope it helps

2 Likes

You could have reported in comments section :stuck_out_tongue:

Thanks guys , I got it now :slight_smile:

Welcome Hitesh!

I used range maximum query and binary lifting to solve this problem, the main idea is the following.

If we connect each element to its next greater element with an edge; and those which don’t have a next greater element to a universal root, we get a rooted tree. Observe that the indices of the array act as exit numbers in the rooted tree.

Now the queries become, given the two exit numbers, find the maximum length of a chain.

Now the nodes between two exit numbers contain some(possibly zero) entire subtrees and at most one partial subtree. We use Range Maximum query for the entire subtrees and Binary Lifting for the partial subtrees.

my code: https://www.codechef.com/viewsolution/39388922

6 Likes

This can be done with range max segment tree + stack + next greater element.

1 Like

I did exactly this too, was going to post it here but saw your comment. :slight_smile: In my case I used constant of 330, but I suspect many other values work too - it essentially got accepted on a very first attempt of choosing this constant.

Here’s my submission in case anyone wants to take a look - https://www.codechef.com/viewsolution/39526398.

1 Like

I did not understand this part, Please someone explain this part.
Btw the problem is very good.

This post was flagged by the community and is temporarily hidden.

@llaki10 I really did not expect anyone using this approach :stuck_out_tongue:
But you have used it ! :slight_smile: :handshake: