Tutorial for Codeforces - Friends and Subsequences

Solution #

The key observation is that if we fix $l$ then we have $\max_{i=l}^ra_i-\min_{i=l}^r b_i\leq \max_{i=l}^{r+1}a_i-\min_{i=l}^{r+1} b_i$ . So we can use binary search to find the min and the max value $r$ such that $\max_{i=l}^r a_i=\min_{i=l}^r b_i$ and add max-min+1 to the answer. We need a RMQ data structure and sparse table can do this in $O(1)$ per query.

Also this can be done using monotone queue but I haven’t figured it out.

Code #

#include <bits/stdc++.h>
 
using namespace std;
using ll=long long;
 
struct sparse{
    int logn;
    vector<vector<int>> f,g;
    sparse(int n){
        logn=__lg(n);
        f=g=vector(n,vector(logn+1,0));
        for(int i=0;i<n;i++) cin>>f[i][0];
        for(int i=0;i<n;i++) cin>>g[i][0];
        for (int j = 1; j <= logn; j++)
            for (int i = 0; i + (1 << j) - 1 < n; i++){
                f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
                g[i][j] = min(g[i][j - 1], g[i + (1 << (j - 1))][j - 1]);
            }
    }
    int geta(int x,int y){
        int s = __lg(y - x + 1);
        return max(f[x][s], f[y - (1 << s) + 1][s]);
    }
    int getb(int x,int y){
        int s = __lg(y - x + 1);
        return min(g[x][s], g[y - (1 << s) + 1][s]);
    }
 
};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    sparse st(n);
    ll ans=0;
    for(int i=0;i<n;i++){
        int l=i,r=n-1;
        while(l<=r){
            int mid=(l+r)/2;
            if(st.geta(i,mid)<st.getb(i,mid)) l=mid+1;
            else r=mid-1;
        }
        int left=r;
        l=i,r=n-1;
        while(l<=r){
            int mid=(l+r)/2;
            if(st.geta(i,mid)<=st.getb(i,mid)) l=mid+1;
            else r=mid-1;
        }
        ans+=r-left;
    }
    cout<<ans;
    return 0;
}