ABC247E Max Min Solution

更好的阅读体验戳此进入

题面

给定数列 $A_n$$A_n$，给定 $X,Y$$X, Y$，我们定义数对 $(L,R)$$(L, R)$ 满足 $1\le L\le R\le n$$1 \le L \le R \le n$，且数列 $A_L,A_{L+1},\cdots ,A_R$$A_L, A_{L + 1}, \cdots, A_R$ 满足最大值为 $X$$X$，最小值为 $Y$$Y$，求有多少种满足条件的数对。

Solution

关于本题有一些较为显然的 $O(n{\log }^{2}n)$$O(n \log ^2 n)$ 或 $O(n\log n)$$O(n \log n)$ 或 $O(n)$$O(n)$ 的做法，前两个大概对应着树套树和线段树，然后后者大概是维护前一个等于 $X$$X$ 等于 $Y$$Y$，在 $(X,Y)$$(X, Y)$ 之间的啊等等一堆东西然后跑一遍，这里就不多赘述了，网上相关做法很多。这里主要提供一个机房巨佬 @Zpair 想出来的人类智慧容斥的做法与推导。

首先我们考虑这段区间里一定不能包含在 $(-\mathrm{\infty },Y)\cup (X,+\mathrm{\infty })$$(-\infty, Y) \cup (X, +\infty)$ 内的数，所以我们考虑让所有在这个区间内的数作为分割点，这样最终会让我们的序列被分成很多个子序列，这里我们不难发现，合法的区间一定不会有跨越两个子区间的，一定都是在子区间内的子子区间。

所以这时候我们只需要对于每个划分出来的子区间考虑其中的合法区间即可，不难想到我们要找的区间合法当且仅当里面包含了至少一个 $X$$X$ 和至少一个 $Y$$Y$，为了方便记录这里我们令等于 $X$$X$ 的点为 $1$$1$，等于 $Y$$Y$ 的点为 $-1$$-1$，在 $(X,Y)$$(X, Y)$ 之间的点为 $0$$0$，也就是我们要找的就是每个子区间里包含 $-1$$-1$ 和 $1$$1$ 的区间由多少个。这里我们令包含 $1$$1$ 的区间的集合为 $A$$A$，包含 $-1$$-1$ 的为 $B$$B$，令子区间内的所有区间的集合为 $\mathrm{\Omega }$$\Omega$，不难想到我们比较好求的是，不包含 $1$$1$ 和 $-1$$-1$ 的区间，不包含 $1$$1$ 的区间，不包含 $-1$$-1$ 的区间，以及全集，分别对应着 $\bar{A}\cap \bar{B}$$\overline{A} \cap \overline{B}$，$\bar{A}$$\overline{A}$，$\bar{B}$$\overline{B}$，$\mathrm{\Omega }$$\Omega$。我们的目标是求出 $A\cap B$$A \cap B$，所以我们希望通过前面的四个求出答案，不难想到如下推导：

此时考虑如何维护这四个值，显然我们可以考虑把子区间再次进行分割，遍历三次，分别由 $1$$1$ 分割，由 $-1$$-1$ 分割，由 $-1$$-1$ 或 $1$$1$ 分割，也就分别对应着式子中的三个区间的大小，然后对于每个子区间维护一遍即可，最后就是一个大常数的线性求解。

然后还有个点就是如果 $X=Y$$X = Y$ 的话那么其实际上是既是 $1$$1$ 又是 $-1$$-1$，需要特判一下。

Code

xxxxxxxxxx
93
1
#define _USE_MATH_DEFINES
2
#include <bits/extc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
10

11
using namespace std;
12
using namespace __gnu_pbds;
13

14
mt19937 rnd(random_device{}());
15
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
16
bool rnddd(int x){return rndd(1, 100) <= x;}
17

18
typedef unsigned int uint;
19
typedef unsigned long long unll;
20
typedef long long ll;
21
typedef long double ld;
22

23
template< typename T = int >
24
inline T read(void);
25

26
int N, X, Y;
27
int a[210000];
28
int cnt0(0), cnt1(0), cnt_1(0), l(1), r(-1);
29
ll ans(0);
30

31
ll GetC(int n, int m){
32
    if(n == 1)return 1;
33
    if(!n || m > n)return 0;
34
    ll ret(1);
35
    for(int i = n; i >= n - m + 1; --i)ret *= i;
36
    for(int i = m; i >= 1; --i)ret /= i;
37
    return ret + n;
38
}
39

40
int main(){
41
    N = read(), X = read(), Y = read();
42
    for(int i = 1; i <= N + 1; ++i){
43
        a[i] = i <= N ? read() : INT_MAX;
44
        a[i] = a[i] == X && a[i] == Y ? -114514 : (a[i] == X ? 1 : (a[i] == Y ? -1 : (Y <= a[i] && a[i] <= X ? 0 : 114514)));
45
        if(a[i] != 114514){r = i; continue;}
46
        if(!~r){l = i + 1; continue;}
47
        ll cur(0);
48
        cur += GetC(r - l + 1, 2);
49
        int ll(l), rr(-1);
50
        for(int j = l; j <= r; ++j){
51
            if(a[j] != -1 && a[j] != -114514){rr = j; continue;}
52
            if(!~rr){ll = j + 1; continue;}
53
            cur -= GetC(rr - ll + 1, 2);
54
            ll = j + 1;
55
        }if(ll <= rr)cur -= GetC(rr - ll + 1, 2);
56
        ll = l, rr = -1;
57
        for(int j = l; j <= r; ++j){
58
            if(a[j] != 1 && a[j] != -114514){rr = j; continue;}
59
            if(!~rr){ll = j + 1; continue;}
60
            cur -= GetC(rr - ll + 1, 2);
61
            ll = j + 1;
62
        }if(ll <= rr)cur -= GetC(rr - ll + 1, 2);
63
        ll = l, rr = -1;
64
        for(int j = l; j <= r; ++j){
65
            if(!a[j]){rr = j; continue;}
66
            if(!~rr){ll = j + 1; continue;}
67
            cur += GetC(rr - ll + 1, 2);
68
            ll = j + 1;
69
        }if(ll <= rr)cur += GetC(rr - ll + 1, 2);
70
        ans += cur;
71
        l = i + 1;
72
    }
73
    printf("%lld\n", ans);
74

75
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
76
    return 0;
77
}
78

79
template < typename T >
80
inline T read(void){
81
    T ret(0);
82
    short flag(1);
83
    char c = getchar();
84
    while(c != '-' && !isdigit(c))c = getchar();
85
    if(c == '-')flag = -1, c = getchar();
86
    while(isdigit(c)){
87
        ret *= 10;
88
        ret += int(c - '0');
89
        c = getchar();
90
    }
91
    ret *= flag;
92
    return ret;
93
}

然后因为我是完全按照这个思路实现的所以上面的可能非常丑，所以这里也贴一个 @Zpair 的优美实现。

xxxxxxxxxx
18
1
#include<bits/stdc++.h>
2
using namespace std;
3
typedef long long ll;
4
int l1,l2,l3,l4,n,x,y;ll ans;
5
ll get(int x){return (ll)x*(x+1)/2;}
6
int main(){
7
    cin>>n>>x>>y;int v;
8
    for(int i=1;i<=n;++i){
9
        scanf("%d",&v);
10
        if(v>x||v<y){ans+=get(l1)-get(l2)-get(l3)+get(l4),l1=l2=l3=l4=0;continue;}
11
        if(v!=x&&v!=y)l1++,l2++,l3++,l4++;
12
        if(v==x&&v==y)l1++,ans+=-get(l2)-get(l3)+get(l4),l2=l3=l4=0;
13
        if(v==x&&v!=y)l1++,l3++,ans+=-get(l2)+get(l4),l2=l4=0;
14
        if(v!=x&&v==y)l1++,l2++,ans+=-get(l3)+get(l4),l3=l4=0;
15
    }
16
    ans+=get(l1)-get(l2)-get(l3)+get(l4);
17
    cout<<ans;
18
}

UPD

update-2022_10_24 初稿