codeforces 689D (二分 RMQ)

題目連結：點選這裡

題意：給出兩個數列， 有多少對[l,r]滿足 max{al,al+1...ar}=min{bl,bl+1...br}

如果固定一個左端點，max數組是遞增的，min是遞減的， 那麼需要尋找一段右端點使得區間的max-min等于0. 這個可以通過枚舉下标然後rmq詢問最大最小得到。因為rmq預處理之後的詢問是O(1)的，是以總複雜度是O(nlgn)。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <map>
using namespace std;

#define maxn 200005
int n;
int a[maxn], b[maxn];
int dp1[maxn][], dp2[maxn][];

void rmq_init () {
    for (int i = ; i < n; i++) dp1[i][] = a[i];
    for (int j = ; (<<j) <= n; j++) {
        for (int i = ; i+(<<j)- < n; i++) {
            dp1[i][j] = max (dp1[i][j-], dp1[i+(<<(j-))][j-]);
        }
    }
    for (int i = ; i < n; i++) dp2[i][] = b[i];
    for (int j = ; (<<j) <= n; j++) {
        for (int i = ; i+(<<j)- < n; i++) {
            dp2[i][j] = min (dp2[i][j-], dp2[i+(<<(j-))][j-]);
        }
    }
}

int rmq_max (int l, int r) {
    int k = ;
    while ((<<(k+)) <= r-l+) k++;
    return max (dp1[l][k], dp1[r-(<<k)+][k]);
}

int rmq_min (int l, int r) {
    int k = ;
    while ((<<(k+)) <= r-l+) k++;
    return min (dp2[l][k], dp2[r-(<<k)+][k]);
}

void solve () {
    rmq_init ();
    long long ans = ;
    for (int i = ; i < n; i++) {
        int l = i, r = n-;
        while (r-l > ) {
            int mid = (l+r)>>;
            if (rmq_min (i, mid)- rmq_max (i, mid) > ) l = mid;
            else r = mid;
        }
        int L;
        if (rmq_min (i, l) - rmq_max (i, l) == ) L = l;
        else if (rmq_min (i, r) - rmq_max (i, r) == ) L = r;
        else continue;
        l = i, r = n-;
        while (r-l > ) {
            int mid = (l+r)>>;
            if (rmq_min (i, mid) - rmq_max (i, mid) < ) r = mid;
            else l = mid;
        } 
        int R;
        if (rmq_min (i, r) - rmq_max (i, r) == ) R = r;
        else if (rmq_min (i, l) - rmq_max (i, l) == ) R = l;
        else continue;
        ans += (R-L+);
    }
    cout << ans << endl;
}

int main () {
    cin >> n;
    for (int i = ; i < n; i++) cin >> a[i];
    for (int i = ; i < n; i++) cin >> b[i];
    solve ();
    return ;
}