选点 如果选了根节点的话，在这棵子树内选的其他的点都要比根节点的值大，如果在左子树选了一个点，在右子树中选的其他点要比它小，根节点比子节点都要小，右子树比左子树都要大所以可以先遍历右儿子，然后用先序遍历dfs序维护最长上升子序列来写。 /* Author : lifehappy */ #include <bits/stdc++.h> using namespace std; const int N = 1e5 + 10; int value[N], son[N][2], a[N], b[N], tot, n; void dfs(int rt) { a[++tot...

[CQOI2015]选数 /* Author : lifehappy */ #include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 2e6 + 10, mod = 1e9 + 7; int prime[N], mu[N], cnt; bool st[N]; ll quick_pow(ll a, int n) { ll ans = 1; while(n) { if(n & 1) ans = ans * a % mod;...

brz的函数 /* Author : lifehappy */ #include <bits/stdc++.h> using namespace std; const int N = 5e4 + 10; int prime[N], mu[N], ans[N], cnt, n; bool st[N]; void init() { mu[1] = 1; for(int i = 2; i < N; i++) { if(!st[i]) { prime[++cnt] = i; mu[i] ...

[SDOI2014]数表 /* Author : lifehappy */ #include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 1e5 + 10; int prime[N], mu[N], ans[N], tree[N], cnt; bool st[N]; struct Node { int id, sigma; bool operator < (const Node &T) const { return...

[SDOI2015]约数个数和 /* Author : lifehappy */ #include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 5e4 + 10; int prime[N], mu[N], cnt; bool st[N]; ll f[N]; void init() { mu[1] = 1; for(int i = 2; i < N; i++) { if(!st[i]) { prime...

[SDOI2017]数字表格 /* Author : lifehappy */ #include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 1e6 + 10, mod = 1e9 + 7, Mod = mod - 1; ll prime[N], mu[N], fib[N], phi[N], inv_fib[N], f[N], cnt; bool st[N]; ll quick_pow(ll a, int n) { ll ans = 1; whi...

Rinne Loves Sequence 思路 写完后看了一下ac代码，果然就我的最暴力了。 代码 /* Author : lifehappy */ #include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 5e5 + 10; int prime[N], mu[N], num[N], n, cnt; bool st[N], vis[N]; vector<int> fac[N]; void init() { mu[1] = 1; ...

Rinne Loves Sequence 题解 HRY and mobius 题解 小V的和式(这道题目好难啊) 有用的 LCM 小D的Lemon 题解 解方程 题解

Lady Layton with Math /* Author : lifehappy */ #include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 2e6 + 10, mod = 1e9 + 7; int prime[N], cnt, n; ll phi[N]; bool st[N]; void init() { phi[1] = 1; for(int i = 2; i < N; i++) { if(!st[i])...

求和 利用dfs序在子树上的连续性，然后通过单点修改，区间查询即可，这点只要用一颗树状数组即可完成。 /* Author : lifehappy */ #include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 1e6 + 10; ll tree[N]; int head[N], to[N << 1], nex[N << 1], cnt = 1; int l[N], r[N], rk[N], value[N], n, m, k, tot; ...

Tree Requests 经典的树上启发式合并题目了（其实就是瞎暴力）。 对于一颗有根树，我们先做一次dfs找到每个节点的重儿子，然后在答案统计的时候优先遍历轻儿子，不保留答案，最后遍历重儿子保留答案。 这颗树显然我们要维护的信息就是每一层字母的奇偶性，所以我们直接在每一层开一个30大小的bitset。 然后暴力遍历，暴力合并即可。 /* Author : lifehappy */ #include <bits/stdc++.h> using namespace std; const int N = 5e5 + 10; int head[N], to[N], nex[N...

Military Problem DFS序模板题了，l[rt]标记rt节点第一次进入，r[rt]表示rt节点退出，然后只要判断l[rt] + k - 1 是否小于等于r[rt]即可。 /* Author : lifehappy */ #include <bits/stdc++.h> using namespace std; const int N = 2e5 + 10; vector<int> G[N]; int id[N], l[N], r[N], rk[N], tot, n, m; void dfs(int rt, int fa) { id[r...

金字塔 利用dfs序的通性，如果[l, r]是一颗完整的子树，一定有str[l] = str[r]，接下来就是考虑如何划分子树了。 考虑对[l, r]的子树进行划分，枚举中间划分值mid，那么因为dfs序一定有str[l] = str[mid] = str[r]。我们定义dp[l][r]，为区间[l][r]，也就是以l,为根节点的划分方案数，当有mid满足条件时，一定有dp[l][r] = dp[l][r] + dp[l + 1][mid - 1] * dp[mid][r]dp[l + 1][mid - 1]为单独作为子树的方案，dp[mid][r]这棵树没有加上[l + 1][r - 1]区...

Legacy 线段树优化建边，开两颗线段树：对于线段树1，自顶向下连边。对于线段树2，自底向上连边。然后对于op1我们直接连边即可。对于op2（u -> [l, r] cost = w），这个操作在线段树1上完成即可。对于op3（[l, r] -> v cost = w），这个操作在线段树2上完成即可。最后跑一遍Dijkstra最短路即可。 /* Author : lifehappy */ #include <bits/stdc++.h> #define mid (l + r >> 1) #define lson rt << 1, l, mi...