单调队列

单调队列问题常常与双指针一起出现
比如求一段序列中,长度不超过mm连续子序列和的最大值

algorithm\textbf{algorithm}
最小化min{S[i]S[j]}\min \{S[i]-S[j]\}
此时目标序列是[j+1,i][j+1, i],满足ijmi-j \leqslant m
对于j<i\forall j < i,即求S[i]maxj<iS[j]S[i] - \max_{j < i} S[j]

  • 算法分析
    对于确定的i, j<ii, \ \forall j < i
    如果j1<j2j_1 < j_2 并且有S[j1]S[j2]S[j_1] \geqslant S[j_2],那么j1j_1 舍掉
    (因为j2j_2 同样满足,并且它距离ii 更近,更容易满足m\leqslant m 这个条件)
    下标值用单调队列存起来,队列中的元素一定满足严格单调增
    S[q1]<S[q2]<<S[qi]<S[q_1] < S[q_2] < \cdots < S[q_i] < \cdots

  • 算法实现

    • 初始化单调队列,一般取q1=0q_1 = 0 作为哨兵
    • 排除队头不合法决策
      while:lr and iq[l]>ml++\textbf{while}: l \leqslant r \ \textbf{and} \ i-q[l] > m \Rightarrow l++
    • 取队头作为最优决策更新答案
    • 当前扫描的点进入队列,并且维护队列单调性
      while:lr and S[qr]S[i]r\textbf{while}: l \leqslant r \ \textbf{and} \ S[q_r] \geqslant S[i] \Rightarrow r--
      q[++r]iq[++r] \leftarrow i

Acwing135

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
const int maxn = 300000 + 10;
const int inf = 0x3f3f3f3f;
int n, m, S[maxn], q[maxn];

void solve() {
int l = 1, r = 1, ans = -inf;
q[1] = 0;
for (int i = 1; i <= n; i++) {
while (l <= r && i - q[l] > m) l++;
ans = max(ans, S[i] - S[q[l]]);
while (l <= r && S[q[r]] >= S[i]) r--;
q[++r] = i;
}
printf("%d\n", ans);
}

int main() {
freopen("input.txt", "r", stdin);
cin >> n >> m;
for (int i = 1; i <= n; i++) {
int x; scanf("%d", &x);
S[i] = S[i-1] + x;
}

solve();
}

取整函数

取整函数有一些常用的性质

x=xx=x\begin{gathered} \lfloor -x \rfloor = -\lceil x \rceil \\ \lceil -x \rceil = -\lfloor x \rfloor \end{gathered}

C+x=C+xCZCx=C+x=CxCZCx=CxCZ\begin{gathered} C + \lfloor x \rfloor = \lfloor C + x \rfloor && C \in \mathbb{Z} \\ C - \lfloor x \rfloor = C + \lceil -x \rceil = \lceil C-x \rceil && C \in \mathbb{Z} \\ C - \lceil x \rceil = \lfloor C-x \rfloor && C \in \mathbb{Z} \end{gathered}

x=x实数x0\begin{gathered} \left \lfloor \sqrt{ \lfloor x \rfloor } \right \rfloor = \left \lfloor \sqrt{x} \right \rfloor && \text{实数} x \geqslant 0 \end{gathered}

x+mn=x+mnx+mn=x+mnm,n 为整数并且分母 n>0\begin{gathered} \left \lfloor \frac{x+m}{n} \right \rfloor = \left \lfloor \frac{ \lfloor x \rfloor + m}{n} \right \rfloor \\ \left \lceil \frac{x+m}{n} \right \rceil = \left \lceil \frac{\lceil x \rceil + m}{n} \right \rceil \\ m, n \ \text{为整数并且分母} \ n > 0 \end{gathered}

线性模型

讲到取整函数,不得不说一种模型叫偏差模型
经常出现在诸如时间tt 这样的线性结构中
比如某一时刻的偏移量满足

Δ=T0+kt\Delta = T_0 + kt

Acwing133
这种问题很显然是线性模型
在初识时刻长度为Q0Q_0tt 时刻过后,长度增加为

Q0+qtQ_0 + q\cdot t

Acwing133-01
Acwing133-02

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
const int maxn = 100000 + 10;
int n, m, q, u, v, t, a[maxn];
#define p u/v

queue<ll> v0, v1, v2;
int cmp(int a, int b) { return a > b; }

ll calc(int t) {
ll mx, x0 = -1, x1 = -1, x2 = -1;
if (v0.size()) x0 = v0.front() + q*t;
if (v1.size()) x1 = v1.front() + q*t;
if (v2.size()) x2 = v2.front() + q*t;

mx = max(max(x0, x1), x2);
if (mx == x0 && v0.size()) v0.pop();
else if (mx == x1 && v1.size()) v1.pop();
else if (mx == x2 && v2.size()) v2.pop();

return mx;
}

void solve() {
sort(a+1, a+1+n, cmp);
_rep(i, 1, n) v0.push(1ll*a[i]);

for (int i = 1; i <= m; i++) {
ll res = calc(i-1);
if (i % t == 0) printf("%lld ", res);

ll li = res * p;
ll ri = res - li;
li -= i*q, ri -= i*q;
v1.push(li), v2.push(ri);
}
printf("\n");

for (int i = 1; i <= n+m; i++) {
ll res = calc(m);
if (i % t == 0) printf("%lld ", res);
}
}

void init() {
//
}

int main() {
freopen("input.txt", "r", stdin);
// get data
scanf("%d%d%d%d%d%d", &n, &m, &q, &u, &v, &t);
_rep(i, 1, n) scanf("%d", &a[i]);

// then solve
solve();
}

单调性和分段函数

单调性和分段函数问题,往往是先根据数学工具挖掘单调性
但常常得出了单调性结论,却发现编程实现困难
这里给出一些常见的编程实现方式

  • 找拐点

    (last,dir)来描述last记录上一个段的最末位置, dir记录上一个段的单调趋势,单调增或减\begin{gathered} (last, dir) \quad \text{来描述} \\ last \text{记录上一个段的最末位置,} \ dir \text{记录上一个段的单调趋势,单调增或减} \end{gathered}

Acwing134
Acwing134-01
Acwing134-01

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
const int maxn = 200000 + 10;
const int inf = 0x3f3f3f3f;
typedef pair<int, int> PII;
PII a[maxn];
int n;

void solve() {
sort(a, a+n);

int last = inf, dir = -1, ans = 1;
for (int i = 0; i < n; ) {
int j = i;
while (j+1 < n && a[j].first == a[j+1].first) j++;
// [i, j] same value

int minv = a[i].second, maxv = a[j].second;
if (dir == -1) {
if (maxv < last) last = minv;
else last = maxv, dir = -dir;
}
else {
if (minv > last) last = maxv;
else {
ans++;
last = minv;
dir = -dir;
}
}
i = j+1;
}
printf("%d\n", ans);
}

void init() {
//
}

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

// get data
cin >> n;
for (int i = 0; i < n; i++) {
scanf("%d", &a[i].first);
a[i].second = i;
}

// solve
solve();
}

链表:数组模拟

链表用数组模拟,需要全局维护两个值

l(i),r(i)i 表示数组下标,l(i),r(i) 分别表示左,右两个位置\begin{gathered} l(i), r(i) \\ i \ \text{表示数组下标,} l(i), r(i) \ \text{分别表示左,右两个位置} \end{gathered}

特别地,可以这么理解数组模拟

L[p]=q 看成是一个作用,将 p 这个位置,左边连到 qR[p]=q 同理,将 p 这个位置,右边连到 q\begin{gathered} L[p] = q \ \text{看成是一个作用,将} \ p \ \text{这个位置,左边连到 } q \\ R[p] = q \ \text{同理,将 } p \ \text{这个位置,右边连到 } q \end{gathered}

1
2
3
4
5
6
7
8
9
10
void init() {
for (int i = 1; i <= n; i++) {
L[i] = i-1, R[i] = i+1;
}
}
// remove i
for (int i = n; i >= 1; i--) {
int left = L[i], right = R[i];
L[right] = left, R[left] = right;
}

Acwing136
链表可以用来求邻值查找问题

min1j<iAiAj\min_{1 \leqslant j < i} |A_i - A_j|

Acwing136

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
typedef pair<ll, int> PII;
const int maxn = 100000 + 10;
const ll inf = 0x3f3f3f3f3f3f3f3f;
PII a[maxn], ans[maxn];
int n;

void solve() {
sort(a+1, a+1+n);
a[0].first = -inf, a[n+1].first = inf;

int L[maxn], R[maxn], mp[maxn];
for (int i = 1; i <= n; i++) {
L[i] = i-1, R[i] = i+1;
mp[a[i].second] = i;
}

for (int id = n; id > 1; id--) {
int i = mp[id], left = L[i], right = R[i];
ll lval = abs(a[left].first - a[i].first);
ll rval = abs(a[right].first - a[i].first);

if (lval <= rval) ans[id] = make_pair(lval, a[left].second);
else ans[id] = make_pair(rval, a[right].second);

L[right] = left, R[left] = right;
}

for (int i = 2; i <= n; i++) printf("%lld %d\n", ans[i].first, ans[i].second);
}


int main() {
freopen("input.txt", "r", stdin);
cin >> n;
for (int i = 1; i <= n; i++) {
scanf("%lld", &a[i].first);
a[i].second = i;
}

// then solve
solve();
}