小阳的贝壳 这里最难维护的应该是区间了，但是我们有一个结论，所以这一步可以转换为维护整个序列的差分。 对于操作一：我们只要对端点的值增加，对端点的值减小。 对于操作二：我们只要得到差分数组里的绝对值最大值就行了。 对于操作三：我们首先要得到，然后得到这一段差分序列的，然后再于求一个即为答案。 对一整颗线段树我们只要维护三个值：区间、区间绝对值最大、区间和，我们就可以完成上面的三个操作了。 然后对某些线段树上的操作特判防止数组越界即可。 #include <bits/stdc++.h> #define mid (l + r >> 1) #define lson rt &l...

#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 2e6 + 10; ll ans1[N], ans2[N], cnt[N], sum[N]; int n, m; void init() { for (int i = 1; i <= m; i++) { for (int j = i; j <= m; j += i) { int r = min(j + i - 1, m), l = j; ans1[i] += 1...

选出来的个数能凑成或者必然有一个性质，。$$ #include <bits/stdc++.h> using namespace std; typedef unsigned long long ull; typedef long long ll; const int N = 2e7 + 10; int prime[N], cnt; ull mu[N]; bool st[N]; void init() { mu[1] = 1; for (int i = 2; i < N; i++) { if (!st[i]) { prime[++cnt]...

老瞎眼 pk 小鲜肉 利用异或前缀和，离线处理。 我们定义为值为的异或前缀和最后一次出现在上。 我们通过枚举有区间，然后把异或相同的区间长度存在上， 之后我们只要在区间查询区间最小值即为答案了。 #include <bits/stdc++.h> #define mid (l + r >> 1) #define lson rt << 1, l, mid #define rson rt << 1 | 1, mid + 1, r #define ls rt << 1 #define rs rt << 1 | 1 using n...

函数的魔法 裸的直接写就好了。 #include <bits/stdc++.h> using namespace std; const int mod = 233; int vis[mod + 10]; typedef pair<int, int> pii; int f(int x) { return (1ll * x * x % mod * x % mod + 1ll * x * x % mod) % mod; } int g(int x) { return (1ll * x * x % mod * x % mod - 1ll * x * x % ...

[SCOI2015]国旗计划 注意一个关键点，没有一个区间是包含在另一个区间的，这意味着区间之间要么相交要么相离，当有一个区间一定加入时，我们可以二分查找去得到下一个区间的，但是这样速度显然太慢了，所以我们利用倍增来优化。 定义表示号节点为左端点，共有条线段连在一起最有可到达的坐标。然后只需要从小到大初始化数组，从大到小枚举选择就行了。 /* Author : lifehappy */ #include <bits/stdc++.h> using namespace std; const int N = 1e6 + 10; int n, m, tot, cnt, b[N]...

A and B and Lecture Rooms 题意要求我们找有多少个点满足，输出点的数量即可。 首先特判无解的情况就是为奇数时，接下来我们讨论有解的情况，大致分为两类。 首先我们一定可以在的路径上找到一个点满足要求。 这个点不在上：如图我们要找的是(5, 6)的满足要求的点有多少个，显然3是其路径上的一个满足要求的点，因为5号节点是从3号节点的父亲连过来的，所以3号节点的父节点往上的节点均不满足要求。同样的6号节点是在3号节点的某一棵子树上，所以3号节点要舍弃以4号节点为根节点的子树，所以这种情况就变成了，，显然我们可以得到路径上的中点记为，中深度更大的节点一定在的子树上，所以的某个儿...

[AHOI2008]MEET 紧急集合 模板题，容易得到集合点一定在之间。 所以我们只要求出三者的然后求一个总距离最小值去更新答案即可。 树链剖分求也算是倍增吧！ /* Author : lifehappy */ #include <bits/stdc++.h> using namespace std; const int N = 1e6 + 10; int head[N], to[N], nex[N], cnt = 1; int fa[N], top[N], son[N], sz[N], dep[N]; int n, m; void add(int x, int ...

A Simple Math Problem /* Author : lifehappy */ #include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 1e5 + 10; ll prime[N], phi[N], mu[N], f[N], g[N], cnt, n; bool st[N]; void init() { phi[1] = mu[1] = f[1] = 1; for(int i = 2; i <= n; i++) { ...

Bookshelves 按位贪心然后dp去验证，实在是太妙了，，， 从高到底，如果高位能选的话优先选高位(低位所有的都选上还是比它小)，接下来就是dp验证当前解是否可行了，定义dp[i][j]表示用前i本书放在前j个书架上是否可以得到当前答案满足要求。 然后不断更新合法答案即可，整体复杂度 /* Author : lifehappy */ #include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 55; int n, k; ll a[N]; bool f[N][...

解方程 /* Author : lifehappy */ #include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 1e7 + 10, mod = 998244353; ll prime[N], minnp[N], f[N], cnt, p, q, n; bool st[N]; ll quick_pow(ll a, int n) { ll ans = 1; while(n) { if(n & 1) ans = ans ...

解方程 /* Author : lifehappy */ #include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 1e7 + 10, mod = 998244353; ll prime[N], minnp[N], f[N], cnt, p, q, n; bool st[N]; ll quick_pow(ll a, int n) { ll ans = 1; while(n) { if(n & 1) ans = ans * ...

小D的Lemon 这里还是给出的朴素版本地写法... /* Author : lifehappy */ #include <bits/stdc++.h> using namespace std; const int N = 3e5 + 10, mod = 1e9 + 7, Mod = mod - 1; int prime[N], g[N], invg[N], mu[N], cnt; bool st[N]; int quick_pow(int a, int n) { int ans = 1; while(n) { if(n &...

HRY and mobius 对于k = 0 ，显然最后答案为，n。 对于k = 1，答案就是这就是经典的杜教筛问题了。 对于k = 2 /* Author : lifehappy */ #include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 1e7 + 10; int prime[N], mu[N], sum[N], cnt; bool st[N]; void init() { mu[1] = 1; for(int i = 2; ...