[ABC248Ex] Beautiful Subsequences Solution

更好的阅读体验戳此进入

题面

给定排列 $P_n$$P_n$ 和整数 $k$$k$，求满足如下条件的点对 $(l,r)$$(l, r)$ 数量。

• $1\le l\le r\le n$$1 \le l \le r \le n$。
• $\underset{i=l}{\overset{r}{max}}{P}_i-\underset{i=l}{\overset{r}{min}}{P}_i\le r-l+k$$\max_{i = l}^rP_i - \min_{i = l}^rP_i \le r - l + k$。

Solution

首先为了方便我们令 $mx=\underset{i=l}{\overset{r}{max}}{P}_i,mn=\underset{i=l}{\overset{r}{min}}{P}_i$$mx = \max_{i = l}^rP_i, mn = \min_{i = l}^rP_i$，原式转化为 $mx-mn\le r-l+k$$mx - mn \le r - l + k$，发现 $k\in [0,3]$$k \in [0, 3]$，所以可以考虑将不等式转化为等式，枚举 $k$$k$，对于每个 $k$$k$，合法方案满足 $mx-mn=r-l+k$$mx - mn = r - l + k$。于是原式可以转化为对于每个 $r\in [1,n]$$r \in [1, n]$，求满足 $l\in [1,r],k\in [0,K],l+mx-mn=r+k$$l \in [1, r], k \in [0, K], l + mx - mn = r + k$ 的个数，此时 $l,r,k$$l, r, k$ 均为固定的，所以我们只需要求出此时的区间 $max,min$$\max, \min$，即可确定是否合法。换句话说，对于枚举的 $r$$r$，要找其左侧所有点的 $l+mx-mn$$l + mx - mn$ 的值与 $r+k$$r + k$ 相等的个数。

于是到此问题可转化为，求区间最大值最小值，然后再求区间等于 $r$$r$ 的数量。对于求区间最大值最小值，这个东西我们发现求的是对于每个 $r$$r$ 的所有后缀最大最小值，这个东西用单调栈维护即可。具体地，对于一个新的值，显然其只有可能更新它前面的点的最值，其自己在第一次插入的时候后缀的区间为 $[i,i]$$[i, i]$，最值显然均为 $a_i$$a_i$，但是这个时候我们却不需要更新最值，因为我们要的值是 $mx-mn$$mx - mn$，既然最值相同那么这个东西为 $0$$0$，所以可以忽略。然后对于一个新的值，要去尝试更新前面值的最值，如对于最大值需要维护单调递减的栈，即栈顶最小，如果新的值更小直接丢到栈上，否则更新栈顶和次栈顶之间区间的最大值。把这些维护完之后直接求所有值为 $r$$r$ 的点即可。

然后考虑如何维护区间等于 $r+k$$r + k$ 的个数，有一个比较好想的就是维护一棵线段树，对于每个节点都维护一个 basic_string < pair < int, int > >，存储对应值有多少个，合并的时候直接把两个加起来即可，然后去个重。同时此时查询的时候可以不用枚举 $k$$k$，直接找 $r+k$$r + k$ 大于等于对应值即可。以此我们便可很直观地写出如下实现，但是这个是错误的。

Code

134
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.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

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

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

22
#define MAXN (150000)
23

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

27
int N, K;
28
int val[MAXN];
29

30
struct MyPair{
31
    int first, second;
32
    friend const bool operator < (const MyPair &a, const MyPair &b){
33
        return a.first == b.first ? a.second < b.second : a.first < b.first;
34
    }
35
};
36

37
struct Node{
38
    basic_string < MyPair/*val, cnt*/ > vals;
39
    int lz;
40
    Node operator = (const Node &b){
41
        this->vals = b.vals;
42
        this->lz = b.lz;
43
        return *this;
44
    }
45
    friend const Node operator + (const Node &a, const Node &b){
46
        Node ret{a.vals + b.vals, 0};
47
        sort(ret.vals.begin(), ret.vals.end());
48
        for(auto it = ret.vals.begin(); next(it) != ret.vals.end();)
49
            if(it->first == next(it)->first)next(it)->second += it->second, it = ret.vals.erase(it);
50
            else advance(it, 1);
51
        return ret;
52
    }
53
    friend Node operator += (Node &a, const int &val){
54
        for(auto &nod : a.vals)nod.first += val;
55
        a.lz += val;
56
        return a;
57
    }
58
};
59
class SegTree{
60
private:
61
    Node tr[MAXN << 2];
62
    #define LS (p << 1)
63
    #define RS (LS | 1)
64
    #define MID ((gl + gr) >> 1)
65
public:
66
    void Pushup(int p){tr[p] = tr[LS] + tr[RS];}
67
    void Pushdown(int p){
68
        if(!tr[p].lz)return;
69
        tr[LS].lz = tr[RS].lz = tr[p].lz;
70
        tr[LS] += tr[p].lz, tr[RS] += tr[p].lz;
71
        tr[p].lz = 0;
72
    }
73
    void Build(int p = 1, int gl = 1, int gr = N){
74
        if(gl == gr)return tr[p].vals += {gl = gr, 1}, void();
75
        Build(LS, gl, MID), Build(RS, MID + 1, gr);
76
        Pushup(p);
77
    }
78
    void Modify(int l, int r, int val, int p = 1, int gl = 1, int gr = N){
79
        if(l <= gl && gr <= r)return tr[p] += val, void();
80
        Pushdown(p);
81
        if(l <= MID)Modify(l, r, val, LS, gl, MID);
82
        if(r >= MID + 1)Modify(l, r, val, RS, MID + 1, gr);
83
        Pushup(p);
84
    }
85
    Node Query(int l, int r, int p = 1, int gl = 1, int gr = N){
86
        if(l <= gl && gr <= r)return tr[p];
87
        Pushdown(p);
88
        if(l > MID)return Query(l, r, RS, MID + 1, gr);
89
        if(r < MID + 1)return Query(l, r, LS, gl, MID);
90
        return Query(l, r, LS, gl, MID) + Query(l, r, RS, MID + 1, gr);
91
    }
92
}st;
93
ll Cal(int R){
94
    ll ret(0);
95
    auto vals = st.Query(1, R).vals;
96
    //r + k >= l + max - min
97
    for(auto nod : vals)if(R + K >= nod.first)ret += nod.second;
98
    return ret;
99
}
100

101
int mx[MAXN]/*Query Min*/, mn[MAXN]/*Query Max*/;
102
int mxp(0), mnp(0);
103

104
int main(){
105
    N = read(), K = read();
106
    for(int i = 1; i <= N; ++i)val[i] = read();
107
    st.Build();
108
    ll ans(0);
109
    for(int R = 1; R <= N; ++R){
110
        while(mxp && val[R] > val[mx[mxp]])st.Modify(mx[mxp - 1] + 1, mx[mxp], val[R] - val[mx[mxp]]), --mxp;
111
        while(mnp && val[R] < val[mn[mnp]])st.Modify(mn[mnp - 1] + 1, mn[mnp], val[mn[mnp]] - val[R]), --mnp;
112
        mx[++mxp] = mn[++mnp] = R;
113
        ans += Cal(R);
114
        // printf("R = %d, Cal = %lld\n", R, Cal(R));
115
    }printf("%lld\n", ans);
116
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
117
    return 0;
118
}
119

120
template < typename T >
121
inline T read(void){
122
    T ret(0);
123
    int flag(1);
124
    char c = getchar();
125
    while(c != '-' && !isdigit(c))c = getchar();
126
    if(c == '-')flag = -1, c = getchar();
127
    while(isdigit(c)){
128
        ret *= 10;
129
        ret += int(c - '0');
130
        c = getchar();
131
    }
132
    ret *= flag;
133
    return ret;
134
}

不过这个东西我们简单分析以下复杂度就会发现，每次合并和修改之后的 Pushup 都会使其重构然后耗费大量时间，所以最后复杂度是 $O(\mathtt{\text{玄学}})$$O(\texttt{玄学})$ 的，提交后就会发现 AT 上只能过十多个点。。感觉复杂度直接退化到暴力了。

然后对于 basic_string < pair < int, int > > 还有个很严重的问题，对于一般的 C++14 及以下都不会有任何问题，但是在 C++17 之后，因为 basic_string.h 中有如下语段：

3
1
#if __cplusplus >= 201703L
2
# include <string_view>
3
#endif

然而引入的这个头文件中还存在如下语句：

1
1
static_assert(is_trivial_v<_CharT> && is_standard_layout_v<_CharT>);

此时我们发现，这东西会 CE！测试后发现如下语段会输出 $0$$0$：

1
1
cout << is_trivial < pair< int, int > >::value << endl;

众所周知 is_trivial 一般就是用于判断类型的构造函数是否为默认构造函数，而 pair 的构造函数似乎是用初始化列表写的，可能是因为这个原因，就会导致其无法通过这个 assert，于是就寄了。然而 AT 上默认的不知道是 C++17 还是 20 或者更高，所以无法过编。这个或许可以通过一些高妙的方式解决，但是我不会，于是考虑自定义一个结构体实现跟 pair 一样但是使用默认构造函数即可。

所以话说回来，这个做法本身就是错误的，于是现在我们考虑正解：

思考什么东西比较好维护区间最值和区间等于 $x$$x$ 的数量，不难想到分块，维护的方式和上面说的差不多，只是用分块替换线段树即可，这个东西的复杂度就是 $O(kn\sqrt{n})$$O(k n \sqrt{n})$，可以通过，似乎也是官方正解，但是我不太喜欢分块这个复杂度不够优秀，所以这里就不给代码实现了，我们考虑一些更优秀的做法。

考虑分治，思路来自机房大佬 @sssmzy，发现对于每一个区间，如果我们令 $l\in [L,mid],r\in [mid+1,R]$$l \in [L, mid], r \in [mid + 1, R]$ 是可以快速维护答案的，于是我们只需要以此为基础，计算完答案后分别二分下去即可。

具体地，对于维护答案的过程，我们发现最大值和最小值的位置无法确定，所以考虑枚举最大值在左侧或右侧，以左侧为例子，我们按照类似猫树的思想，从 $mid$$mid$ 向两侧维护后/前缀最值，不难想到，以前缀最大值为例，显然扩展时最大值是单调不降的，最小值同理，然而我们需要让最大值取在左侧，那么显然存在一个分割点 $sp1$$sp1$，在其左的右侧点是合法的，同时也存在一个分割点 $sp2$$sp2$，满足在其左的点最小值取左侧，其右的取右侧，然后发现这个东西是单调的，所以可以直接双（三）指针，枚举 $l$$l$，考虑 $sp1,sp2$$sp1, sp2$，同时维护桶记录所有可能的合法的值的数量。然后讨论 $r$$r$ 位置与分割点的关系，如果在 $[mid+1,min(sp1,sp2)]$$[mid + 1, \min(sp1, sp2)]$ 那么显然此时最大最小值都在左侧，也就是此时确定 $k$$k$ 之后直接就有 $r=l+mx-mn-k$$r = l + mx - mn - k$，判断 $\mathtt{\text{RHS}}$$\texttt{RHS}$ 是否在范围内即可。否则在 $(sp1,sp2]$$(sp1, sp2]$ 之间的话，最大值在左侧和 $l$$l$ 相关，最小值在右侧和 $r$$r$ 相关，此时有 $r-mn=l+mx-k$$r - mn = l + mx - k$，同样将对应 $\mathtt{\text{RHS}}$$\texttt{RHS}$ 的桶加上即可。然后再考虑 $mx$$mx$ 再右侧同理算一遍即可，注意此时因为索引可能为负，所以需要加个 $n$$n$ 转正。

当前区间算完之后二分下去分别求解即可，这样最终复杂度 $O(kn\log n)$$O(k n \log n)$，跑得飞快。

Code

87
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.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

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

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

22
#define MAXN (150000)
23

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

27
int N, K;
28
int a[MAXN];
29
ll ans(0);
30
int mx[MAXN], mn[MAXN];
31
int buc[MAXN << 1];
32

33
void Divide(int gl = 1, int gr = N){
34
    if(gl == gr)return ++ans, void();
35
    int MID = (gl + gr) >> 1;
36
    mx[MID] = mn[MID] = a[MID], mx[MID + 1] = mn[MID + 1] = a[MID + 1];
37
    for(int i = MID - 1; i >= gl; --i)mx[i] = max(mx[i + 1], a[i]), mn[i] = min(mn[i + 1], a[i]);
38
    for(int i = MID + 2; i <= gr; ++i)mx[i] = max(mx[i - 1], a[i]), mn[i] = min(mn[i - 1], a[i]);
39
    int sp1(MID), sp2(MID);
40
    for(int l = MID; l >= gl; --l){
41
        while(sp1 + 1 <= gr && mx[sp1 + 1] <= mx[l])++sp1, buc[sp1 + mn[sp1]]++;
42
        while(sp2 + 1 <= gr && mn[sp2 + 1] >= mn[l])++sp2, buc[sp2 + mn[sp2]]--;
43
        for(int k = 0; k <= K; ++k){
44
            int r = l + mx[l] - mn[l] - k;
45
            int idx = l + mx[l] - k;
46
            if(MID + 1 <= r && r <= min(sp1, sp2))++ans;
47
            if(sp2 < sp1 && idx > 0)ans += buc[idx];
48
        }
49
    }for(int i = MID + 1; i <= gr; ++i)buc[i + mn[i]] = 0;
50
    sp1 = MID + 1, sp2 = MID + 1;
51
    for(int r = MID + 1; r <= gr; ++r){
52
        while(sp1 - 1 >= gl && mx[sp1 - 1] <= mx[r])--sp1, buc[sp1 - mn[sp1] + N]++;
53
        while(sp2 - 1 >= gl && mn[sp2 - 1] >= mn[r])--sp2, buc[sp2 - mn[sp2] + N]--;
54
        for(int k = 0; k <= K; ++k){
55
            int l = r - mx[r] + mn[r] + k;
56
            int idx = r - mx[r] + k + N;
57
            if(max(sp1, sp2) <= l  && l <= MID)++ans;
58
            if(sp1 < sp2 && idx > 0)ans += buc[idx];
59
        }
60
    }for(int i = gl; i <= MID; ++i)buc[i - mn[i] + N] = 0;
61
    Divide(gl, MID), Divide(MID + 1, gr);
62
}
63

64
int main(){
65
    N = read(), K = read();
66
    for(int i = 1; i <= N; ++i)a[i] = read();
67
    Divide();
68
    printf("%lld\n", ans);
69
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
70
    return 0;
71
}
72

73
template < typename T >
74
inline T read(void){
75
    T ret(0);
76
    int flag(1);
77
    char c = getchar();
78
    while(c != '-' && !isdigit(c))c = getchar();
79
    if(c == '-')flag = -1, c = getchar();
80
    while(isdigit(c)){
81
        ret *= 10;
82
        ret += int(c - '0');
83
        c = getchar();
84
    }
85
    ret *= flag;
86
    return ret;
87
}

UPD

update-2022_11_22 初稿