Jeekr's site
0%

Posted on Edited on

2018/10/10考试记录

今天考试内容比较没有头绪，第一道题看样子是序列上的dp，好像又有后效性，就很无奈。干脆写了随机化，最后拿了50分。正解确实是dp，裸的dp能拿50分，如果用Lowerbound和线段树来初始化，用线段树转移状态，就能拿到满分。时间复杂度为\(O(n\log_2n)\)，要注意一些细节，改了很久。

顺便一提，bool operator<(const T &o)在某些环境下是无法编译通过的，但是在某些环境上却可以编译通过，与-std=c++98选项无关，与警告无关。(T){xxxx}也是一样，但是c++11标准是明确支持的，这两个可能会导致CE。为了避免CE，还是手动写一个struct的构造函数为好，最好是以额外的函数形式写。

第二题同样是没有什么头绪，也写了随机化算法，拿到了30分，但是花费了不少时间。第二题解决方法有二：枚举中间节点，跑最小生成树，或者附加状态的dp，或者叫状压dp。

第三题的暴力，可以枚举根节点，跑树状背包。正解是树分治，可惜没有学。

距离NOIP还有30天，需要加倍努力，进省队还是有希望的。

10.16 得分记录

T1 第一题是简单的模拟，首先预处理出\(s[i] = min\{x_j\}(j \le i)\)，设p指向数组末端，从p向前查找第一个大于\(x_i\)的位置，然后把这个位置改为0，重复这个步骤，直到处理完所有输入，或者\(p == 0\)，然后输出\(p\)即可。

T2 这一道题的正解是排序+贪心+并查集，首先将所有的海拔从低到高排序，然后取出其中最低的一个，如果是属于A城市，则连向周围的遍历过的一个点，重复这个步骤，直到所有的A城市的点都于其他点合并了起来。考试的时候没有什么好的思路，于是随机化+卡时，好像拿了30分。

T3 这一题的做法有很多，暴力分能到70甚至90分，常见的做法是：数链剖分、dfs序+数据结构，都可以树状数组/线段树来做。还有做法是利用并查集的路径压缩思想，可以过90分的点。

T4 正解是枚举从左边切的最大次数，然后按照上下左右的顺序切割，直到完成任务。这些做完之后，将图翻转90°，重复。当时写了个有些问题的贪心，只有20分。

10-20

今天考了分治，但是几道题都没有用分治做。 - 第一题是栅栏涂色，没有想到怎么写，甚至连贪心都没有写出来，是个失误。正解是考虑[L,R]，高度>H的一段，要么这一段竖直涂色，要么全部水平涂色，然后就求水平涂色的上方的一段。 - 第二题的思路是，二分最大价格，利用所有价格小于它的边建最小生成树，直到所有有冲突的点都被连接起来。瓶颈在找有冲突的点，相当于找平面最近点对。 - 第三题是求\(k^s\mod m\)，其中s非常大，一个方法是利用拓展欧拉定理，将s转成longlong来操作，另一个方法是直接将s看做n进制数，然后进行快速幂，这个不容易出错。 - 第四题不妨称为斐波那契图，20分的数据是\(n,m\le10\)，50分的数据是\(n\le16, m \le 1e5\)，当时只想到了50分的做法，没想到成了最高分。只是递推出了第n张图，然后直接跑最短路，但这样是\(O(Vm)\)的，不过可以离线处理，复杂度降到了\(O(V^2)\)，踩了题解中的50分做法。标程是首先与处理出每张图的第一个点第一个点到最后一个点的距离，然后得出u,v到最近的割点的距离，再计算割点之间的距离，不需要建图，能过n<1000的点。（但是实际上，它不处理n>80的部分，因为再向上就会爆longlong。

Posted on Edited on

事情缘由

事情是这样的，今天第二次做"关押罪犯”一题，奇迹般的MLE了4个点。

一开始想要优化并查集点写法，不想费事初始化，于是有了以下代码 

1
2
3
4
5
6
7
8
9
10
11
int f[N];
int find(int x)
{
    if(f[x])
        return f[x] = find(f[x]);
    return x;
}
void merge(int x, int y)
{
    f[find(x)] = find(y);
}
看着没有什么问题。

事情的发展

后来发现把代码改成这样就没有问题了。 

1
2
3
4
5
6
7
int find(int x)
{
    if(f[x] != x)
        return f[x] = find(f[x]);
    return x;
}
//加初始化
但是这样又违背了初衷，感觉很奇怪。 ## 事情的解决 在十几篇博客中的某篇博客的注释中，发现了我的问题所在：如果merge(i,i)，也就是在同一棵子树上的两个节点，再find(i)，就会认为某个节点是子节点，它的父节点也是自己，造成死循环/无限递归，至于是M还是T，取决于时间空间限制。做如下改动就行了 
1
2
3
4
5
void merge(int x, int y)
{
    int rx = find(x), ry = find(y);
	rx != ry ? f[rx] = find(ry): 0 ;
}

Posted on Edited on

本站切换了自己写的WP-ReliableMD插件，现测试效果

image \(E=mc^2\) linline math \(f(x)=x^2\) block math 
1
e^{i\pi}+1=0
# GFM Markdown ## Heading 2 ### Heading 3 #### Heading 4 ##### Heading 5 ###### Heading 6 code block 
1
console.log("fenced code block");
**HTML block**
  • list
    • list indented
  1. ordered
  2. list
    1. ordered list
    2. indented
  • task
  • list completed

link > block quote --- horizontal line ** code, italic*, bold, strikethrough, Red color

Table Cell Merge

@cols=2:merged
table table

Charts

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
,Budget,Income,Expenses,Debt
June,5000,8000,4000,6000
July,3000,1000,4000,3000
Aug,5000,7000,6000,3000
Sep,7000,2000,3000,1000
Oct,6000,5000,4000,2000
Nov,4000,3000,5000,4000

type: column
title: Monthly Revenue
width: 465
x.title: Amount
y.title: Month
y.suffix: $
legend.visible: false

UML

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class BaseClass

namespace net.dummy #DDDDDD {
    .BaseClass <|-- Person
    Meeting o-- Person

    .BaseClass <|- Meeting
}

namespace net.foo {
  net.dummy.Person  <|- Person
    .BaseClass <|-- Person

  net.dummy.Meeting o-- Person
}

BaseClass <|-- net.unused.Person

Posted on Edited on

今天是WP-ReliableMD立项的第二天。 项目介绍： 制作一个能够使用的、坑少的WP markdown插件。目前我使用的插件是WP-Editor.MD，作者弃坑，踢出了全部的群成员。另一个群里的群主@起航天空 有了这个想法，邀请我一起开发，我接受了。 GitHub 2018-9-29

可视化编辑器决定修改summernote的源代码 20189-9-30

Posted on Edited on

9-21 今天上午做了三题： Run 最小生成树+倍增，可能是倍增写错了，爆零，需要继续调试。后来发现倍增确实写错了，但是没有再次调试这道题。 Nim 涉及到博弈论，不会做。正解是奇数行的亦或值是否为1 Toy 应该是树形dp，我写了暴力。正解是选或不选这个点，如果不选这个点，子节点就必须有选的 下午： Sequence 正解是O(n)算法，我只想到了O(n^2)的模拟算法，需要进一步研究。 Word 涉及到高深的技术和kmp字符串匹配，没有想到怎么做 Car 一开始模仿八皇后写了搜索算法，时间复杂度略高，后来改成了状压dp，因为有一个状态被遗漏了，WA，后来该上了，应该能AC。 9-22 今天到noi.ac上打比赛，只拿到了60分暴力分。 第一题，count 组合数学题，for I = 1..n+1 do ans[i] = C(n+1, i) – C(L+R, I – 1)。调试的时候，由于组合数复杂度太高而T，后来由于模后数相减没有调整为正数，卡了好久。还要背过逆元递推式，并进行阶乘的预处理，O(n) 第二题，delete，首先是DP，60分，研究DP的转移状态，得到二维偏序问题，sort后做LIS即可，O(nlogn) 第三题，涉及到树剖，没有研究。

另外研究了昨天的LCA问题，洛谷上LCA如果用倍增法，不用读入优化会T，而ST表求RMQ则不会T，昨天T1需要求额外的信息，就不能用ST表来做了

9-23 今天考了几道题，isbn、connect和drive Isbn水过了。 Connect 爆了0，后来研究发现，是printf输出符号打错了，lf达成了ld。修改后只有45分，调整模拟退火算法的参数后75.查看题解，发现正解是枚举+最大生成树。 照题解修改程序后发现是95分，后来查出，是循环内使用es数组数据，而sort改变了es数组的顺序，进而有一组数据没有通过。谨以记之。 第三题是图上dp，实际上也可以不建图，常数略大而已。写的时候有一点小问题，gdb调了半天，发现时复制样例输入的时候复制错了，程序本身没有问题。 9-24 今天上午做了: Toy: dp+斜率优化。考试的时候看错了题意，写了贪心，没有得分。下午和晚上学习了斜率优化，打算配合相关的题目练习一下。 Fence：据说是要用单调队列计算对答案的贡献。没有研究。 Sequence: 据说要用单调队列优化，或者是某种奇怪的贪心。 Apple dp+优化（离散化+排序）

9-25 上午做了dp优化系列2，以为是有两道题以为是贪心，结果是错误的。 第一题garden非常诡异，当时搜索没有写出来，就放弃了。题意是，只能是长条和矩形，这样才能保证距离是曼哈顿距离 第二题写了搜索，可能剪枝剪得太厉害了，只过了样例。正解是m=2时的答案最大，按照l, r排序后，用单调栈维护状态、更新答案。 第三道题是某种贪心、也使用单调栈维护。 第四题是某种dp，和编辑距离有关，我写了搜索，搜到了小部分的分。后来在推dp方程，没有推出来。 另外提交答案的时候，输出搞错了，要注意一下。 晚上研究了树链剖分，被某种有坑的文章坑了好久。

9-26 今天没有考试，研究了一些零散的dp题，在洛谷上做了一些，感觉不是很熟练，需要进一步练习

9-27 今天考试内容是图论，二分图匹配。 城堡守卫，当时写了搜索，A1W1T8，应该是搜索剪枝厉害了，正解是每行设置一个编号，遇到墙则断开，然后每列这么处理，同时又可以站立的格子，则把当前格子所属的行列编号连边，进行二分图匹配或网络流。 序列变换，距离公式是还上距离，当时写了搜索。正解是裸的二分图匹配，从大到小开始匹配，匹配时从小到大，如果不能完全匹配则No Answer，完全匹配则输出匹配内容。 机器调度，考场上写了spfa+map的最短路问题，同时将问题简化，认为调度时只能依次处理，骗到了70分。正解是modA和modB连边，直接二分图匹配。 导弹，第一题是求同时满足三维的最长上升子序列，直接连边求最长路即可，spfa会被卡一个点，记忆化dfs可以过，第二题是求小路径覆盖问题，根据公式 最小路径覆盖=点数-最大匹配，套用匈牙利算法解决。预处理需要o(n^2)，由于没有时间限制，所以每次必须遍历所有的点。似乎可以排序后遍历一部分，常数会小很多，但没必要。

Posted on Edited on

欧拉线性筛

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int pri[50000], phi[50000], len;
void calc_phi(int n)
{
    phi[1] = 1;
    for(int i=2;i<=n;i++)
    {
        if(!phi[i])
        {
            pri[len++]=i;
            phi[i]=i-1;
        }
        for(int j=0;j<len&&pri[j]*i<=n;j++)
        {
            if(i%pri[j]==0)
            {
                phi[i*pri[j]]=pri[j]*phi[i];
                break;
            }
            else phi[i*pri[j]]=(pri[j]-1)*phi[i];
        }
    }
}

优化过的并查集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int pre[200010];
int find(int x)
{
    if(pre[x] > 0)
    {
        pre[x] = find(pre[x]);
        return pre[x];
    }
    return x;
}
void merge(int x, int y)
{
    int rx = find(x);
    int ry = find(y);
    if(rx == ry)
        return;
    if(-pre[rx] > -pre[ry])
        swap(rx, ry);
    pre[ry] += pre[rx] - 1;
    pre[rx] = ry;

}

tarjan 求割点

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
const int MAXN = 21000, MAXM = 100010;

int g[MAXN], cnt = 0;

struct edge {
    int t, nxt;
} e[MAXM * 2];
void add_edge(int u, int v) {
    e[++cnt].t = v;
    e[cnt].nxt = g[u];
    g[u] = cnt;
}


int dfn[MAXN], low[MAXN], fa[MAXN];
int is_cut[MAXN];

int ans = 0;

void tarjan(int i) {
    static int count = 0;
    int children = 0;
    bool cut = false;
    dfn[i] = low[i] = ++count;
    for (int j_ = g[i], j; j = e[j_].t, j_; j_ = e[j_].nxt) {
        if (!dfn[j]) {
            children += 1;
            fa[j] = i;
            tarjan(j);
            low[i] = min(low[i], low[j]);
            if (fa[i] && low[j] >= dfn[i]) {
                cut = true;
            }
        } else if (j != fa[i]) {
            low[i] = min(low[i], dfn[j]);
        }
    }
    if (cut || (fa[i] == 0 && children >= 2)) {
        is_cut[i] = 1;
        ans += 1;
    }
}

树链剖分和线段树

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
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
#include <iostream>
#include <cstring>

using namespace std;
typedef long long treetype;
const int MAXN = static_cast<const int> ( 1e6 + 5 );
int n, a[MAXN];
int MOD;

treetype sgt_query(int lft, int rht, int rt, int l, int r);

void sgt_update(int lft, int rht, int mul, int add, int rt, int l, int r);

treetype sgt_get_val(int rt);

struct edge {
    int t, n;
} es[MAXN];


int g[MAXN * 2];
int len;

void addedge(int a, int b) {
    es[++len].t = b;
    es[len].n = g[a];
    g[a] = len;
}


int wt[MAXN], fat[MAXN], dep[MAXN], siz[MAXN], hvy[MAXN], id[MAXN], top[MAXN], cnt;


#define childs_in(root, j) for(int j##_ = g[root], j; j##_ && (j = es[j##_].t); j##_ = es[j##_].n)

void tcd_dfs1(int x, int f, int depth) {
    dep[x] = depth;
    fat[x] = f;
    siz[x] = 1;
    hvy[x] = 0;
    childs_in (x, s) {
        if (s == fat[x]) continue;
        tcd_dfs1(s, x, depth + 1);
        siz[x] += siz[s];
        if (!hvy[x] || siz[s] > siz[hvy[x]])
            hvy[x] = s;
    }
}


void tcd_dfs2(int x, int top_father) {
    id[x] = ++cnt;
    wt[cnt] = a[x];
    top[x] = top_father;
    if (hvy[x]) {
        tcd_dfs2(hvy[x], top_father);
        childs_in(x, s) {
            if (fat[x] == s || hvy[x] == s) continue;
            tcd_dfs2(s, s);
        }

    }
}


treetype tcd_query_sum(int x, int y) {
    treetype sum = 0;
    while (top[x] != top[y]) {
        if (dep[top[x]] < dep[top[y]])
            swap(x, y);
        (sum += sgt_query(id[top[x]], id[x], 1, 1, n)) %= MOD;
        x = fat[top[x]];
    }
    if (dep[x] > dep[y]) {
        swap(x, y);
    };
    return (sgt_query(id[x], id[y], 1, 1, n) + sum) % MOD;
}

void tcd_update(int x, int y, int mul, int add) {
    while (top[x] != top[y]) {
        if (dep[top[x]] < dep[top[y]])
            swap(x, y);
        sgt_update(id[top[x]], id[x], mul, add, 1, 1, n);
        x = fat[top[x]];
    }
    if (dep[x] > dep[y])
        swap(x, y);

    sgt_update(id[x], id[y], mul, add, 1, 1, n);
}


treetype tcd_query_son(int x) {
    return sgt_query(id[x], id[x] + siz[x] - 1, 1, 1, n);
}

void tcd_update_son(int x, int mul, int add) {
    return sgt_update(id[x], id[x] + siz[x] - 1, mul, add, 1, 1, n);
}


// segment tree part
treetype sum[MAXN * 4], lz_add[MAXN * 4], lz_mul[MAXN * 4];
#define ls rt<1
#define rs rt<1|1
#define lson ls,l,mid
#define rson rs,mid+1,r
#define md int mid = (l + r) >> 1;

inline void sgt_init_lazy(int rt) {
    lz_mul[rt] = 1;
}

inline void sgt_set_val(int rt, int x) {
    sum[rt] = wt[x];
}

inline treetype sgt_get_val(int rt) {
    return sum[rt];
}

inline void sgt_pushup(int rt) {
    sum[rt] = (sum[ls] + sum[rs]) % MOD;
}
inline void init_val(treetype &v)
{
    v = 0;
}
inline void change_val(treetype &v, treetype x)
{
    (v += x) %= MOD;
}


inline void sgt_change_node(int rt, int l, int r, treetype add, treetype mul) {
    if (mul != 1) {
        sum[rt] = sum[rt] * mul % MOD;
        lz_mul[rt] = lz_mul[rt] * mul % MOD;
        lz_add[rt] = lz_add[rt] * mul % MOD;
    }
    if (add) {
        sum[rt] = (sum[rt] + add * (r - l + 1)) % MOD;
        lz_add[rt] = (lz_add[rt] + add) % MOD;
    }
}

inline void sgt_pushdown(int rt, int l, int r) {
    if (lz_add[rt] || lz_mul[rt] != 1) {
        md;
        sgt_change_node(lson, lz_add[rt], lz_mul[rt]);
        sgt_change_node(rson, lz_add[rt], lz_mul[rt]);
        lz_add[rt] = 0;
        lz_mul[rt] = 1;
    }
}

void sgt_build(int rt, int l, int r) {
    sgt_init_lazy(rt);
    if (l == r) {
        sgt_set_val(rt, l);
        return;
    }
    md;
    if (l <= mid)
        sgt_build(lson);
    if (r > mid)
        sgt_build(rson);
    sgt_pushup(rt);
}

treetype sgt_query(int lft, int rht, int rt, int l, int r) {
    if (lft <= l && r <= rht) {
        return sgt_get_val(rt);
    }
    sgt_pushdown(rt, l, r);
    treetype val;
    init_val(val);
    md;
    if (lft <= mid)
        change_val(val, sgt_query(lft, rht, lson));
    if (rht > mid)
        change_val(val, sgt_query(lft, rht, rson));
    return val;
}


// first mul second add
void sgt_update(int lft, int rht, int mul, int add, int rt, int l, int r) {
    if (lft <= l && r <= rht) {
        sgt_change_node(rt, l, r, add, mul);
        return;
    }
    sgt_pushdown(rt, l, r);
    md;
    if (lft <= mid) sgt_update(lft, rht, mul, add, lson);
    if (rht > mid) sgt_update(lft, rht, mul, add, rson);
    sgt_pushup(rt);
}

inline void tcd_init(int r, int n)
{
    tcd_dfs1(r, 0, 1);
    tcd_dfs2(r, r);
    sgt_build(1, 1, n);

}
int main() {
    int m, r;
    cin >> n >> m >> r >> MOD;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    for (int i = 0; i < n - 1; ++i) {
        int a, b;
        cin >> a >> b;
        addedge(a, b);
        addedge(b, a);
    }

    tcd_init(r, n);

    for (int i = 0; i < m; ++i) {
        int t, a, b, c;
        cin >> t;
        switch (t) {
            case 1:
                cin >> a >> b >> c;
                tcd_update(a, b, 1, c);
                break;
            case 2:
                cin >> a >> b;
                cout < "<:" < tcd_query_sum(a, b) < endl;
                break;
            case 3:
                cin >> a >> b;
                tcd_update_son(a, 1, b);
                break;
            case 4:
                cin >> a;
                cout < "<:" < tcd_query_son(a) < endl;
                break;
            default:
                exit(-1);
        }
    }
    return 0;
}

用于维护序列的splay tree

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
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
#include <iostream>
#include <cstdio>
#include <cstring>
#include <stack>
#include <vector>
#include <algorithm>
#include <queue>

#define rep(i) for (int i=0; i<n; i++)
using namespace std;
typedef long long ll;
const int N = 100005, inf = 0x3f3f3f3f;


typedef struct splaynode *pNode;
struct splaynode {
    pNode pre, ch[2];
    ll value, lazy, max, sum;
    int size, rev;

    void init(ll v) {
        pre = ch[0] = ch[1] = NULL;
        max = value = sum = v;
        lazy = rev = 0;
        size = 1;
    }
} mem[N];

int memtop;

stack<pNode> S;
pNode root;

inline int get_size(pNode &x) {
    return x ? x->size : 0;
}

void pushdown(pNode &x) {
    if (!x) return;
    if (x->lazy) {
        ll w = x->lazy;
        x->value += w;
        if (x->ch[0]) {
            x->ch[0]->lazy += w;
            x->ch[0]->max += w;
            x->ch[0]->sum += w * get_size(x->ch[0]);
        }
        if (x->ch[1]) {
            x->ch[1]->lazy += w;
            x->ch[1]->max += w;
            x->ch[1]->sum += w * get_size(x->ch[1]);
        }
        x->lazy = 0;
    }
    if (x->rev) {
        pNode t = x->ch[0];
        x->ch[0] = x->ch[1];
        x->ch[1] = t;
        x->rev = 0;
        if (x->ch[0]) x->ch[0]->rev ^= 1;
        if (x->ch[1]) x->ch[1]->rev ^= 1;
    }
}

void update(pNode &x) {
    if (!x) return;
    x->size = 1;
    x->max = x->value;
    x->sum = x->value;
    if (x->ch[0]) {
        x->sum += x->ch[0]->sum;
        x->max = max(x->max, x->ch[0]->max);
        x->size += x->ch[0]->size;
    }
    if (x->ch[1]) {
        x->sum += x->ch[1]->sum;
        x->max = max(x->max, x->ch[1]->max);
        x->size += x->ch[1]->size;
    }
}

void rotate(pNode &x, int d) {
    pNode y = x->pre;
    pushdown(y);
    pushdown(x);
    pushdown(x->ch[d]);
    y->ch[!d] = x->ch[d];
    if (x->ch[d] != NULL) x->ch[d]->pre = y;
    x->pre = y->pre;
    if (y->pre != NULL) { if (y->pre->ch[0] == y) y->pre->ch[0] = x; else y->pre->ch[1] = x; }
    x->ch[d] = y;
    y->pre = x;
    update(y);
    if (y == root) root = x;
}

void splay(pNode &src, pNode &dst) {
    pushdown(src);
    while (src != dst) {
        if (src->pre == dst) {
            if (dst->ch[0] == src) rotate(src, 1); else rotate(src, 0);
            break;
        } else {
            pNode y = src->pre, z = y->pre;
            if (z->ch[0] == y) {
                if (y->ch[0] == src) {
                    rotate(y, 1);
                    rotate(src, 1);
                } else {
                    rotate(src, 0);
                    rotate(src, 1);
                }
            } else {
                if (y->ch[1] == src) {
                    rotate(y, 0);
                    rotate(src, 0);
                } else {
                    rotate(src, 1);
                    rotate(src, 0);
                }
            }
            if (z == dst) break;
        }
        update(src);
    }
    update(src);
}

void select(int k, pNode &f) {
    int tmp;
    pNode t = root;
    while (true) {
        pushdown(t);
        tmp = get_size(t->ch[0]);
        if (k == tmp + 1) break;
        if (k <= tmp) t = t->ch[0];
        else {
            k -= tmp + 1;
            t = t->ch[1];
        }
    }
    pushdown(t);
    splay(t, f);
}

inline void selectsegment(int l, int r) {
    select(l, root);
    select(r + 2, root->ch[1]);
}

void insert(int pos, ll value) {  //在pos位置后面插入一个新值value
    selectsegment(pos + 1, pos);
    pNode t;
    pNode x = root->ch[1];
    pushdown(root);
    pushdown(x);
    if (!S.empty()) {
        t = S.top();
        S.pop();
    } else {
        t = &mem[memtop++];
    }
    t->init(value);
    t->ch[1] = x;
    x->pre = t;
    root->ch[1] = t;
    t->pre = root;
    splay(x, root);
}

void add(int a, int b, int value) {  //区间[a,b]中的数都加上value
    selectsegment(a, b);
    pNode x = root->ch[1]->ch[0];
    pushdown(x);
    update(x);
    x->max += value;
    x->lazy += value;
    splay(x, root);
}

void reverse(int a, int b) {   //区间[a,b]中的数翻转
    selectsegment(a, b);
    root->ch[1]->ch[0]->rev ^= 1;
    pNode x = root->ch[1]->ch[0];
    splay(x, root);
}

void revolve(int a, int b, int t) { //区间[a,b]中的数向后循环移t位
    pNode p1, p2;
    selectsegment(a, b);
    select(b + 1 - t, root->ch[1]->ch[0]);
    p1 = root->ch[1]->ch[0];
    pushdown(p1);
    p2 = p1->ch[1];
    p1->ch[1] = NULL;

    select(a + 1, root->ch[1]->ch[0]);
    p1 = root->ch[1]->ch[0];
    pushdown(p1);
    p1->ch[0] = p2;
    p2->pre = p1;

    splay(p2, root);
}

ll getmax(int a, int b) {   //取[a,b]中最小的值
    selectsegment(a, b);
    pNode x = root->ch[1];
    pushdown(x);
    x = x->ch[0];
    pushdown(x);
    update(x);
    return x->max;
}

ll getsum(int a, int b) {
    selectsegment(a, b);
    pNode x = root->ch[1];
    pushdown(x);
    x = x->ch[0];
    pushdown(x);
    update(x);
    return x->sum;
}

void erase(int pos) {               //抹去第pos个元素
    selectsegment(pos, pos);
    pushdown(root->ch[1]);
    S.push(root->ch[1]->ch[0]);        //回收内存
    root->ch[1]->ch[0] = NULL;
    pNode x = root->ch[1];
    splay(x, root);
}


void cutandmove(int a, int b, int c) {
    selectsegment(a, b);
    pNode CutRoot = root->ch[1]->ch[0];
    CutRoot->pre = NULL;
    root->ch[1]->size -= CutRoot->size;
    root->ch[1]->ch[0] = NULL;

    selectsegment(c + 1, c);

    CutRoot->pre = root->ch[1];
    root->ch[1]->ch[0] = CutRoot;
    root->ch[1]->size += CutRoot->size;
}

void cut(int a, int b) {
    selectsegment(a, b);
    pNode CutRoot = root->ch[1]->ch[0];
    CutRoot->pre = NULL;
    root->size -= CutRoot->size;
    root->ch[1]->size -= CutRoot->size;
    root->ch[1]->ch[0] = NULL;
}

vector<ll> ans;

void inorder(pNode x) {
    if (!x) return;
    pushdown(x);
    inorder(x->ch[0]);
    if (x->value != inf) ans.push_back(x->value);
    inorder(x->ch[1]);
}

void init_splaytree(ll *a, int n) {
    memtop = 0;
    root = &mem[memtop++];
    root->init(inf);
    root->ch[1] = &mem[memtop++];
    root->ch[1]->init(inf);
    while (!S.empty()) S.pop();
    rep(i) insert(i, a[i]);
}

splay常见操作

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
179
180
181
182
183
184
185
#include <bits/stdc++.h>

using namespace std;
const int MAXN = 1000000;
int ch[MAXN][2], f[MAXN], size[MAXN], cnt[MAXN], key[MAXN];
int sz, root;


inline void clear(int x) {
    ch[x][0] = ch[x][1] = f[x] = size[x] = cnt[x] = key[x] = 0;
}
int new_node(int x, int fa = 0) {
    sz += 1;
    ch[sz][0] = ch[sz][1] = 0;
    f[sz] = fa;
    size[sz] = cnt[sz] = 1;
    key[sz] = x;
    return sz;
}

inline bool get(int x) {
    return ch[f[x]][1] == x;
}

inline void update(int x) {
    if (x) {
        size[x] = cnt[x];
        if (ch[x][0]) size[x] += size[ch[x][0]];
        if (ch[x][1]) size[x] += size[ch[x][1]];
    }
}

inline void rotate(int x) {
    int old = f[x], oldf = f[old], whichx = get(x);
    ch[old][whichx] = ch[x][!whichx];
    f[ch[old][whichx]] = old;
    ch[x][!whichx] = old;
    f[old] = x;
    f[x] = oldf;
    if (oldf)
        ch[oldf][ch[oldf][1] == old] = x;
    update(old);
    update(x);
}

inline void splay(int x) {
    for (int fa; (fa = f[x]); rotate(x))
        if (f[fa])
            rotate((get(x) == get(fa)) ? fa : x);
    root = x;
}


inline void insert(int x) {
    if (root == 0) {
        root = new_node(x);
        return;
    }
    int now = root, fa = 0;
    while (true) {
        if (x == key[now]) {
            cnt[now]++;
            update(now);
            update(fa);
            splay(now);
            break;
        }
        fa = now;
        now = ch[now][key[now] < x];
        if (now == 0) {
            int nd = new_node(x, fa);
            ch[fa][key[fa] < x] = nd;
            update(fa);
            splay(nd);
            break;
        }
    }
}


inline int find(int x) {
    int now = root, ans = 0;
    while (true) {
        if (x < key[now]) {
            now = ch[now][0];
        } else {
            ans += (ch[now][0] ? size[ch[now][0]] : 0);
            if (x == key[now]) {
                splay(now);
                return ans + 1;
            }
            ans += cnt[now];
            now = ch[now][1];
        }
    }
}

inline int findx(int x) {
    int now = root;
    while (true) {
        if (ch[now][0] && x <= size[ch[now][0]])
            now = ch[now][0];
        else {
            int temp = (ch[now][0] ? size[ch[now][0]] : 0) + cnt[now];
            if (x <= temp) return key[now];
            x -= temp;
            now = ch[now][1];
        }
    }
}

inline int pre() {
    int now = ch[root][0];
    while (ch[now][1]) now = ch[now][1];
    return now;
}

inline int next() {
    int now = ch[root][1];
    while (ch[now][0]) now = ch[now][0];
    return now;
}

inline void del(int x) {
    find(x);
    if (cnt[root] > 1) {
        cnt[root] -= 1;
        update(root);
    }
    else if (!ch[root][0] && !ch[root][1]) {
        clear(root);
        root = 0;
    }
    else if (!ch[root][0]) {
        int oldroot = root;
        root = ch[root][1];
        f[root] = 0;
        clear(oldroot);
    } else if (!ch[root][1]) {
        int oldroot = root;
        root = ch[root][0];
        f[root] = 0;
        clear(oldroot);
    } else {
        int leftbig = pre(), oldroot = root;
        splay(leftbig);
        ch[root][1] = ch[oldroot][1];
        f[ch[oldroot][1]] = root;
        clear(oldroot);
        update(root);
    }
}

int main() {
    int n, opt, x;
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d%d", &opt, &x);
        switch (opt) {
            case 1:
                insert(x);
                break;
            case 2:
                del(x);
                break;
            case 3:
                printf("%d\n", find(x));
                break;
            case 4:
                printf("%d\n", findx(x));
                break;
            case 5:
                insert(x);
                printf("%d\n", key[pre()]);
                del(x);
                break;
            case 6:
                insert(x);
                printf("%d\n", key[next()]);
                del(x);
                break;
        }
    }
}

Posted on Edited on

说下大体思路：

  1. 利用VMWare，把U盘模拟成硬盘安装kali，启动模式最好是UEFI，U盘分区必须是是MBR（如果你需要双引导的话）。
  2. 如果需要划分资料分区，正常划分即可。推荐U盘大小在32GB以上，预留至少10G的系统空间。
  3. 把VMWare切换成BIOS引导模式，参考archwiki上grub的界面 给U盘安装第二遍GRUB2，需要手动指定二进制文件的位置为EFI分区，安装GRUB2位置是主引导扇区。
  4. 退出VMWare，在实体机上开机，安装完成。进行后续操作。

如此操作，两种引导方式可以并存，共享同一份配置文件。如果不利用VMWare的修改引导设置的功能，则无法安装另一引导方式的GRUB2。解决方法是利用其他设备，进入另一种引导方式（比如以此法安装好的U盘）

LEGECY BIOS方式启动的GRUB2，可以正常引导GRUB4DOS，经测试，WEIPE可以正常使用，按理说，其他PE也可以正常使用。某些设备上会花屏，可能因为WEIPE系统的兼容性不是非常好。

这个方法目前没有在其他网站上见到过，特此分享出来。

Posted on Edited on

找到html中的</head>标签，删掉/即可 另一种方式： 在css文件中加入#vdbanner{display:none;}