ACM►命题

SDUTACM十周年题解（Fish出题部分）

区间第K大

题目完全没有弯，就是区间修改，询问第 K 大。

但是 K 特别小，我们考虑用线段树去维护这个东西，线段树每个节点维护当前区间的前 K 大的数。

首先区间修改操作还是用 Lazy 去做就 OK，打 Lazy 标记的时候把前 K 大的值同时修改，然后我们考虑第 K 大怎么维护。

考虑左右两个区间的信息合并，假设左右区间已经维护了前 K 大的数，那么左右区间合并后的前 K 大的数显然等于这两个区间前 K 大的数降序排序取前 K 个。

然后这个题就做完了，复杂度$O(k\cdot q\cdot \log(n))$

代码

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
#include <bits/stdc++.h>

using namespace std;

const int MAX = 1e5 + 100;
const int INF = 0x3f3f3f3f;

struct Node {
    vector<int> v;
    int lazy;

    Node() {
        lazy = 0;
        v = vector<int>();
    }

    void maintain(int d) {
        for (auto &x : v) x += d;
        lazy += d;
    }

    Node operator+(const Node &t) {
        Node rst;
        rst.lazy = 0;
        for (auto x : v) rst.v.push_back(x);
        for (auto x : t.v) rst.v.push_back(x);
        sort(rst.v.begin(), rst.v.end(), greater<>());
        if (rst.v.size() > 5) rst.v.erase(rst.v.begin() + 5, rst.v.end());
        return rst;
    }
} tree[MAX << 4];

#define lson (o<<1)
#define rson (o<<1|1)
#define MID int m = (l + r) >> 1

void push_down(int o) {
    if (!tree[o].lazy) return;
    int &lazy = tree[o].lazy;
    tree[lson].maintain(lazy);
    tree[rson].maintain(lazy);
    lazy = 0;
}

void update(int o, int l, int r, int ql, int qr, int v) {
    if (qr < l || r < ql) return;
    if (ql <= l && r <= qr) {
        tree[o].maintain(v);
        return;
    }
    push_down(o);
    MID;
    update(lson, l, m, ql, qr, v);
    update(rson, m + 1, r, ql, qr, v);
    tree[o] = tree[lson] + tree[rson];
}

Node query(int o, int l, int r, int ql, int qr) {
    if (qr < l || r < ql) return Node();
    if (ql <= l && r <= qr) return tree[o];
    push_down(o);
    MID;
    return query(lson, l, m, ql, qr) + query(rson, m + 1, r, ql, qr);
}

int A[MAX];

void build(int o, int l, int r) {
    tree[o] = Node();
    if (l == r) {
        tree[o].v.push_back(A[l]);
        return;
    }
    MID;
    build(lson, l, m);
    build(rson, m + 1, r);
    tree[o] = tree[lson] + tree[rson];
}

int main() {
    int n, q;
    while (~scanf("%d %d", &n, &q)) {
        for (int i = 1; i <= n; i++) scanf("%d", A + i);
        build(1, 1, n);
        while (q--) {
            int o, l, r, v;
            scanf("%d %d %d %d", &o, &l, &r, &v);
            if (o == 1) update(1, 1, n, l, r, v);
            else printf("%d\n", query(1, 1, n, l, r).v[v - 1]);
        }
    }
}

QAQ子串

我们考虑至少包含 QAQ 的子串比较难求，所以我们反过来考虑，求不包含 QAQ 子串的字符串。

那么这是一个常见的动态规划问题。

我们定义 $dp[i][j]$的含义长度为 $i$，并且结尾的状态为 $j$ 的方案数。

定义状态 $0$ 为不构成 QAQ 任何前缀的结尾，比如 “QAAA”、“bLue”、“UMR” 等。

定义状态 $1$ 为以 Q 字符为结尾，比如 “QWQ”、“QvQ” 等。

定义状态 $2$ 为以 “QA” 为结尾，比如 AQA”，“AQQA” 等。

状态 $0​$ 可由状态 $0​$ 或状态 ‘2’ 加上任意非 ‘Q’ 的字符转移而来，或由状态 $1​$ 加上任意非 ‘Q’ 且非 ‘A’ 的字符转移而来。

状态 $1$ 可由状态 $0$ 或状态 $1$ 加上 ‘Q’ 字符转移而来。

状态 2 仅有状态 1 加上 ‘A’ 转移而来。

即

$dp[i][0] = 25\times dp[i - 1][0] + 24 \times dp[i - 1][1] + 25\times dp[i - 1][2]$

$dp[i][1] = dp[i - 1][0] + dp[i - 1][1]$

$dp[i][2] = dp[i][1]$

初始值 $dp[i][0] = 1, dp[i][1] = dp[i][2] = 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
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int MAX = 1e5 + 100;
const int MOD = 1e9 + 7;

ll dp[MAX][3];

void add(ll &x, ll y) {
    x = (x + y) % MOD;
}

ll cnt[MAX];

int main() {
    int n;
    dp[0][0] = 1;
    cnt[0] = 1;
    for (int i = 0; i < 1e5; i++) {
        cnt[i + 1] = cnt[i] * 26 % MOD;
        add(dp[i + 1][0], dp[i][0] * 25);
        add(dp[i + 1][0], dp[i][1] * 24);
        add(dp[i + 1][0], dp[i][2] * 25);

        add(dp[i + 1][1], dp[i][0]);
        add(dp[i + 1][1], dp[i][1]);

        add(dp[i + 1][2], dp[i][1]);
    }
    while (~scanf("%d", &n)) {
        ll ans = (cnt[n] - (dp[n][0] + dp[n][1] + dp[n][2]) % MOD + MOD) % MOD;

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