首页 algorithm 杂杂的算法知识

# 最大数

给定一个正整数数列 a1,a2,…,an ，每一个数都在 0∼p−1 之间。

可以对这列数进行两种操作：

  1. 添加操作：向序列后添加一个数，序列长度变成 n+1 ；
  2. 询问操作：询问这个序列中最后 L 个数中最大的数是多少。

如果该行的内容是 Q L ，则表示这个操作是询问序列中最后 L 个数的最大数是多少；

如果是 A t ，则表示向序列后面加一个数，加入的数是 (t+a) mod p 。其中，t 是输入的参数，a 是在这个添加操作之前最后一个询问操作的答案（如果之前没有询问操作，则 a=0）。

基本模版

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
#include <iostream>
using namespace std;
const int N = 2e5 + 10;
int m, p;
struct Node
{
    int l, r;
    int v;
}tree[N * 4];
void build(int u, int l, int r)
{
    tree[u] = {l,r};
    if(l == r) return;
    int mid = (l + r) >> 1;
    build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
}
void modify(int u, int x, int v)
{
    if(tree[u].l == x && tree[u].r == x)
    {
        tree[u].v = v;
        return;
    }
    int mid = (tree[u].l + tree[u].r) >> 1;
    if(x <= mid) modify(u << 1, x, v);
    else modify(u << 1 | 1, x, v);
    tree[u].v = max(tree[u << 1].v, tree[u <<1 | 1].v);
}
int query(int u, int l, int r)
{
    if(l <= tree[u].l && r >= tree[u].r) return tree[u].v;
    int mid = (tree[u].l + tree[u].r) >> 1;
    int v = 0;
    if(l <= mid) v = query(u << 1, l, r);
    if(r > mid) v = max(v, query(u << 1 | 1, l, r));
    return v;
}
int main()
{
    cin >> m >> p;
    int n = 0, last = 0;
    build(1, 1, m);
    while(m--)
    {
        char op;    cin >> op;
        if(op == 'A')
        {
            int t; cin >> t;
            modify(1, n + 1, ((long long)t + last) % p);
            n++;
        }
        else
        {
            int L;  cin >> L;
            last = query(1, n - L + 1, n);
            cout << last << '\n';
        }
    }
    return 0;
}

# 你能回答这些问题吗

给定长度为 N 的数列 A，以及 M 条指令，每条指令可能是以下两种之一：

  1. 1 x y ，查询区间 [x,y] 中的最大连续子段和，即max⁡x≤l≤r≤y{∑i=lrA[i]}\max\limits_{x\leq l\leq r \leq y}\left\{\sum\limits_{i=l}^r A[i]\right\}。
  2. 2 x y ，把 A [x] 改成 y。

对于每个查询指令，输出一个整数表示答案。

  1. 线段树结构体中要记录的有 l,r,max

  2. max 向上传递有三种情况

    • 问的区间恰好在区间的左半边
    • 问的区间恰好在区间的右半边
    • 问的区间横跨两个区间

    那么这个时候就需要记录左半边的右端点最大连续字段和以及右半边的左端点的最大连续字段和，以及整个区间的最大连续字段和

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
#include <iostream>
using namespace std;
const int N = 5e5 + 10;
struct Node
{
    int l, r;
    int lmax, rmax, tmax,sum;
}tree[N * 4];
int a[N];
int n, m;
//重点！
void pushup(Node& u, Node& l, Node& r)
{
    u.sum = l.sum + r.sum;
    u.lmax = max(l.lmax, l.sum + r.lmax);
    u.rmax = max(r.rmax, r.sum + l.rmax);
    u.tmax = max(max(l.tmax, r.tmax), l.rmax + r.lmax);
}
void pushup(int u)
{
    pushup(tree[u], tree[u << 1], tree[u << 1 | 1]);
}
void build(int u, int l, int r)
{
    if(l == r) tree[u] = {l, r, a[r], a[r], a[r], a[r]};
    else
    {
        tree[u] = {l, r};
        int mid = (l + r) >> 1;
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }
}
Node query(int u, int l, int r)
{
    if(tree[u].l >= l && tree[u].r <= r) return tree[u];
    int mid = (tree[u].l + tree[u].r) >> 1;
    if(l > mid) return query(u << 1 | 1, l, r);
    else if(r <= mid) return query(u << 1, l, r);
    else
    {
        auto left = query(u << 1, l, r);
        auto right = query(u << 1 | 1, l, r);
        Node res;
        pushup(res, left, right);
        return res;
    }
}
void modify(int u, int x, int y)
{
    if(tree[u].l == x && tree[u].r == x) tree[u] = {x, x, y, y, y, y};
    else
    {
        int mid = (tree[u].l + tree[u].r) >> 1;
        if(x <= mid) modify(u << 1, x, y);
        else if(x > mid) modify(u << 1 | 1, x, y);
        pushup(u);
    }
}
int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> a[i];
    build(1, 1, n);
    while(m--)
    {
        int k, x, y;
        cin >> k >> x >> y;
        if(k == 1)
        {
            if(x > y) swap(x, y);
            cout << query(1, x, y).tmax << '\n';
        }
        else if(k == 2)
        {
            modify(1, x, y);
        }
    }
    return 0;
}

# 区间最大公约数

给定一个长度为 N 的数列 A，以及 M 条指令，每条指令可能是以下两种之一：

  1. C l r d ，表示把 A[l],A[l+1],…,A[r]A[l],A[l+1],…,A[r] 都加上 d 。
  2. Q l r ，表示询问 A[l],A[l+1],…,A[r]A[l],A[l+1],…,A[r] 的最大公约数 (GCD)。

对于每个询问，输出一个整数表示答案。

  1. 涉及把一个区间都加上一个数，且求的是公约数，可以想到用差分；线段数结构体存储 l,r,sum,d ，sum 用来计算差分数组的前缀和即原数组，d 用来记录差分
  2. 查询操作：因为 gcd(a, b, c) = gcd(a, b - a, c - a) ，所以求 [l,r] 区间的最大公约数可以求 l.sum 即 a[i] 和 r.d 即 [l + 1, r] 差分的最大约数（在 l + 1 <= r 的情况下）
  3. 更改操作：因为是差分，所以在第 l 个位置加上 d，如果 r + 1 <= n 就减去 d
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
86
87
88
89
90
91
92
93
94
95
#include <iostream>
using namespace std;
#define int long long
const int N = 5e5 + 10;
int a[N];
int n, m;
struct Node
{
    int l, r;
    int sum, d;
}tree[N * 4];
int gcd(int a, int b)
{
    return b == 0 ? a : gcd(b, a % b);
}
void pushup(Node& u, Node& l, Node& r)
{
    u.sum = l.sum + r.sum;
    u.d = gcd(l.d, r.d);
}
void pushup(int u)
{
    pushup(tree[u], tree[u << 1], tree[u << 1 | 1]);
}
void build(int u, int l, int r)
{
    if(l == r) tree[u] = {l, r, a[r] - a[r - 1], a[r] - a[r - 1]};
    else
    {
        tree[u] = {l, r};
        int mid = l + r >> 1;
        build(u << 1, l, mid);
        build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }
}
Node query(int u, int l, int r)
{
    if(l <= tree[u].l && r >= tree[u].r) return tree[u];
    else
    {
        int mid = tree[u].l + tree[u].r >> 1;
        if(r <= mid) return query(u << 1, l, r);
        else if(l > mid) return query(u << 1 | 1, l, r);
        else
        {
            auto left = query(u << 1, l, r);
            auto right = query(u << 1 | 1, l, r);
            Node res;
            pushup(res, left, right);
            return res;
        }
    }
}
void modify(int u, int x, int v)
{
    if(tree[u].l == x && tree[u].r == x)
    {
        int b = tree[u].sum + v;
        tree[u] = {x, x, b, b};
    }
    else
    {
        int mid = tree[u].l + tree[u].r >> 1;
        if(x <= mid) modify(u << 1, x, v);
        else modify(u << 1 | 1, x, v);
        pushup(u);
    }
}
signed main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> a[i];
    build(1, 1, n);
    while(m--)
    {
        char op;    cin >> op;
        if(op == 'Q')
        {
            int l, r;   cin >> l >> r;
            auto left = query(1, 1, l);
            Node right = {0, 0, 0, 0};
            if(l + 1 <= r) right = query(1, l + 1, r);
            cout << abs(gcd(left.sum, right.d)) << '\n';
        }   
        else
        {
            int l, r, v;
            cin >> l >> r >> v;
            modify(1, l, v);
            if(r + 1 <= n) modify(1, r + 1, -v);
        }
    }
    return 0;
}

# 一个简单的整数问题 2

给定一个长度为 N 的数列 A，以及 M 条指令，每条指令可能是以下两种之一：

  1. C l r d ，表示把 A[l],A[l+1],…,A[r]A[l],A[l+1],…,A[r] 都加上 d。
  2. Q l r ，表示询问数列中第 l∼r 个数的和。

对于每个询问，输出一个整数表示答案。

利用懒标记 pushdown ()

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
86
87
88
#include <iostream>
using namespace std;
#define int long long
const int N = 1e5 + 10;
int a[N], n, m;
struct Node
{
    int l, r;
    int sum, tag;
}tree[N * 4];
void pushup(int u)
{
    tree[u].sum = tree[u << 1].sum + tree[u << 1 | 1].sum; 
}
void pushdown(int u)
{
    Node& root = tree[u], & left = tree[u << 1], & right = tree[u << 1 | 1];
    if(root.tag)
    {
        left.tag += root.tag, left.sum += (left.r - left.l + 1) * root.tag;
        right.tag += root.tag, right.sum += (right.r - right.l + 1) * root.tag;
        root.tag = 0;
    }
}
void build(int u, int l, int r)
{
    if(l == r) 
    {
        tree[u] = {l, r, a[l], 0};
        return;
    }
    tree[u] = {l, r};
    int mid = (l + r) >> 1;
    build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
    pushup(u);
}
void modify(int u, int l, int r, int v)
{
    if(tree[u].l >= l && tree[u].r <= r)
    {
        tree[u].sum += (tree[u].r - tree[u].l + 1) * v;
        tree[u].tag += v;
    }
    else
    {
        pushdown(u);
        int mid = (tree[u].l + tree[u].r) >> 1;
        if(l <= mid) modify(u << 1, l, r, v);
        if(r > mid) modify(u << 1 | 1, l, r, v);
        pushup(u);
    }
}
int query(int u, int l, int r)
{
    if(tree[u]. l >= l && tree[u].r <= r) 
    {
        return tree[u].sum;
    }
    pushdown(u);
    int mid = (tree[u].l + tree[u].r) >> 1;
    int s = 0;
    if(l <= mid) s = query(u << 1, l, r);
    if(r > mid) s += query(u << 1 | 1, l, r);
    return s;
}
signed main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> a[i];
    build(1, 1, n);
    while(m--)
    {
        char op; cin >> op;
        if(op == 'C')
        {
            int l, r, d;
            cin >> l >> r >> d;
            modify(1, l, r, d);
        }
        else
        {
            int l, r;
            cin >> l >> r;
            cout << query(1, l, r) << '\n';
        }
    }
    return 0;
}