2022.9.24
CF1479D Odd Mineral Resource
假如不需要知道路径上哪些数只出现奇数次，那么这道题及类似于共价大爷游长沙。
现在考虑如何找出路径上出现奇数次，范围在 $ [l, r] $ 之间的任意数。考虑用欧拉序的方式来维护路径，具体用主席树维护某一个值的出现次数。
My Submission
CF1515I Phoenix and Diamonds
读错题意若干次QAQ
如果用线段树暴力维护，每次选择连续一段尽可能取走，很容易被卡复杂度，实测Time Limit Exceeded on Test 71。
由于 $ c $ 一开始非常大，$ w_i $ 则较小，前面可以尽可能取，直到剩下的 $ c $ 小于 $ 10^5 $ 。
考虑对于每个 $ c $ ，大于 $ \lfloor c \rfloor $ 最多取一次，剩下的要在小于 $ \lfloor c \rfloor $ 中取。由于取的顺序是一定的，所以可以通过线段树维护能取到 $ \lfloor c \rfloor $ 的哪一个钻石，对于小于 $ \lfloor c \rfloor $ 的可以用另一个线段树维护。
考虑对于不同的 $ c $，$ \lfloor c \rfloor $ 会不同，难以预处理。直接按二进制按位预处理即可。
My Submission
昨天CF有点摆。。。周末还有icpc网络赛。。。
晚上打了把ABC，状态极度不佳，明天靠队友。。。
2022.9.25
dbq QAQ，我是罚时机器。。。
今天状态很不对，很多莫名其妙的错误同一天犯（数组开小、忘记取min，题意看错），好在队友发挥了作用，最后八题垫底（我的锅）（但我还是写了七道）
2022.9.28
技能CD了一下，稍微暖一下手感~
Check,Check,Check one two!
用后缀自动机维护parent树，任意两个endpos的lca的len是它们的最长公共前缀。
对于点对 $ (i, j) $ ， $ s[i - a + 1, i + b - 1] = s[j - a + 1, j + b - 1] $ ，则贡献为 $ a \times b $ 。我们现在很容易地维护了前缀，考虑后缀如何处理。由于每个点对 $ (i, j) $ ，它们会在 $ (i + 1, j + 1) $ 至 $ (i + b - 1, j + b - 1) $ 都计算一边，故每次加上贡献 $ a $ 即可。
考虑 $ k1, k2 $ 的限制。对 $ (i, j) $ 已知的前缀进行约束，即直接统计点对在该前缀子串上都合法的情况。此外，对于 $ s[m, m + k1] $ （举个栗子），之前在 $ m $ 处的贡献应减去，且减去后不会对此再有影响。
My Submission
PS: LJ不在QQ群里供题了啊QAQ，日常口胡断粮了
最近要期中考，考虑先放一放ACM，先苟住学分绩。。。
2022.10.3
2022.10.4
CF1734F Zeros and Ones
为什么我想不到QAQ
Solution from Zhihu
2022.10.5
CF1712F Triameter
My Submission
2022.10.8
AGC009D Uninity
题意实际上是求最大深度最小的点分树的深度。
考虑正常点分治下层数已经是 $ \mathcal{O}(\log n) $ 的，那么最优状态下一定小于正常点分治的深度，即深度状态可以状态压缩。
将节点按 $ 0, 1, 2, \dots, k $ 编号表示节点的Uninity值，其中叶子节点编号为 $ 0 $ 。
根据点分树的性质，任意两个编号相同的节点路径上一定存在编号比它们大的节点。
每个节点存状态数组 $ ned[u] $ ，表示 $ u $ 节点的子树内未完成成对匹配的编号，按位存储。对于 $ u $ ，假设有两个不同的子节点 $ v, w $ ，若 $ \exist x, 2^{x} \in ned[v] \and ned[w] $ ，则 $ u $ 节点编号要大于 $ x $ ，否则 $ u $ 子树下编号为 $ x $ 将无法完成匹配。同时，若 $ \exist x, 2^{x} \in ned[v] $ ，则 $ u $ 也不能选 $ x $ ，否则 $ u $ 会与 $ v $ 子树内的同编号点无法匹配。
$ u $ 的编号从小到大贪心取即可。通过位运算骚操作可以让复杂度变为 $ \mathcal{O}(n) $ 。
[My Submission])(https://atcoder.jp/contests/agc009/submissions/35453858)
2022.10.9
突然发现自己构造能力很差，再不补就是弱鸡水平了。
今天看到一个构造，要求构造一个 不存在长度大于等于3的等差子序列 的排列。方法大概是先将奇偶分开，奇数在前，偶数在后，这样不存在既有奇数又有偶数的等差子序列。再将奇数列和偶数列递归构造。这种方法同样适用于构造已知元素的数列，使它等差子序列个数尽可能少。
补了一下ICPC2022网络赛第一场的K题（可以在pintia上看）。可以发现最多不能击败 $ 2 \sqrt{\max{x_i}} $ ，因为可以先花 $ \sqrt{max{x_i}} $ 的时间叠buff，再花同样的时间将buff叠战力，然后无敌。同样，buff最多叠 $ \sqrt{max{x_i}} $ 层，因为多叠的一层的时间将它用来叠战力，到无敌时始终更优。然后dp，$ f[i][j][k] $ 表示干了第i个，没干掉j个，buff层数为k的最大战力。
这周戒题，准备期中考。
2022.10.18
AGC023F 01 on Tree
观察不难发现，父亲节点一定先于儿子节点取，对于每个儿子向父亲合并时，最优策略一定是儿子的序列进行归并（每个儿子的子序列保持不变）。这有了递归的基础。
此外，我们还可以发现，假如当前有0，则能取尽取；如果有1，则取尽可能少的1去获得足量的0。考虑对于一个01序列，假如取了前面的一串1，则后面紧跟着的一串0都要跟着取，也就是类似11…100…0这样的取法是绑定的，不会在归并时改变。考虑取法的优先级。设这样的序列$a, b$ ，其中 $a_0, a_1, b_0, b_1$ 分别表示各自0、1的个数，比较相对位置，若$ a_1 \times b_0 < b_1 \times a_0 $ ，则 $ a $ 在前更优。
此时已经可以直接dfs并用set维护11…100…0序列并暴力启发式合并了，不过这代码难度。。。
与其直接dfs，不如考虑一个序列如何直接接上父亲。如果这个序列是整棵树上最优的，那他可以直接接在父亲所在的序列后，然后合并成新的序列，虽然不满足11…100…0的形式，但是合并的贡献计算方式一致。用并查集和优先队列维护即可。
My Submission
（啊，这是凌晨写的）
PAM（回文自动机）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
using namespace std;
typedef long long ll;
const int N = 2100010;
int n, id[N];
char s[N]; int len[N], fail[N], tot, sz[N], ch[N][26], cur;
void init() {
len[0] = 0, len[1] = -1, fail[0] = 1, fail[1] = 0, tot = 1, cur = 0;
}
int gfail(int x, int now) {
for(; now - len[x] - 1 < 1 || s[now - len[x] - 1] != s[now]; x = fail[x]);
return x;
}
void insert(int now, int c) {
int pos = gfail(cur, now);
if(!ch[pos][c]) {
++tot;
fail[tot] = ch[gfail(fail[pos], now)][c];
ch[pos][c] = tot, len[tot] = len[pos] + 2, sz[tot] = sz[fail[tot]] + 1;
}
cur = ch[pos][c];
}
int main() {
scanf("%s", s + 1), n = strlen(s + 1);
init();
int ans = 0;
rep(i, 1, n) {
s[i] = (s[i] - 97 + ans) % 26 + 97;
insert(i, s[i] - 97), ans = sz[cur];
printf("%d ", ans);
}
return 0;
}
2022.10.26
少年不知mt19937 rnd(time(0))贵，错把srand(time(0)) 当宝贝。
2022.11.6
被各种事情搞得焦头烂额，又要大一年度项目又要思政实践项目又要考试又要竞赛，感觉再搞下去离大学ICPC/CCPC退役都不远了。
今天下午是我的第一场ICPC，不奢求有多好的成绩吧，只希望能够尽可能好地发挥吧，最近状态极度不稳，水平在幼儿园和红名之间剧烈波动，构造题、思维题依旧是我的弱项。
铁了
2022.11.9
G. Shinyruo and KFC 值域根号分治
M. 810975 隔板法
2022.11.12
关于某个质数的剩余系的题原根是真的好用。原根可以把数的乘法变成原根上指数的加法，这样也可以快速计算二次剩余。对于每个质数都有原根。
C. Assign or Multiply利用原根把乘法变加法，用数组标记某个数是否出现过，每加入一个数，进行循环移位，找到循环移位后值不同的位置并修改，这个操作总共是不超过n次的，利用二分和树状数组维护的哈希来找到这些位置并修改。
2022.11.13
假如不能比较两个数的两两关系（拓扑图而非竞赛图）的话还是不要用sort了吧。。。
Ex - Constrained Sums
约束 $ L \leq a + b, a \in [0, M], b \in [0, M] $ 等价于 $ \forall x \in [0, M], x \leq a \or L - x + 1 \leq b $ 成立，证明显然。如果是 $ a + b \leq R $ 的用互补律即可 $ (a \or b = \overline{\overline{a} \and \overline{b}}) $ 。
然后2-sat，按照关系连边，详见代码My Submission