AtCoder Beginner Contest 248 Solution

更好的阅读体验戳此进入

题面链接

题面 Luogu 链接

[ABC248A] Lacked Number

题面

给定字符集为 0-9 数字的字符串，求字符集中没有在字符串中出现的唯一数字。

Solution

语法题。

Code

xxxxxxxxxx
52
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
template< typename T = int >
23
inline T read(void);
24

25
bool vis[10];
26

27
int main(){
28
    for(int i = 1; i <= 9; ++i){
29
        char c = getchar();
30
        while(!isdigit(c))c = getchar();
31
        vis[c - '0'] = true;
32
    }for(int i = 0; i <= 9; ++i)if(!vis[i])printf("%d\n", i), exit(0);
33

34
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
35
    return 0;
36
}
37

38
template < typename T >
39
inline T read(void){
40
    T ret(0);
41
    int flag(1);
42
    char c = getchar();
43
    while(c != '-' && !isdigit(c))c = getchar();
44
    if(c == '-')flag = -1, c = getchar();
45
    while(isdigit(c)){
46
        ret *= 10;
47
        ret += int(c - '0');
48
        c = getchar();
49
    }
50
    ret *= flag;
51
    return ret;
52
}

[ABC248B] Slimes

题面

给定 $a,b,k$$a, b, k$，求最小的 $x$$x$ 使得 $a\times k^x\ge b$$a \times k^x \ge b$，输出 $x$$x$。

Solution

语法题，数据范围不大所以直接浮点数搞一下 $\log$$\log$ 即可。

Code

xxxxxxxxxx
47
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
template< typename T = int >
23
inline T read(void);
24

25
int main(){
26
    int A = read(), B = read(), K = read();
27
    int ans = (int)ceill(log((ld)B / (ld)A) / log((ld)K));
28
    printf("%d\n", ans);
29
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
30
    return 0;
31
}
32

33
template < typename T >
34
inline T read(void){
35
    T ret(0);
36
    int flag(1);
37
    char c = getchar();
38
    while(c != '-' && !isdigit(c))c = getchar();
39
    if(c == '-')flag = -1, c = getchar();
40
    while(isdigit(c)){
41
        ret *= 10;
42
        ret += int(c - '0');
43
        c = getchar();
44
    }
45
    ret *= flag;
46
    return ret;
47
}

[ABC248C] Dice Sum

题面

给定 $n,m,k$$n, m, k$，求满足以下条件的长度为 $n$$n$ 的序列数，对 $998244353$$998244353$ 取模。

• $1\le a_i\le m(1\le i\le n)$$1 \le a_i \le m(1 \le i \le n)$。
• $\sum _{i=1}^n{a}_i\le k$$\sum_{i = 1}^n a_i \le k$。

Solution

数据范围太小，写一个 $\mathtt{\text{3D1D}}$$\texttt{3D1D}$ 的 dp 就行，没啥可说的。

Code

xxxxxxxxxx
59
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 MOD (ll)(998244353)
23

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

27
int N, M, K;
28
ll dp[60][3000];
29

30
int main(){
31
    N = read(), M = read(), K = read();
32
    dp[0][0] = 1;
33
    for(int i = 1; i <= N; ++i)
34
        for(int j = 1; j <= K; ++j)
35
            for(int lst = 1; lst <= M; ++lst)
36
                if(j - lst >= 0)
37
                    (dp[i][j] += dp[i - 1][j - lst]) %= MOD;
38
    ll ans(0);
39
    for(int i = 0; i <= K; ++i)(ans += dp[N][i]) %= MOD;
40
    printf("%lld\n", ans);
41
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
42
    return 0;
43
}
44

45
template < typename T >
46
inline T read(void){
47
    T ret(0);
48
    int flag(1);
49
    char c = getchar();
50
    while(c != '-' && !isdigit(c))c = getchar();
51
    if(c == '-')flag = -1, c = getchar();
52
    while(isdigit(c)){
53
        ret *= 10;
54
        ret += int(c - '0');
55
        c = getchar();
56
    }
57
    ret *= flag;
58
    return ret;
59
}

[ABC248D] Range Count Query

题面

给定序列 $A_n$$A_n$，$Q$$Q$ 次询问求 $[l,r]$$[l, r]$ 中 $a_i=x$$a_i = x$ 的数量。

Solution

值域较小，每个数维护一个出现位置的 basic_string，每次在里面二分两次查左右端点调用一下 distance() 即可。

Code

xxxxxxxxxx
54
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
template< typename T = int >
23
inline T read(void);
24

25
int N, Q;
26
basic_string < int > pos[210000];
27

28
int main(){
29
    N = read();
30
    for(int i = 1; i <= N; ++i)pos[read()] += i;
31
    Q = read();
32
    while(Q--){
33
        int l = read(), r = read(), x = read();
34
        printf("%d\n", (int)distance(lower_bound(pos[x].begin(), pos[x].end(), l), upper_bound(pos[x].begin(), pos[x].end(), r)));
35
    }
36
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
37
    return 0;
38
}
39

40
template < typename T >
41
inline T read(void){
42
    T ret(0);
43
    int flag(1);
44
    char c = getchar();
45
    while(c != '-' && !isdigit(c))c = getchar();
46
    if(c == '-')flag = -1, c = getchar();
47
    while(isdigit(c)){
48
        ret *= 10;
49
        ret += int(c - '0');
50
        c = getchar();
51
    }
52
    ret *= flag;
53
    return ret;
54
}

[ABC248E] K-colinear Line

题面

给一堆点问有多少条直线至少经过了 $k$$k$ 个点。

Solution

数据范围较小，随便枚举一下然后判个重即可。

Code

xxxxxxxxxx
68
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 EPS (double)(1e-8)
23

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

27
int N, K;
28
bool vis[310][310];
29
struct Coord{int x, y;}p[310];
30
int ans(0);
31
bool Check(Coord a, Coord b, Coord c){
32
    // return (abs((double)(b.y - a.y) / (double)(b.x - a.x) - (double)(c.y - b.y) / (double)(c.x - b.x)) <= EPS);
33
    return ((ll)(b.y - a.y) * (c.x - b.x) == (ll)(c.y - b.y) * (b.x - a.x));
34
}
35

36
int main(){
37
    N = read(), K = read();
38
    if(K == 1)printf("Infinity\n"), exit(0);
39
    for(int i = 1; i <= N; ++i)p[i].x = read(), p[i].y = read();
40
    for(int i = 1; i <= N; ++i)
41
        for(int j = i + 1; j <= N; ++j)
42
            if(!vis[i][j]){
43
                basic_string < int > pts; pts += {i, j};
44
                for(int k = 1; k <= N; ++k)
45
                    if(k != i && k != j && Check(p[i], p[j], p[k]))pts += k;
46
                for(auto u : pts)for(auto v : pts)vis[u][v] = true;
47
                if((int)pts.size() >= K)++ans;
48
            }
49
    printf("%d\n", ans);
50
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
51
    return 0;
52
}
53

54
template < typename T >
55
inline T read(void){
56
    T ret(0);
57
    int flag(1);
58
    char c = getchar();
59
    while(c != '-' && !isdigit(c))c = getchar();
60
    if(c == '-')flag = -1, c = getchar();
61
    while(isdigit(c)){
62
        ret *= 10;
63
        ret += int(c - '0');
64
        c = getchar();
65
    }
66
    ret *= flag;
67
    return ret;
68
}

[ABC248F] Keep Connect

题面

给定 $n,p$$n, p$，存在如图的 $2\times n$$2 \times n$ 的网格图，显然初始共有 $2n$$2n$ 个顶点和 $3n-2$$3n - 2$ 条边，分别求删除 $i\in [1,n-1]$$i \in [1, n - 1]$ 条边后仍使图连通的删边方案数，对 $p$$p$ 取模。

Solution

这种题 DP 很显然，考虑设状态 $dp(i,j,0/1)$$dp(i, j, 0/1)$ 表示考虑前 $i$$i$ 列，删除了 $j$$j$ 条边，第 $i$$i$ 列上下两点之间是否连边，然后对不同情况无脑进行分类讨论即可。

具体地，对于 $dp(i,j,0)$$dp(i, j, 0)$，如下图，此时 $i$$i$ 位置两个点竖直方向并未连边，则为了保证连通性，那么 $i$$i$ 到 $i+1$$i + 1$ 的水平的两个边必须连上，而 $i+1$$i + 1$ 的竖直的边（即虚线边）是否连结均合法，则有如下转移：

对于 $dp(i,j,1)$$dp(i, j, 1)$，如下图，三条边都不能直接确定，所以需要继续讨论，具体地，可以讨论 $i+1$$i + 1$ 的竖直边是否连结，简单想一下就有如下 $4$$4$ 个转移，此处不多赘述，直接看方程吧。

同时注意 $\times 2$$\times 2$ 是因为要枚举上下的两个水平边删掉其中一个。

边界可以是 $dp(1,0,1)=dp(1,1,0)=1$$dp(1, 0, 1) = dp(1, 1, 0) = 1$，对应删边数 $d$$d$ 的答案即为 $dp(n,d,1)$$dp(n, d, 1)$。

Code

xxxxxxxxxx
58
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
template< typename T = int >
23
inline T read(void);
24

25
int N; int MOD;
26
int dp[3100][3100][2];
27

28
int main(){
29
    N = read(), MOD = read();
30
    dp[1][0][1] = dp[1][1][0] = 1;
31
    for(int i = 1; i <= N - 1; ++i)
32
        for(int j = 0; j <= N - 1; ++j)
33
            dp[i + 1][j + 1][0] = ((ll)dp[i + 1][j + 1][0] + dp[i][j][0]) % MOD,
34
            dp[i + 1][j][1] = ((ll)dp[i + 1][j][1] + dp[i][j][0]) % MOD,
35
            dp[i + 1][j + 1][1] = ((ll)dp[i + 1][j + 1][1] + dp[i][j][1] * 2ll) % MOD,
36
            dp[i + 1][j][1] = ((ll)dp[i + 1][j][1] + dp[i][j][1]) % MOD,
37
            dp[i + 1][j + 2][0] = ((ll)dp[i + 1][j + 2][0] + dp[i][j][1] * 2ll) % MOD,
38
            dp[i + 1][j + 1][1] = ((ll)dp[i + 1][j + 1][1] + dp[i][j][1]) % MOD;
39
    for(int i = 1; i <= N - 1; ++i)printf("%d%c", dp[N][i][1], i == N - 1 ? '\n' : ' ');
40
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
41
    return 0;
42
}
43

44
template < typename T >
45
inline T read(void){
46
    T ret(0);
47
    int flag(1);
48
    char c = getchar();
49
    while(c != '-' && !isdigit(c))c = getchar();
50
    if(c == '-')flag = -1, c = getchar();
51
    while(isdigit(c)){
52
        ret *= 10;
53
        ret += int(c - '0');
54
        c = getchar();
55
    }
56
    ret *= flag;
57
    return ret;
58
}

[ABC248G] GCD cost on the tree

题面

给定一颗树有 $n$$n$ 个结点，每个结点上有一个权值 $a_i$$a_i$, 对于每条至少包含两个点的简单路径，它的贡献为 路径上点的数量（包括端点）$\times$$\times$ 路径上所有点的 $a_i$$a_i$ 的最大公约数（gcd）。求所有简单路径的贡献之和，对 $998244353$$998244353$ 取模。

Solution

考虑枚举每个子树，无脑搜索所有路径，用 map 存储对于每个路径上的 $gcd$$\gcd$ 作为第一关键字对应的路径长度和和对应的路径数量，存储后者主要为了在路径延申的时候加上对应的数量，然后一个子树完全算完之后往回递归，把这些全都合在一起，整棵树 dfs 一遍即可，最终复杂度 $O({\sigma }^2(a_i)n\log n)$$O(\sigma^2(a_i) n \log n)$。也可以用容斥写，但是会更难写一些。

Code

xxxxxxxxxx
104
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 MOD (ll)(998244353)
23

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

27
struct Edge{
28
    Edge* nxt;
29
    int to;
30
    OPNEW;
31
}ed[210000];
32
ROPNEW(ed);
33
Edge* head[110000];
34

35
int N;
36
ll ans(0);
37
int a[110000];
38
struct Paths{
39
    ll sum, cnt;
40
    friend const Paths operator + (const Paths &a, const Paths &b){
41
        return Paths{(a.sum + b.sum) % MOD, (a.cnt + b.cnt) % MOD};
42
    }
43
    friend Paths operator += (Paths &origin, const Paths &add){
44
        return origin = origin + add;
45
    }
46
};
47

48
ll Cal(const map < int, Paths > &a, const map < int, Paths > &b){
49
    ll ret(0);
50
    for(auto mpa : a)for(auto mpb : b)
51
        (ret += (ll)__gcd(mpa.first, mpb.first) * (
52
            mpa.second.sum * mpb.second.cnt % MOD +
53
            mpa.second.cnt * mpb.second.sum % MOD +
54
            mpa.second.cnt * mpb.second.cnt % MOD
55
        )) %= MOD;
56
    return ret;
57
}
58
auto Extend(const map < int, Paths > &origin, int val){
59
    map < int, Paths > ret;
60
    for(auto mp : origin)ret[__gcd(mp.first, val)] += Paths{mp.second.sum + mp.second.cnt, mp.second.cnt};
61
    return ret;
62
}
63
void Union(map < int, Paths > &origin, const map < int, Paths > add){
64
    for(auto mp : add)origin[mp.first] += mp.second;
65
}
66
map < int, Paths > dfs(int p = 1, int fa = 0){
67
    map < int, Paths > ret;
68
    ret.insert({a[p], Paths{0, 1}});
69
    for(auto i = head[p]; i; i = i->nxt){
70
        if(SON == fa)continue;
71
        auto son = Extend(dfs(SON, p), a[p]);
72
        (ans += Cal(ret, son)) %= MOD;
73
        Union(ret, son);
74
    }return ret;
75
}
76

77
int main(){
78
    N = read();
79
    for(int i = 1; i <= N; ++i)a[i] = read();
80
    for(int i = 1; i <= N - 1; ++i){
81
        int s = read(), t = read();
82
        head[s] = new Edge{head[s], t};
83
        head[t] = new Edge{head[t], s};
84
    }dfs();
85
    printf("%lld\n", ans);
86
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
87
    return 0;
88
}
89

90
template < typename T >
91
inline T read(void){
92
    T ret(0);
93
    int flag(1);
94
    char c = getchar();
95
    while(c != '-' && !isdigit(c))c = getchar();
96
    if(c == '-')flag = -1, c = getchar();
97
    while(isdigit(c)){
98
        ret *= 10;
99
        ret += int(c - '0');
100
        c = getchar();
101
    }
102
    ret *= flag;
103
    return ret;
104
}

[ABC248Ex] Beautiful Subsequences

题面

给定排列 $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

xxxxxxxxxx
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 中有如下语段：

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

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

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

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

xxxxxxxxxx
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)$，跑得飞快。

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