算法设计策略中
扫描法有关的,常常包括

  • 前缀和与差分
  • 前缀最大值,最小值维护

单调性有关的,常常包括

  • 单调队列与单调栈
  • 滑动窗口,双指针
  • 二分

二分法

整数二分

说到单调性的问题,很多二分可以解决的问题,往往也具有单调性
这里补充一些整数二分的模版

1
2
3
4
5
6
7
8
9
10
11
12
将区间 [l, r] 划分成为 [l, mid] 和 [mid+1, r]
更新操作是 r = mid 或者 l = mid + 1
最后的答案是新区间的 l

int bsearch(int l, int r) {
while (l < r) {
int mid = l + r >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
return l;
}
1
2
3
4
5
6
7
8
9
10
11
12
将区间 [l, r] 划分成为 [l, mid-1] 和 [mid, r]
更新操作是 l = mid 或者是 r = mid - 1
为了防止死循环,计算 mid = l + r + 1 >> 1;

int bsearch(int l, int r) {
while (l < r) {
int mid = l + r + 1 >> 1;
if (check(mid)) l = mid;
else r = mid - 1;
}
return l;
}

两种二分,实际上是上取整和下取整的不同
实际上,中点都满足mid=(l+r)/2mid = (l+r) / 2

第一种情况
[l,r][l,mid][mid+1,r][l,r] \to [l,mid] \cup [mid+1, r]

第二种情况
[l,r][l,mid1][mid,r][l,r] \to [l,mid-1] \cup [mid, r]
边界条件是r=l+1r = l+1
此时mid=(2l+1)/2=lmid = (2l+1)/2 = l 恒成立
[l,r][mid,r]=[l,r][l, r] \to [mid, r]=[l,r]
区间没有发生变化,导致死循环
解决方法是mid=(l+r+1)/2mid = (l+r+1) / 2 进行上取整即可

1
2
3
为了简便记忆,当执行了
l = mid
二分条件就变成了 mid = (l+r+1) / 2

小数二分

小数二分答案,其实反而更简单

1
2
3
4
5
6
7
8
double bsearch(double l, double r) {
while (r - l > eps) {
double mid = (l + r) / 2;
if (check(mid)) l = mid;
else r = mid;
}
return l;
}

值得注意的是 PI 的定义

1
const double PI = acos(-1.0);

扫描法,二分维护历史集合

Acwing113
Acwing113

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
vector<int> specialSort(int N) {
vector<int> ans;
ans.push_back(1);

for (int i = 2; i <= N; i++) {
// binary search
int l = 0, r = ans.size() - 1;
while (l < r) {
int mid = l + r + 1 >> 1;
if (compare(ans[mid], i)) l = mid;
else r = mid - 1;
}
// ans is r

ans.push_back(i);
// bubble sort
for (int j = ans.size() - 2; j > r; j--) swap(ans[j], ans[j+1]);
if (compare(i, ans[r])) swap(ans[r], ans[r+1]);
}
return ans;
}
};

环形双指针

Acwing2452
Acwing2452
本例涉及的思想有:计算几何,转角法,双指针

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
constexpr int maxn = 800 + 10;
int m = 0;

int S[maxn<<2], Sd[maxn<<2], St[maxn<<2];
ll ans = 0;

class Point {
public:
int x, y, fl;
Point() = default;
Point(int x, int y, int fl = 0) : x(x), y(y), fl(fl) {}
int sgn() const {
if (y > 0 || (y == 0 && x > 0)) return 1;
else return -1;
}
} a[maxn], b[maxn], c[maxn], vec[maxn<<2];
// a enemy, b source, c tower
int _D, _S, _T;

inline ll cross(const Point &a, const Point &b) {
return 1ll*a.x*b.y - 1ll*a.y*b.x;
}

bool cmp(const Point &a, const Point &b) {
if (a.sgn() != b.sgn()) return a.sgn() > b.sgn();
return cross(a, b) > 0;
}

void work() {
_rep(i, 1, m << 1) {
S[i] = S[i-1], Sd[i] = Sd[i-1], St[i] = St[i-1];
if (vec[i].fl == 0) {
Sd[i]++;
}
else {
S[i] += Sd[i], St[i]++;
}
}

// double pointer
int j = 1, k = 1;
for (; j <= m; j++) if (vec[j].fl) {
if (k < j) k = j;
while (k+1 < j+m && cross(vec[j], vec[k+1]) >= 0 ) k++;
ans += (S[k] - S[j]) - Sd[j] * (St[k]-St[j]);
}
}

void solve() {
_rep(i, 1, _S) {
m = 0;
_rep(j, 1, _D) vec[++m] = Point(a[j].x-b[i].x, a[j].y-b[i].y, 0);
_rep(j, 1, _T) vec[++m] = Point(c[j].x-b[i].x, c[j].y-b[i].y, 1);
sort(vec+1, vec+1+m, cmp);
_rep(j, 1, m) vec[j+m] = vec[j];

// then work
work();
}
printf("%lld\n", ans);
}

void init() {
memset(S, 0, sizeof(S));
memset(Sd, 0, sizeof(Sd));
memset(St, 0, sizeof(St));
m = 0;
ans = 0;
}

int main() {
freopen("input.txt", "r", stdin);
init();

// get data
scanf("%d", &_D);
_rep(i, 1, _D) scanf("%d%d", &a[i].x, &a[i].y);
scanf("%d", &_S);
_rep(i, 1, _S) scanf("%d%d", &b[i].x, &b[i].y);
scanf("%d", &_T);
_rep(i, 1, _T) scanf("%d%d", &c[i].x, &c[i].y);

// then solve
solve();
}

滑动窗口的单调性

Acwing1688 列车记录2
Acwing1688-01
Acwing1688-02
Acwing1688-03
Acwing1688-04

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
const int maxn = 1e5 + 10;
const int inf = 1e9;
const int mod = 1e9 + 7;
int N, K, c[maxn];

inline int solve(int v, int len) {
int f[maxn];
f[0] = f[1] = 1;

int p = inf - v;
for (int i = 2; i <= len + 1; i++) {
f[i] = 1ll * (p+1) * f[i-1] % mod;
if (i-K-1 >= 0) f[i] = (f[i] - 1ll * f[i-K-1] * ksm(p, K, mod) % mod + mod) % mod;
}
return f[len+1];
}

void init() {
//
}

int main() {
freopen("input.txt", "r", stdin);
init();
scanf("%d%d", &N, &K);
_rep(i, 1, N+1-K) scanf("%d", &c[i]);

// then solve
int i = 1, j = 1, len = 1;
ll ans = 1;
for (; i <= N+1-K; i = j+1) {
j = i;
while (c[j+1] == c[i]) j++;
len = j-i+K;
if (i > 1 && c[i-1] > c[i]) len -= K;
if (j < N+1-K && c[j+1] > c[i]) len -= K;

ans = 1ll * ans * solve(c[i], len) % mod;
}
printf("%lld\n", ans);
}

连续子序列问题

连续子序列问题是典型的可以用滑动窗口维护的
必要时可借助其他数据结构维护滑动窗口区间[l,r][l, r]

UVA11536
这是一个求“连续子区间长度最小”的问题

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
constexpr int maxn = 1e6 + 10;
const int inf = 0x3f3f3f3f;
int x[maxn], N, M, K;

void prework() {
_for(i, 0, N) {
if (i < 3) x[i] = i+1;
else x[i] = (x[i-1] + x[i-2] + x[i-3]) % M + 1;
}
}

void add(int v, map<int, int> &mp) {
if (1<= v && v <= K) mp[v]++;
}
void del(int v, map<int, int> &mp) {
if (mp.count(v) == 0) return;
mp[v]--;
if (mp[v] < 1) mp.erase(v);
}

void solve() {
int ans = inf;
map<int, int> mp;
int i = 0, j = 0;

for (; i < N; i++) {
while (j < N && mp.size() < K) add(x[j++], mp);
if (mp.size() == K) {
while (i < N && ( !mp.count(x[i]) || mp[x[i]] > 1 )) del(x[i++], mp);
chmin(ans, j - i);
}
del(x[i], mp);
}

if (ans == inf) printf("sequence nai\n");
else printf("%d\n", ans);
}

void init() {
memset(x, 0, sizeof(x));
}

int main() {
freopen("input.txt", "r", stdin);
int kase, _ = 0;
scanf("%d", &kase);

while (kase--) {
init();
printf("Case %d: ", ++_);
scanf("%d%d%d", &N, &M, &K);

// then prework and solve
prework();
solve();
}
}

单调栈模型

单调栈最常用的模型就是:找到左边第一个比AiA_i 小的元素
Gym101334F
Gym101334F

根据单调栈模型,本例的算法就很简单了

  • 预处理每一个AiA_i,求出左边第一个比AiA_i 小的元素位置L(i)L(i)
    右边第一个比AiA_i 小的元素R(i)R(i)
  • 用区间[L(i)+1,R(i)1][L(i)+1, R(i)-1] 部分和×Ai\times A_i 来更新全局的ansans
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
constexpr int maxn = 100000 + 10;
const ll inf = 0x3f3f3f3f3f3f3f3f;
int N, a[maxn];

int s[maxn], top = 0;
ll S[maxn];
int l[maxn], r[maxn];

void prework() {
_rep(i, 1, N) S[i] = S[i-1] + 1ll * a[i];

top = 0;
for (int i = 1; i <= N; i++) {
while (top && a[s[top]] >= a[i]) top--;
if (top == 0) l[i] = 0;
else l[i] = s[top];
s[++top] = i;
}

top = 0;
for (int i = N; i >= 1; i--) {
while (top && a[s[top]] >= a[i]) top--;
if (top == 0) r[i] = N + 1;
else r[i] = s[top];
s[++top] = i;
}
}

void solve() {
int ansl = 0, ansr = 0;
ll ans = -inf;
for (int i = 1; i <= N; i++) {
ll res = 1ll * (S[r[i]-1] - S[l[i]]) * a[i];
if (chmax(ans, res)) {
ansl = l[i] + 1, ansr = r[i] - 1;
}
}

printf("%lld\n", ans);
printf("%d %d\n", ansl, ansr);
}

void init() {
memset(s, 0, sizeof(s));
memset(S, 0, sizeof(S));
memset(l, 0, sizeof(l));
memset(r, 0, sizeof(r));
top = 0;
}

int main() {
freopen("feelgood.in", "r", stdin);
freopen("feelgood.out", "w", stdout);
init();
scanf("%d", &N);
_rep(i, 1, N) scanf("%d", &a[i]);

// prework and solve
prework();
solve();
}

差分思想

差分基础

Acwing100
Acwing100-01
Acwing100-02

树状数组和差分序列

差分策略常常利用树状数组作为数据结构来解决

Acwing246
Acwing246

1