CF689D Friends and Subsequences 题解

题目链接：CF689D Friends and Subsequences

题意：

• 给定序列 \(a\) 和序列 \(b\)，长度均为 \(n\)。问有多少组 \((l,r)\)，满足 \(1\le l\le r\le n\) 且 \(\displaystyle \max_{i=l}^r a_i=\min_{i=l}^r b_i\)
• \(1\le n\le 2\times 10^5\)，\(|a_i|,|b_i|\le 10^9\)。

输入格式：

The first line contains only integer \(n\) (\(1\leq n\leq 200000\)).

The second line contains \(n\) integer numbers \(a_{1}, a_{2}, \ldots, a_{n}\) (\(-10^9 \leq a_i \leq 10^9\)) — the sequence \(a\).

The third line contains \(n\) integer numbers \(b_{1}, b_{2}, \ldots, b_{n}\) (\(-10^9 \leq b_i \leq 10^9\)) — the sequence \(b\).

输出格式：

Print the only integer number — the number of occasions the robot will count, thus for how many pairs \(\displaystyle \max _{i=l}^r a_i=\min _{i=l}^r b_i\) is satisfied.

注意到当左端点固定时，\(a\) 最大值减 \(b\) 最小值的差会单调不降。

容易想到这样的做法：枚举合法区间的左端点，然后二分一个右端点。然而这个做法是错的。

假设 \([l,r]\) 是一个极大合法的区间，且区间 \([p,l-1]\) 不合法。而此时 \([p,l]\) 却可能是一个合法区间。

于是考虑枚举左端点 \(l\) ，接着做两个二分，得到以 \(l\) 为左端点的极大合法区间的范围 \([l^{\prime},r^{\prime}]\) ，

则对于任意整数 \(x \in [l^{\prime}, r^{\prime}]\) ，区间 \([l,x]\) 为合法区间，并且 \(l^{\prime}\) 是最左侧的那个，\(r^{\prime}\) 是最右侧的那个。

实现的话，因为不带修改，所以可以用 ST表 解决，线段树二分有空再写吧。

时间复杂度 \(\mathcal{O}(n \log n)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(2e5 + 5))
#define LN 20

int n,res,lg[N],f1[LN][N],f2[LN][N];
int qmax(int l,int r)
{
    int k = lg[r - l + 1];
    return max(f1[k][l], f1[k][r - (1 << k) + 1]);
}
int qmin(int l,int r)
{
    int k = lg[r - l + 1];
    return min(f2[k][l], f2[k][r - (1 << k) + 1]);
}
int ql(int i)
{
    int l = i, r = n;
    while(l < r)
    {
        int mid = (l + r + 1) >> 1;
        if(qmax(i,mid) <= qmin(i,mid)) l = mid;
        else r = mid - 1;
    }
    if(l <= n && qmax(i,l) == qmin(i,l)) return l;
    return 0;
}
int qr(int i)
{
    int l = i, r = n;
    while(l < r)
    {
        int mid = (l + r) >> 1;
        if(qmax(i,mid) >= qmin(i,mid)) r = mid;
        else l = mid + 1;
    }
    if(r > 0 && qmax(i,r) == qmin(i,r)) return r;
    return 0;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n;
    for(int i = 2; i <= n; i++) lg[i] = lg[i >> 1] + 1;
    for(int i = 1; i <= n; i++) cin >> f1[0][i];
    for(int i = 1; i <= n; i++) cin >> f2[0][i];
    for(int j = 0; 1 << (j + 1) <= n; j++)
    {
        int *f = f1[j], *g = f1[j + 1];
        for(int i = 1; i + (1 << j) - 1 <= n; i++)
            g[i] = max(f[i], f[i + (1 << j)]);
        f = f2[j], g = f2[j + 1];
        for(int i = 1; i + (1 << j) - 1 <= n; i++)
            g[i] = min(f[i], f[i + (1 << j)]);
    }
    for(int i = 1; i <= n; i++)
    {
        int l = ql(i), r = qr(i);
        if(!l || !r) continue; if(l > r) swap(l,r);
        res += (r - l + 1);
    }
    cout << res << '\n';
    return 0;
}