QBXT Jinan Day1

Posted on | In , | | Visitors:
Words count in article: 2.7k | Reading time ≈ 13


Day1 上午——高级数据结构

一、树状数组

基本功能

1.单点修改，前缀信息查询
2.区间修改可减信息，单点查询

对lowbit的理解

保留x中最后一位1（由位运算实现）

1
#define lowbit(x) (x&-x)

例题一:矩形数点

给定$n$个点坐标($x_i$,$y_i$)，q次询问，每次询问给出一个矩形的右上角坐标和左下角坐标，求矩形内包含给定点的个数
n, q $\leq$ $10^5$，0 $\leq$ $x_i$, $y_i$ $\leq$ $10^9$

思路

首先用容斥原理把矩形拆型四个二维偏序区域（形如$\sum$[$x_i$ $\leq$ $x$, $y_i$ $\leq$ $y$]）
将数据离散化，排序，此时$x$自然满足偏序结构，用树状数组根据$y$值维护前缀和即可

复杂度

O((n+q)logn)

例题二:逆序对

给定一个长度为$n$的序列，可以将其中任意个数字取相反数，求可以得到的最少逆序对数
$n$ $\le$ $10^5$，$\left|A_i \right|$ $\le$ $10^9$

思路

对于每个数字，我们发现$A_i$的正负只影响绝对值比$A_i$小的数，所以求出每个数$A_i$前后分别有多少数绝对值大于$A_i$，取较少的那一个就行了

二、线段树

例题一、序列操作

给定长度为$n$的序列$A$，执行$q$次操作，支持区间加、区间赋值、查询区间和、查询区间最大值

思路

线段树模板

例题二、环上连续最大和

给定一个长度为$n$的环形序列$A$，其中$A_1$与$A_n$是相邻的。$q$次操作，每次操作更改$A_x=v$。对于每次修改输出最大连续和
$n,q\le10^5,1\le x\le n,\left|A_i\right|,\left|v\right|\le10^9$

思路

线段树维护一下最小前缀和，最小后缀和与最小连续和，考虑到题目中的序列为环形，最大环形序列可能是两段互不相交的前缀与后缀，用总和减去最小子序列就行了。

例题三、SDOI2016 游戏

题面见P4069

思路

树链剖分+李超线段树

代码

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
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
#include <bits/stdc++.h>
#define jh(x,y) x^=y^=x^=y
#define rg register
#define inl inline
typedef long long ll;
const int N = 2e5 + 5;
const ll INF = 123456789123456789;
using namespace std;
namespace fast_IO {
    inl ll read()
    {
        rg ll num = 0;
        rg char ch;
        rg bool flag = false;
        while ((ch = getchar()) == ' ' || ch == '\n' || ch == '\r');
        if (ch == EOF)return ch; if (ch == '-')flag = true; else num = ch ^ 48;
        while ((ch = getchar()) != ' '&&ch != '\n'&&ch != '\r'&&~ch)
            num = (num << 1) + (num << 3) + (ch ^ 48);
        if (flag)return -num; return num;
    }
    inl ll max(rg ll a, rg ll b) { if (a > b)return a; return b; }
    inl ll min(rg ll a, rg ll b) { if (a < b)return a; return b; }
    void write(rg long long x) { if (x < 0)putchar('-'), x = -x; if (x >= 10)write(x / 10); putchar(x % 10 ^ 48); }
};
ll pos[N], id, ssize[N], fa[N], p[N], w[N], b[N], h[N], nt[N], num, son[N], deep[N], belong[N], dist[N];
inl void add(rg ll z, rg int y, rg int x)
{
    b[++num] = y, w[num] = z;
    nt[num] = p[x], p[x] = num;
    b[++num] = x, w[num] = z;
    nt[num] = p[y], p[y] = num;
}
void dfs1(rg int x)
{
    ssize[x] = 1;
    for (rg int e = p[x]; e; e = nt[e])
    {
        rg int k = b[e];
        if (k == fa[x])continue;
        fa[k] = x, deep[k] = deep[x] + 1;
        dist[k] = dist[x] + w[e];
        dfs1(k);
        if (ssize[son[x]] < ssize[k])son[x] = k;
        ssize[x] += ssize[k];
    }
}
void dfs2(rg int x, rg int chain_number)
{
    belong[x] = chain_number;
    pos[x] = ++id; h[id] = x;
    if (son[x])dfs2(son[x], chain_number);
    for (rg int e = p[x]; e; e = nt[e])
    {
        rg int k = b[e];
        if (k == fa[x] || k == son[x])continue;
        dfs2(k, k);
    }
}
struct Line {
    ll k, b;
    Line() { k = 0, b = INF; }
    Line(rg ll k, rg ll b) :k(k), b(b) {}
};
struct Node {
    int left, right;
    ll min, l, r;
    Line delta;
    Node() { min = INF; delta.b = INF; }
}tree[N << 2];
void build(rg int x, rg int l, rg int r)
{
    tree[x].left = l, tree[x].right = r;
    if (l == r) { tree[x].l = tree[x].r = dist[h[l]]; return; }
    rg int mid = l + r >> 1;
    build(x << 1, l, mid), build(x << 1 | 1, mid + 1, r);
    tree[x].l = tree[x << 1].l; tree[x].r = tree[x << 1 | 1].r;
}
inl ll f(rg ll x, rg ll k, rg ll b) { return k * x + b; }
inl void apply(rg int x, rg ll k, rg ll b)
{
    rg ll nl = f(tree[x].l, k, b), nr = f(tree[x].r, k, b),
        l = f(tree[x].l, tree[x].delta.k, tree[x].delta.b), r = f(tree[x].r, tree[x].delta.k, tree[x].delta.b);
    if (nl <= l && nr <= r)
    {
        tree[x].delta = Line(k, b);
        tree[x].min = fast_IO::min(tree[x].min, fast_IO::min(nl, nr));
        return;
    }
    if (nl > l&&nr > r)return;
    rg ll tmp = (b - tree[x].delta.b) / (tree[x].delta.k - k);
    rg ll mid = tree[x << 1].r;
    if (nl <= l || tmp <= mid)apply(x << 1, k, b);
    if (nr <= r || tmp > mid)apply(x << 1 | 1, k, b);
    tree[x].min = fast_IO::min(tree[x].min, fast_IO::min(tree[x << 1].min, tree[x << 1 | 1].min));
}
void addline(rg int x, rg int l, rg int r, rg ll k, rg ll b)
{
    if (tree[x].left >= l && tree[x].right <= r)
    {
        apply(x, k, b);
        return;
    }
    rg int mid = tree[x].left + tree[x].right >> 1;
    if (l <= mid)addline(x << 1, l, r, k, b);
    if (r > mid)addline(x << 1 | 1, l, r, k, b);
    tree[x].min = fast_IO::min(tree[x].min, fast_IO::min(tree[x << 1].min, tree[x << 1 | 1].min));
}
inl void addLine(rg int x, rg int y, rg ll k, rg ll b)
{
    while (belong[x] != belong[y])
    {
        if (deep[belong[x]] < deep[belong[y]])jh(x, y);
        addline(1, pos[belong[x]], pos[x], k, b);
        x = fa[belong[x]];
    }
    if (pos[x] > pos[y])jh(x, y);
    addline(1, pos[x], pos[y], k, b);
}
inl int LCA(rg int x, rg int y)
{
    while (belong[x] != belong[y])
    {
        if (deep[belong[x]] < deep[belong[y]])jh(x, y);
        x = fa[belong[x]];
    }
    if (deep[x] < deep[y])return x;
    return y;
}
inl void tian()
{
    rg int s = fast_IO::read(), t = fast_IO::read();
    rg ll k = fast_IO::read(), b = fast_IO::read();
    rg int lca = LCA(s, t);
    addLine(s, lca, -k, k*dist[s] + b);
    addLine(lca, t, k, k*dist[s] - 2 * k*dist[lca] + b);
}
ll querymin(rg int x, rg int l, rg int r)
{
    rg ll ans = INF, mid = tree[x].left + tree[x].right >> 1;
    if (l <= tree[x].left&&r >= tree[x].right)return tree[x].min;
    if (l <= mid)ans = fast_IO::min(ans, querymin(x << 1, l, r));
    if (r > mid)ans = fast_IO::min(ans, querymin(x << 1 | 1, l, r));
    l = fast_IO::max(l, tree[x].left), r = fast_IO::min(r, tree[x].right);
    ans = fast_IO::min(ans, f(dist[h[l]], tree[x].delta.k, tree[x].delta.b));
    ans = fast_IO::min(ans, f(dist[h[r]], tree[x].delta.k, tree[x].delta.b));
    return ans;
}
inl ll queryMin(rg int x, rg int y)
{
    rg ll ans = INF;
    while (belong[x] != belong[y])
    {
        if (deep[belong[x]] < deep[belong[y]])jh(x, y);
        ans = fast_IO::min(ans, querymin(1, pos[belong[x]], pos[x]));
        x = fa[belong[x]];
    }
    if (pos[x] > pos[y])jh(x, y);
    return fast_IO::min(ans, querymin(1, pos[x], pos[y]));
}
inl ll query()
{
    rg int s = fast_IO::read(), t = fast_IO::read();
    return queryMin(s, t);
}

int main(void)
{
    rg int n = fast_IO::read(), m = fast_IO::read();
    for (rg int i = 1; i != n; ++i)add(fast_IO::read(), fast_IO::read(), fast_IO::read());
    dfs1(1), dfs2(1, 1), build(1, 1, n);
    while (m--)
        switch (fast_IO::read())
        {
        case 1:tian(); break;
        case 2:printf("%lld\n", query()); break;
        }
    return 0;
}

三、可并堆（左偏树）

左偏树呈二叉树结构，除维护权值信息外，还需要维护子树内最近叶结点的距离$d_x$。

例题一、Dispatching

题面见P1552。

思路

考虑到如果某个忍者当管理员时不选$x$忍者，那么这个忍者的直接上级一定不会选$x$。
使用左偏树维护以$x$为根子树内派遣忍者名单，它需要满足大根堆的性质，不断删除堆顶直到总和$\le m$。

代码

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
#include <bits/stdc++.h>
#define jh(x,y) x^=y^=x^=y
#define rg register
#define inl inline
typedef long long ll;
const int N = 1e5 + 5;
using namespace std;
namespace fast_IO {
    inl ll read()
    {
        rg ll num = 0;
        rg char ch;
        rg bool flag = false;
        while ((ch = getchar()) == ' ' || ch == '\n' || ch == '\r');
        if (ch == EOF)return ch; if (ch == '-')flag = true; else num = ch ^ 48;
        while ((ch = getchar()) != ' '&&ch != '\n'&&ch != '\r'&&~ch)
            num = (num << 1) + (num << 3) + (ch ^ 48);
        if (flag)return -num; return num;
    }
    inl ll max(rg ll a, rg ll b) { if (a > b)return a; return b; }
    inl ll min(rg ll a, rg ll b) { if (a < b)return a; return b; }
    void write(rg long long x) { if (x < 0)putchar('-'), x = -x; if (x >= 10)write(x / 10); putchar(x % 10 ^ 48); }
};
int fa[N], n, lson[N], rson[N], d[N], root[N], ssize[N];
ll c[N], m, l[N], sum[N], ans;
int merge(rg int x, rg int y)
{
    if (!x || !y)return x | y;
    if (c[x] < c[y])jh(x, y);
    rson[x] = merge(rson[x], y);
    if (d[lson[x]] < d[rson[x]])jh(lson[x], rson[x]);
    d[x] = d[rson[x]] + 1;
    return x;
}


int main(void)
{
    n = fast_IO::read(), m = fast_IO::read();
    for (rg int i = 1; i <= n; ++i)
        fa[i] = fast_IO::read(), sum[i] = c[i] = fast_IO::read(),
        l[i] = fast_IO::read(), root[i] = i, ssize[i] = 1,
        ans = fast_IO::max(ans, l[i]);
    for (rg int i = n; i != 1; --i)
    {
        root[fa[i]] = merge(root[i], root[fa[i]]);
        sum[fa[i]] += sum[i]; ssize[fa[i]] += ssize[i];
        while (sum[fa[i]] > m)
        {
            sum[fa[i]] -= c[root[fa[i]]];
            root[fa[i]] = merge(lson[root[fa[i]]], rson[root[fa[i]]]);
            --ssize[fa[i]];
        }
        ans = fast_IO::max(ans, l[fa[i]] * ssize[fa[i]]);
    }
    fast_IO::write(ans);
    return 0;
}

线段树的合并

线段树要合并，必须要有相同的结构，均摊复杂度$O(log n)$。

四、平衡树

Treap——Treep=Tree+Heap

Treap通过单旋保持堆性质。树高期望$O(logn)$

启发式合并

合并两棵$Treap$的时候，只需要暴力遍历较小的 Treap 提取所有结点，然后依次插入到较大的$Treap$之中就好了。
很多数据结构都可以用启发式合并

例题一、Peaks

题面见P4197

思路

将道路和询问混在一起排序，进行$Kruskal$算法的同时用$Treap $维护连通分量内所有山峰的高度。

Splay

Splay借助双旋操作（zig_zag）。

例题二、序列终结者

题面见P4146。

思路

Splay维护翻转、子树最值、addv标记。

例题三、三维偏序

思路

线段树套平衡树

Day1 下午

五、嵌套数据结构

嵌套数据结构的思想是将普通的数据结构维护的信息拓展成另一
种数据结构（可能与第一维数据结构相同）

树套树

常见的有树状数组套平衡树，线段树套权值线段树等。
注意，第一维的数据结构应该尽量简单，可以节约空间减小时间复杂度。

例题一、Mokia

题面见P4390。

思路

树状数组套Splay

六、可持久化线段树（主席树）

可持久化数据结构

可持久化数据结构就是利用函数式编程的思想使其支持询问历史版本，同时充分利用它们之间的共同数据来减少时间和空间消耗

大致的思想就是只新建不修改，保存历史版本

例题一、静态区间第k小

题面见P3834。

思路

主席树模板题

不是很懂。。。弄明白以后再补

总结

数据结构是很重要的基础。
讲课好快…今天的例题只敲出来两个，其他的还得以后慢慢做