题解 CF689D Friends and Subsequences

发表于 分类于 阅读次数： Valine： 本文字数： 2k 阅读时长 ≈ 2 分钟

在这里介绍一个防止二分写挂的神仙方法（今天教练介绍的2333

我们先枚举一个左端点，发现随着右端点的增长，min⁡\min 值单调递减，max⁡\max 值单调递增。

于是可以二分一下这个右端点的可能区间。具体就二分一下右端点区间的左端和右端点区间的右端即可。使用 ST 表优化查询区间 min⁡\min、max⁡\max 值的速度。

但是，这个二分很容易写挂！

怎么办？

我们索性不考虑二分的边界啥的，在 ll 与 rr 距离很小的时候就跳出二分，然后暴力地在这个 ll 和 rr 之间找一下即可！

这样可以减少很多细节的考虑！方便考场调试代码！

具体见代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
const int N=2e5+5;
int n,a[N],b[N];
int mn[N][22],mx[N][22];
signed main() {
    scanf("%lld",&n);
    rep(i,1,n) scanf("%lld",&a[i]),mx[i][0]=a[i];
    rep(i,1,n) scanf("%lld",&b[i]),mn[i][0]=b[i];
    rep(j,1,21) {
        rep(i,1,n) {
            if(i+(1<<(j-1))-1>n) mx[i][j]=mx[i][j-1];
            else mx[i][j]=max(mx[i][j-1],mx[i+(1<<(j-1))][j-1]);
        }
    }
    rep(j,1,21) {
        rep(i,1,n) {
            if(i+(1<<(j-1))-1>n) mn[i][j]=mn[i][j-1];
            else mn[i][j]=min(mn[i][j-1],mn[i+(1<<(j-1))][j-1]);
        }
    }
    int ans=0;
    rep(i,1,n) {
        int l=i,r=n;
        int rr=0,ll=0;
        while(r-l>5) {
            int mid=(l+r)>>1;
            //printf("de:%lld %lld %lld\n",l,r,mid);
            int lg=log2(mid-i+1);
            int mxx=max(mx[i][lg],mx[mid-(1<<lg)+1][lg]);
            int mnn=min(mn[i][lg],mn[mid-(1<<lg)+1][lg]);
            if(mxx>mnn) r=mid;
            else l=mid;
        }
        per(j,r,l) {
            int lg=log2(j-i+1);
            int mxx=max(mx[i][lg],mx[j-(1<<lg)+1][lg]);
            int mnn=min(mn[i][lg],mn[j-(1<<lg)+1][lg]);
            if(mxx==mnn) {rr=j;break;}
        }
        l=i,r=n;
        while(r-l>5) {
            int mid=(l+r)>>1;
            int lg=log2(mid-i+1);
            int mxx=max(mx[i][lg],mx[mid-(1<<lg)+1][lg]);
            int mnn=min(mn[i][lg],mn[mid-(1<<lg)+1][lg]);
            if(mxx>=mnn) r=mid;
            else l=mid;
        }
        rep(j,l,r) {
            int lg=log2(j-i+1);
            int mxx=max(mx[i][lg],mx[j-(1<<lg)+1][lg]);
            int mnn=min(mn[i][lg],mn[j-(1<<lg)+1][lg]);
            if(mxx==mnn) {ll=j;break;}
        }
        if(ll&&rr) ans+=(rr-ll+1);
    }
    printf("%lld",ans);
	return 0;
}