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;
}