Lucius7nya

代码与猫耳并存的世界～ UwU

0%

templates

发表于 更新于

[TOC]

__builtin

1
__builtin_clz(a)

std::hypotl

计算 平方和开平方根

1
std::hypotl(x, y)

list

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
std::list<int> list;
list.push_front(0);
std::vector<std::list<int>::iterator> it(N);
it[0] = list.begin();
for (int i = 1; i < N; i++) {
    int k, p;
    std::cin >> k >> p;
    k--;
    if (p == 0) {
        it[i] = list.insert(it[k], i);
    } else {
        it[i] = list.insert(std::next(it[k]), i);
    }
}

int M;
std::cin >> M;

std::vector<bool> erased(N);

while (M--) {
    int x;
    std::cin >> x;
    x--;
    if (!erased[x]) {
        list.erase(it[x]);
        erased[x] = true;
    }
}

for (int x : list) {
    std::cout << x + 1 << " ";
}

DSU

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
struct DSU {
    std::vector<int> f, siz;
    
    DSU() {}
    DSU(int n) {
        init(n);
    }
    
    void init(int n) {
        f.resize(n);
        std::iota(f.begin(), f.end(), 0);
        siz.assign(n, 1);
    }
    
    int find(int x) {
        while (x != f[x]) {
            x = f[x] = f[f[x]];
        }
        return x;
    }
    
    bool same(int x, int y) {
        return find(x) == find(y);
    }
    
    bool merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return false;
        }
        siz[x] += siz[y];
        f[y] = x;
        return true;
    }
    
    int size(int x) {
        return siz[find(x)];
    }
};

DSU with weight

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
struct DSU {
    std::vector<int> f, siz;
    std::vector<int> val;
    
    DSU() {}
    DSU(int n) {
        init(n);
    }
    
    void init(int n) {
        f.resize(n);
        std::iota(f.begin(), f.end(), 0);
        siz.assign(n, 1);
        val.resize(n);
    }
    
    int find(int x) {
        if (x == f[x]) {
        	return x;
        }
        int root = find(f[x]);
        val[x] += val[f[x]];
        return f[x] = root;
    }
    
    bool same(int x, int y) {
        return find(x) == find(y);
    }
    
    bool merge(int x, int y, int w) {
        int nx = find(x), ny = find(y);
        if (nx == ny) {
            return false;
        }
        
        if (siz[nx] < siz[ny]) {
        	std::swap(nx, ny);
        	std::swap(x, y);
        	w *= -1;
        }

	    siz[nx] += siz[ny];
	    val[ny] = val[x] + w - val[y];
	    f[ny] = nx;

        return true;
    }
    
    int size(int x) {
        return siz[find(x)];
    }
};

DSU with rollback

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
struct DSU {
    std::vector<int> siz;
    std::vector<int> f;
    std::vector<std::array<int, 2>> his;
    
    DSU(int n) : siz(n + 1, 1), f(n + 1) {
        std::iota(f.begin(), f.end(), 0);
    }
    
    int find(int x) {
        while (f[x] != x) {
            x = f[x];
        }
        return x;
    }
    
    bool same(int x, int y) {
        return find(x) == find(y);
    }
    
    bool merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return false;
        }
        if (siz[x] < siz[y]) {
            std::swap(x, y);
        }
        his.push_back({x, y});
        siz[x] += siz[y];
        f[y] = x;
        return true;
    }
    
    int time() {
        return his.size();
    }
    
    void revert(int tm) {
        while (his.size() > tm) {
            auto [x, y] = his.back();
            his.pop_back();
            f[y] = y;
            siz[x] -= siz[y];
        }
    }
};

ST

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
template<class T, class Cmp = std::less<T>>
struct RMQ {
    const int n;
    const Cmp cmp;
    std::vector<std::vector<T>> a;
    RMQ(const std::vector<T> &init) : n(init.size()), cmp(Cmp()) {
        int lg = std::__lg(n);
        a.assign(n, std::vector<T>(lg + 1));
        for (int j = 0; j <= lg; j++) {
            for (int i = 0; i + (1 << j) <= n; i++) {
                a[i][j] = (j == 0 ? init[i] : std::min(a[i][j - 1], a[i + (1 << (j - 1))][j - 1], cmp));
            }
        }
    }
    T rangeMin(int l, int r) {
        int k = std::__lg(r - l);
        return std::min(a[l][k], a[r - (1 << k)][k], cmp);
    }
};

auto cmpIdx = [](int x, int y) {
		if (key[x] != key[y]) {
			return key[x] > key[y];
		}
		return x > y;
};

partition_point

二分查找后继：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int ans = *std::ranges::partition_point(std::ranges::iota_view(0, int(1E9) + 1), 
        [&](int k) {
            int L = 0, R = 0;
            for (int i = 0; i < n; i++) {
                L -= k;
                R += k;
                L = std::max(L, l[i]);
                R = std::min(R, r[i]);
                if (L > R) {
                    return true;
                }
            }
            return false;
        });

二分查找：FFFFFTTTTTT

前驱（第一个T）：

1
2
3
4
5
6
7
8
9
10
11
int lo = 1, hi = 1E9;
while (lo < hi) {
    int m = (lo + hi) / 2;
    if (check(m)) {
        hi = m;
    } else {
        lo = m + 1;
    }
}
std::cout << lo << "\n";

后继（最大可行值）：
TTTTFFFFF（最后一个 T）：

1
2
3
4
5
6
7
8
9
10
int lo = 1, hi = 1E9;
while (lo < hi) {
    int m = (lo + hi + 1) / 2;
    if (check(m)) {
        lo = m;
    } else {
        hi = m - 1;
    }
}
std::cout << lo << "\n";

partial_sum

前缀和：

1
std::partial_sum(A.begin(), A.end(), prefix.begin() + 1);

前缀异或和：

1
std::partial_sum(A.begin(), A.end(), prefix.begin() + 1, [](int a, int b) { return a ^ b; });

后缀和：

1
std::partial_sum(A.rbegin(), A.rend(), suffix.rbegin() + 1);

int128

1
2
3
4
5
6
7
8
9
10
11
12
std::ostream &operator<<(std::ostream &os, i128 n) {
    if (n == 0) {
        return os << 0;
    }
    std::string s;
    while (n > 0) {
        s += char('0' + n % 10);
        n /= 10;
    }
    std::reverse(s.begin(), s.end());
    return os << s;
}

随机数

1
std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());

Y conbinator + lambda

bfs + dfs（找环）：

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
int n, a, b;
std::cin >> n >> a >> b;
a--, b--;

std::vector<std::vector<int>> adj(n);
for (int i = 0; i < n; i++) {
    int u, v;
    std::cin >> u >> v;
    u--, v--;
    adj[u].push_back(v);
    adj[v].push_back(u);
}

auto bfs = [&](int s) {
    std::vector<int> dis(n, -1);
    dis[s] = 0;
    std::queue<int> q;
    q.push(s);

    while (!q.empty()) {
        auto x = q.front();
        q.pop();

        for (auto y : adj[x]) {
            if (dis[y] == -1) {
                dis[y] = dis[x] + 1;
                q.push(y);
            }
        }
    }
    return dis;
};

auto dis = bfs(b);

int u = -1;
std::vector<int> vis(n);
std::vector<int> par(n), dep(n);
auto dfs = [&](auto self, int x) -> void {
    vis[x] = true;

    for (auto y : adj[x]) {
        if (!vis[y]) {
            par[y] = x;
            dep[y] = dep[x] + 1;
            self(self, y);
        } else if (dep[y] < dep[x] - 1) {
            for (int i = x; ; i = par[i]) {
                if (u == -1 || dis[i] < dis[u]) {
                    u = i;
                }
                
                if (i == y) {
                    break;
                }
            }
        }
    }
};
dfs(dfs, 0);

if (bfs(u)[a] > dis[u]) {
    std::cout << "YES\n";
} else {
    std::cout << "NO\n";
}

data structure

fenwick:

0base，add(i, a), sum(i), rangeSum(l, r)

select(x)：前缀和不超过 x 的最大位置 。

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
template <typename T>
struct Fenwick {
    int n;
    std::vector<T> a;
    
    Fenwick(int n_ = 0) {
        init(n_);
    }
    
    void init(int n_) {
        n = n_;
        a.assign(n, T{});
    }
    
    void add(int x, const T &v) {
        for (int i = x + 1; i <= n; i += i & -i) {
            a[i - 1] = a[i - 1] + v;
        }
    }
    
    T sum(int x) {
        T ans{};
        for (int i = x; i > 0; i -= i & -i) {
            ans = ans + a[i - 1];
        }
        return ans;
    }
    
    T rangeSum(int l, int r) {
        return sum(r) - sum(l);
    }
    
    int select(const T &k) {
        int x = 0;
        T cur{};
        for (int i = 1 << std::__lg(n); i; i /= 2) {
            if (x + i <= n && cur + a[x + i - 1] <= k) {
                x += i;
                cur = cur + a[x - 1];
            }
        }
        return x;
    }
};

二维 fenwick

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
template <typename T>
struct Fenwick {
    int n, m;
    std::vector<std::vector<T>> a;
    
    Fenwick(int n_ = 0, int m_ = 0) {
        init(n_, m_);
    }
    
    void init(int n_, int m_) {
        n = n_, m = m_;
        a.assign(n, std::vector<T>(m_, T{}));
    }
    
    void add(std::pair<int, int> x, const T &v) {
        for (int i = x.first + 1; i <= n; i += i & -i) {
            for (int j = x.second + 1; j <= m; j += j & -j) {
            	a[i - 1][j - 1] = a[i - 1][j - 1] + v;
            }
        }
    }
    
    T sum(std::pair<int, int> x) {
        T ans{};
        for (int i = x.first; i > 0; i -= i & -i) {
        	for (int j = x.second; j > 0; j -= j & -j) {
        		ans = ans + a[i - 1][j - 1];
        	}
        }
        return ans;
    }
    
    T rangeSum(std::pair<int, int> x, std::pair<int, int> y) {
        return sum({y.first + 1, y.second + 1}) - sum({y.first + 1, x.second}) - sum({x.first, y.second + 1}) + sum({x.first, x.second});
    }
};

SegmentTree:

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
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
template<class Info>
struct SegmentTree {
    int n;
    std::vector<Info> info;
    SegmentTree() : n(0) {}
    SegmentTree(int n_, Info v_ = Info()) {
        init(n_, v_);
    }
    template<class T>
    SegmentTree(std::vector<T> init_) {
        init(init_);
    }
    void init(int n_, Info v_ = Info()) {
        init(std::vector(n_, v_));
    }
    template<class T>
    void init(std::vector<T> init_) {
        n = init_.size();
        info.assign(4 << std::__lg(n), Info());
        std::function<void(int, int, int)> build = [&](int p, int l, int r) {
            if (r - l == 1) {
                info[p] = init_[l];
                return;
            }
            int m = (l + r) / 2;
            build(2 * p, l, m);
            build(2 * p + 1, m, r);
            pull(p);
        };
        build(1, 0, n);
    }
    void pull(int p) {
        info[p] = info[2 * p] + info[2 * p + 1];
    }
    void modify(int p, int l, int r, int x, const Info &v) {
        if (r - l == 1) {
            info[p] = v;
            return;
        }
        int m = (l + r) / 2;
        if (x < m) {
            modify(2 * p, l, m, x, v);
        } else {
            modify(2 * p + 1, m, r, x, v);
        }
        pull(p);
    }
    void modify(int p, const Info &v) {
        modify(1, 0, n, p, v);
    }

    void rangeOr(int p, int l, int r, int x, int y, int v) {
        if (l >= y || r <= x) {
            return;
        }

        if ((info[p].sumAnd & v) == v) {
            return;
        }

        if (r - l == 1) {
            int nv = (info[p].sumAnd | v);
            info[p] = {nv, nv, std::max(0, nv), std::max(0, nv), std::max(0, nv)};
            return;
        }

        int m = (l + r) / 2;
        rangeOr(2 * p, l, m, x, y, v);
        rangeOr(2 * p + 1, m, r, x, y, v);
        pull(p);
    }

    void rangeOr(int l, int r, int v) {
        rangeOr(1, 0, n, l, r, v);
    }

    Info rangeQuery(int p, int l, int r, int x, int y) {
        if (l >= y || r <= x) {
            return Info();
        }
        if (l >= x && r <= y) {
            return info[p];
        }
        int m = (l + r) / 2;
        return rangeQuery(2 * p, l, m, x, y) + rangeQuery(2 * p + 1, m, r, x, y);
    }
    Info rangeQuery(int l, int r) {
        return rangeQuery(1, 0, n, l, r);
    }

    template<class F>
    int findFirst(int p, int l, int r, int x, int y, F &&pred) {
        if (l >= y || r <= x) {
            return -1;
        }
        if (l >= x && r <= y && !pred(info[p])) {
            return -1;
        }
        if (r - l == 1) {
            return l;
        }
        int m = (l + r) / 2;
        int res = findFirst(2 * p, l, m, x, y, pred);
        if (res == -1) {
            res = findFirst(2 * p + 1, m, r, x, y, pred);
        }
        return res;
    }
    template<class F>
    int findFirst(int l, int r, F &&pred) {
        return findFirst(1, 0, n, l, r, pred);
    }
    
    template<class F>
    int findLast(int p, int l, int r, int x, int y, F &&pred) {
        if (l >= y || r <= x) {
            return -1;
        }
        if (l >= x && r <= y && !pred(info[p])) {
            return -1;
        }
        if (r - l == 1) {
            return l;
        }
        int m = (l + r) / 2;
        int res = findLast(2 * p + 1, m, r, x, y, pred);
        if (res == -1) {
            res = findLast(2 * p, l, m, x, y, pred);
        }
        return res;
    }
    template<class F>
    int findLast(int l, int r, F &&pred) {
        return findLast(1, 0, n, l, r, pred);
    }
};

constexpr i64 inf = 1E18 + 1;

struct Info {
    i64 sum = 0;
    int sumAnd = ~0;
    i64 maxSub = -inf;
    i64 pre = -inf;
    i64 suf = -inf;
};

Info operator+ (const Info &a, const Info &b) {
    Info c;
    c.sum = a.sum + b.sum;
    c.sumAnd = a.sumAnd & b.sumAnd;
    c.maxSub = std::max({a.suf + b.pre, a.maxSub, b.maxSub});
    c.pre = std::max(a.pre, a.sum + b.pre);
    c.suf = std::max(b.suf, a.suf + b.sum);
    return c;
}



LazySegmentTree：

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
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
template<class Info, class Tag>
struct LazySegmentTree {
    int n;
    std::vector<Info> info;
    std::vector<Tag> tag;
    LazySegmentTree() : n(0) {}
    LazySegmentTree(int n_, Info v_ = Info()) {
        init(n_, v_);
    }
    template<class T>
    LazySegmentTree(std::vector<T> init_) {
        init(init_);
    }
    void init(int n_, Info v_ = Info()) {
        init(std::vector(n_, v_));
    }
    template<class T>
    void init(std::vector<T> init_) {
        n = init_.size();
        info.assign(4 << std::__lg(n), Info());
        tag.assign(4 << std::__lg(n), Tag());
        std::function<void(int, int, int)> build = [&](int p, int l, int r) {
            if (r - l == 1) {
                info[p] = init_[l];
                return;
            }
            int m = (l + r) / 2;
            build(2 * p, l, m);
            build(2 * p + 1, m, r);
            pull(p);
        };
        build(1, 0, n);
    }
    void pull(int p) {
        info[p] = info[2 * p] + info[2 * p + 1];
    }
    void apply(int p, const Tag &v) {
        info[p].apply(v);
        tag[p].apply(v);
    }
    void push(int p) {
        apply(2 * p, tag[p]);
        apply(2 * p + 1, tag[p]);
        tag[p] = Tag();
    }
    void modify(int p, int l, int r, int x, const Info &v) {
        if (r - l == 1) {
            info[p] = v;
            return;
        }
        int m = (l + r) / 2;
        push(p);
        if (x < m) {
            modify(2 * p, l, m, x, v);
        } else {
            modify(2 * p + 1, m, r, x, v);
        }
        pull(p);
    }
    void modify(int p, const Info &v) {
        modify(1, 0, n, p, v);
    }
    Info rangeQuery(int p, int l, int r, int x, int y) {
        if (l >= y || r <= x) {
            return Info();
        }
        if (l >= x && r <= y) {
            return info[p];
        }
        int m = (l + r) / 2;
        push(p);
        return rangeQuery(2 * p, l, m, x, y) + rangeQuery(2 * p + 1, m, r, x, y);
    }
    Info rangeQuery(int l, int r) {
        return rangeQuery(1, 0, n, l, r);
    }
    void rangeApply(int p, int l, int r, int x, int y, const Tag &v) {
        if (l >= y || r <= x) {
            return;
        }
        if (l >= x && r <= y) {
            apply(p, v);
            return;
        }
        int m = (l + r) / 2;
        push(p);
        rangeApply(2 * p, l, m, x, y, v);
        rangeApply(2 * p + 1, m, r, x, y, v);
        pull(p);
    }
    void rangeApply(int l, int r, const Tag &v) {
        return rangeApply(1, 0, n, l, r, v);
    }
    
    template<class F>
    int findFirst(int p, int l, int r, int x, int y, F &&pred) {
        if (l >= y || r <= x) {
            return -1;
        }
        if (l >= x && r <= y && !pred(info[p])) {
            return -1;
        }
        if (r - l == 1) {
            return l;
        }
        int m = (l + r) / 2;
        push(p);
        int res = findFirst(2 * p, l, m, x, y, pred);
        if (res == -1) {
            res = findFirst(2 * p + 1, m, r, x, y, pred);
        }
        return res;
    }
    template<class F>
    int findFirst(int l, int r, F &&pred) {
        return findFirst(1, 0, n, l, r, pred);
    }
    template<class F>
    int findLast(int p, int l, int r, int x, int y, F &&pred) {
        if (l >= y || r <= x) {
            return -1;
        }
        if (l >= x && r <= y && !pred(info[p])) {
            return -1;
        }
        if (r - l == 1) {
            return l;
        }
        int m = (l + r) / 2;
        push(p);
        int res = findLast(2 * p + 1, m, r, x, y, pred);
        if (res == -1) {
            res = findLast(2 * p, l, m, x, y, pred);
        }
        return res;
    }
    template<class F>
    int findLast(int l, int r, F &&pred) {
        return findLast(1, 0, n, l, r, pred);
    }
};

struct Tag {
    int x = 0;
    void apply(const Tag &t) & {
        x = std::max(x, t.x);
    }
};

struct Info {
    int x = 0;
    void apply(const Tag &t) & {
        x = std::max(x, t.x);
    }
};

Info operator+(const Info &a, const Info &b) {
    return {std::max(a.x, b.x)};
}

欧拉筛：

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
std::vector<int> minp, primes;

void sieve(int n) {
    minp.assign(n + 1, 0);
    primes.clear();
    
    for (int i = 2; i <= n; i++) {
        if (minp[i] == 0) {
            minp[i] = i;
            primes.push_back(i);
        }
        
        for (auto p : primes) {
            if (i * p > n) {
                break;
            }
            minp[i * p] = p;
            if (p == minp[i]) {
                break;
            }
        }
    }
}

bool isprime(int n) {
    return minp[n] == n;
}

离散化：

1
2
3
4
5
std::sort(v.begin(), v.end());
v.erase(std::unique(v.begin(), v.end()), v.end());
for (int i = 0; i < n; i++) {
	a[i] = std::lower_bound(v.begin(), v.end(), a[i]) - v.begin();
}

双指针

1
2
3
4
5
6
7
8
for (int x = 0, y = -1; x <= n; x++) {
    if (x < n && s[x] == 'A') {
        ans++;
    } else {
        min = std::min(min, x - y - 1);
        y = x;
    }
}

单调栈

1
2
3
4
5
6
7
8
9
10
11
12
13
std::vector<int> stk;
for (int i = 0; i < N; i++) {
    while (!stk.empty() && A[i] > A[stk.back()]) {
        stk.pop_back();
    }

    if (!stk.empty()) {
        ans[i] = -1;
    } else {
        ans[i] = stk.back();
    }
    stk.push_back(i);
}

单调队列

1
2
3
4
5
6
7
8
9
10
11
12
13
std::deque<int> q;
for (int i = 0; i < n; i++) {
	while (!q.empty() && a[i] >= a[q.back()]) {
		q.pop_back();
	}
	q.push_back(i);
	if (i - q.front() > k - 1) {
		q.pop_front();
	}
	if (i >= k - 1) {
		max[i] = a[q.front()];
	}
}

二维单调队列

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
std::vector<std::vector<int>> rowMin(a, std::vector<int>(b - n + 1)), rowMax(a, std::vector<int>(b - n + 1));
for (int x = 0; x < a; x++) {
	std::deque<int> qMin, qMax;
	for (int y = 0; y < b; y++) {
		while (!qMin.empty() && g[x][y] <= g[x][qMin.back()]) {
			qMin.pop_back();
		}
		qMin.push_back(y);
		if (y - qMin.front() > n - 1) {
			qMin.pop_front();
		}
		if (y >= n - 1) {
			rowMin[x][y - n + 1] = g[x][qMin.front()];
		}
	}

	for (int y = 0; y < b; y++) {
		while (!qMax.empty() && g[x][y] >= g[x][qMax.back()]) {
			qMax.pop_back();
		}
		qMax.push_back(y);
		if (y - qMax.front() > n - 1) {
			qMax.pop_front();
		}
		if (y >= n - 1) {
			rowMax[x][y - n + 1] = g[x][qMax.front()];
		}
	}
}

std::vector<std::vector<int>> min(a - n + 1, std::vector<int>(b - n + 1)), max(a - n + 1, std::vector<int>(b - n + 1));
for (int y = 0; y < b - n + 1; y++) {
	std::deque<int> qMin, qMax;
	for (int x = 0; x < a; x++) {
		while (!qMin.empty() && rowMin[x][y] <= rowMin[qMin.back()][y]) {
			qMin.pop_back();
		}
		qMin.push_back(x);
		if (x - qMin.front() > n - 1) {
			qMin.pop_front();
		}
		if (x >= n - 1) {
			min[x - n + 1][y] = rowMin[qMin.front()][y];
		}
	}
	for (int x = 0; x < a; x++) {
		while (!qMax.empty() && rowMax[x][y] >= rowMax[qMax.back()][y]) {
			qMax.pop_back();
		}
		qMax.push_back(x);
		if (x - qMax.front() > n - 1) {
			qMax.pop_front();
		}
		if (x >= n - 1) {
			max[x - n + 1][y] = rowMax[qMax.front()][y];
		}
	}
}

dijkstra

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
std::vector<std::vector<std::pair<int, i64>>> g(n);
   for (int i = 0; i < m; i++) {
       int u, v;
       i64 w;
       std::cin >> u >> v >> w;
       u--;
       v--;
       g[u].push_back({v, w});
       g[v].push_back({u, w});
   }

   
   std::vector<i64> dis(n, INF);
   std::priority_queue<std::pair<i64,int>, std::vector<std::pair<i64,int>>, std::greater<std::pair<i64,int>>> pq;

   pq.emplace(0, T);
dis[T] = 0;
   while (!pq.empty()) {
       i64 d = pq.top().first;
       int u = pq.top().second;
       pq.pop();
       if (d != dis[u]) {
       	continue;
       }
       for (int i = 0; i < g[u].size(); i++) {
           int v = g[u][i].first;
           i64 w = g[u][i].second;
           if (dis[v] > d + w) {
               dis[v] = d + w;
               pq.emplace(dis[v], v);
           }
       }
   }

dijkstra:

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

using i64 = long long;

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);

	int n, t;
	std::cin >> n >> t;

	std::vector<std::vector<std::pair<int, int>>> adj(n);
	for (int i = 0; i < t; i++) {
		int m;
		std::cin >> m;

		for (int j = 0; j < m; j++) {
			int u, v;
			std::cin >> u >> v;
			u--;
			v--;
			adj[u].emplace_back(v, i);
			adj[v].emplace_back(u, i);
		}
	}

	int k;
	std::cin >> k;

	std::vector<std::vector<int>> pos(t);
	for (int i = 0; i < k; i++) {
		int a;
		std::cin >> a;
		a--;
		pos[a].push_back(i);
	}

	std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<>> q;
	q.emplace(0, 0);
	std::vector<int> dis(n, -1);

	while (!q.empty()) {
		auto [d, x] = q.top();
		q.pop();

		if (dis[x] != -1) {
			continue;
		}
		dis[x] = d;

		for (auto [y, i] : adj[x]) {
			auto it = std::lower_bound(pos[i].begin(), pos[i].end(), d);
			if (it != pos[i].end()) {
				q.emplace(*it + 1, y);
			}
		}
	}

	std::cout << dis[n - 1] << "\n";

	return 0;
}

trie 树

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

using i64 = long long;

constexpr int N = 1E6 + 10;

int tot = 1;
int trie[N][26];
int cnt[N];


int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);

	int n;
	std::cin >> n;

	std::vector<std::string> s(n);
	i64 ans = 0;
	for (int i = 0; i < n; i++) {
		std::cin >> s[i];
		ans += s[i].size();

		int p = 1;
		for (auto c : s[i]) {
			int &q = trie[p][c - 'a'];
			if (!q) {
				q = ++tot;
			}
			p = q;
			cnt[p] += 1;
		}
	}

	ans *= 2 * n;
	for (int i = 0; i < n; i++) {
		std::reverse(s[i].begin(), s[i].end());

		int p = 1;
		for (auto c : s[i]) {
			int &q = trie[p][c - 'a'];
			if (!q) {
				break;
			}
			p = q;
			ans -= 2 * cnt[p];
		}
	}

	std::cout << ans << "\n";

	return 0;
}

公式

平方和：

__builtin_popcount(x): x 二进制下， 的个数。

组合数：

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
/**   组合数（小范围预处理，逆元+杨辉三角）
 *    2024-03-14: https://qoj.ac/submission/353877
 *    2023-10-06: https://qoj.ac/submission/203196
**/
constexpr int P = 1000000007;
constexpr int L = 10000;

int fac[L + 1], invfac[L + 1];
int sumbinom[L + 1][7];

int binom(int n, int m) {
    if (n < m || m < 0) {
        return 0;
    }
    return 1LL * fac[n] * invfac[m] % P * invfac[n - m] % P;
}

int power(int a, int b) {
    int res = 1;
    for (; b; b /= 2, a = 1LL * a * a % P) {
        if (b % 2) {
            res = 1LL * res * a % P;
        }
    }
    return res;
}

int main() {
    fac[0] = 1;
    for (int i = 1; i <= L; i++) {
        fac[i] = 1LL * fac[i - 1] * i % P;
    }
    invfac[L] = power(fac[L], P - 2);
    for (int i = L; i; i--) {
        invfac[i - 1] = 1LL * invfac[i] * i % P;
    }

    sumbinom[0][0] = 1;
    for (int i = 1; i <= L; i++) {
        for (int j = 0; j < 7; j++) {
            sumbinom[i][j] = (sumbinom[i - 1][j] + sumbinom[i - 1][(j + 6) % 7]) % P;
        }
    }
}

欢迎关注我的其它发布渠道