勤劳努力的小蜜蜂

可持久化线段树是支持访问历史版本的线段树 内存空间 初始建树需开 \(2n-1\) 个节点，\(n\)次修改，每次修改最多开 \(logn+1\) 个节点，所以节点总数为 \(2n-1+n(logn+1)\) 动态开点 不再用 \(u<<1\)和\(u<<1|1\) 记录左儿子和右儿子，而是使用 \(ls[u]\) 和 \(rs[u]\) 来表示，每个版本的根节点用 \(root\) 数组来维护 例题 Luogu P3919 【模板】可持久化线段树 1（可持久化数组） 有了可持久化数组，便可以实现很多衍生的可持久化功能 题目描述 如题，你需要维护这样的一个长度为 \(N\) 的数组，支持如下几种操作 在某个历史版本上修改某一个位置上的值 访问某个历史版本上的某一位置的值 此外，每进行一次操作(对于操作2，即为生成一个完全一样的版本，不作任何改动)，就会生成一个新的版本。版本编号即为当前操作的编号(从1开始编号，版本0表示初始状态数组) 输入格式 输入的第一行包含两个正整数 \(N,M\)，分别表示数组的长度和操作的个数。 第二行包含 \(N\) 个整数，依次 ...

A. Only Pluses 每次操作选择一个数 \(+1\)，执行五次，使得 \(a*b*c\) 最大，只需要在每次操作对 \(a,b,c\) 中最小的一个 \(+1\) 即可 code: 1234567891011121314151617181920212223242526272829303132#include <bits/stdc++.h>#define x first#define y second#define int long longusing namespace std;typedef pair<int, int> PII;const int N = 200010;int T;int a[3];signed main(){ cin >> T; while (T--) { for (int i = 0; i < 3; i++) cin >> a[i]; for (int i = 0; i < 5; i++) { ...

A. Submission Bait 博弈 当最大数的数量是奇数时，第一个选择最大数是必胜的，因此 \(Alice\) 先手选择最大数即为必胜策略 当最大数的数量是偶数时，第一个选择最大数是必败的，因此两人都要避免第一个选择最大数，这时可以考虑选择次大数，可以发现，当次大数的数量为奇数时，先手拿次大数的人会后手拿最大数，反之会先手拿最大数 从后往前递推，可以发现，当存在一个数的数量是奇数时，先手必胜，否则先手必败 code: 123456789101112131415161718192021222324252627282930313233343536#include <bits/stdc++.h>#define x first#define y second#define int long longusing namespace std;const int N = 200010;int T;int n;int a[N];signed main(){ cin >> T; while (T--) { cin & ...

A. Minimize! 输出\(b-a\)即可 code: 123456789101112131415161718#include <bits/stdc++.h>using namespace std;int T;int a, b;int main(){ cin >> T; while (T--) { cin >> a >> b; cout << b - a << endl; } return 0;} B. osu!mania 从下到上，从左到右遍历字符串，输出每个\(\#\)在当前行的位置 code: 123456789101112131415161718192021222324252627#include <bits/stdc++.h>using namespace std;const int N = 510;int T;int n;string s[N];int main(){ ci ...

A. 会赢吗？ 签到，比大小 code: 123456789101112131415#include <bits/stdc++.h>using namespace std;double a, b;int main(){ cin >> a >> b; if (a < b) cout << "YES" << endl; else cout << "NO" << endl; return 0;} B. 能做到的吧 判断是否有\(i,j\)满足\(1<=i<j<=n\)，并且\(s[i]<s[j]\)，如果有就输出\(YES\)，否则输出\(NO\) code: 1234567891011121314151617181920212223242526272829303132#include <bits/stdc++.h>using namespace std;int T;s ...

A. Dora's Set 要使三个数互质，那么一定是两个奇数\(+\)一个偶数，因此遍历\(l\)到\(r\)，每次删除相邻的奇偶奇序列即可 code: 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576#include <bits/stdc++.h>#define int long longusing namespace std;int T;int n, m;signed main(){ cin >> T; while (T--) { cin >> n >> m; int res = 0; while (n <= m) { if (n % 2 == 0) n ...

A. Sakurako's Exam 签到，优先考虑\(2\)之间互相加减，所以只会剩下最多一个\(2\)，用\(2\)个\(1\)来消除，最后判断剩下\(1\)的个数即可 code: 1234567891011121314151617181920212223242526272829#include <bits/stdc++.h>#define int long long#define x first#define y secondusing namespace std;typedef pair<int, int> PII;const int N = 200010;int T;int a, b;signed main(){ cin >> T; while (T--) { cin >> a >> b; b %= 2; a -= b * 2; if (a < 0 || a % 2) cout << "NO&qu ...

A. Turtle and Good Strings 根据题意可知，一个好的字符串一定可以拆成两个满足条件的字符串，所以只需要令\(k=2\)进行操作即可 code: 123456789101112131415161718192021222324252627282930313233#include <bits/stdc++.h>#define int long long#define x first#define y second#define endl '\n'using namespace std;typedef pair<int, int> PII;const int N = 200010;int T;int n;string s;signed main(){ ios::sync_with_stdio(false); cin.tie(0), cout.tie(0); cin >> T; while (T--) { cin >> n >> ...

A. Primary Task 暴力判断即可 code: 1234567891011121314151617181920212223242526272829303132333435363738394041#include <bits/stdc++.h>#define x first#define y second#define int long longusing namespace std;typedef pair<int, int> PII;const int N = 200010;int T;int n;int a[N];signed main(){ cin >> T; while (T--) { cin >> n; string s; while (n > 10) { s += n % 10 + '0'; n /= 10;
...

A. Closest Point 观察一下可以发现，只有当集合中的点数等于\(2\),并且这两个点的差值大于\(1\)时，才有满足条件的点可以插入 code: 123456789101112131415161718192021222324252627282930#include <bits/stdc++.h>#define int long long#define x first#define y secondusing namespace std;typedef pair<int, int> PII;const int N = 200010;int T;int n;int a[N];signed main(){ cin >> T; while (T--) { cin >> n; for (int i = 0; i < n; i++) cin >> a[i]; if (n == 2 && abs(a[0] - a[1]) > ...