10.12
从今天开始写总结，其实之前就想开始的，但是操作太复杂了，而且我也懒，不想开始。但是时间一长有些写过的题技巧和方法都忘了，还是写写吧。
P7828 [CCO2021] Swap Swap Sort
https://www.luogu.com.cn/problem/P7828
这题根号分治，对出现次数不大于S的数直接双指针暴力，对出现次数大于S的数进行预处理。那么将会有不超过N/S个出现次数大于S的数，预处理复杂度为N*（N/S）。共有Q次询问，每次询问对于出现次数不大于S的数暴力，询问复杂度为Q*S。总复杂度为（N*N/S+Q*S），当S等于N/sqrt(Q)时，复杂度最小，为N*sqrt(Q)。
交完，有re有wa有tle有ac，第一次同时见到这么多颜色，很是激动啊。卡了半天块长，又调了半天数组大小，最后取得了巨大进展，由四种颜色变成了两种颜色，嘿嘿。
最后找高手cy帮忙，又调了半天，发现原来是预处理写假了。。。
P3396 哈希冲突
https://www.luogu.com.cn/problem/P3396
还是根号分治，对模数小于S的数，用sum[p][k%p]表示模数为p时，k%p池内数的总和。修改时，枚举模数p，修改所有x%p下池内数的总和。查询时，对于小于S的数，直接输出处理好的结果，对于不小于S的数，池内有不超过N/S个元素，直接暴力枚举做加法即可。总复杂度为（Q*S+Q*（N/S）），当S等于sqrt（N）时，复杂度最小，为（Q*sqrt（S））。
P4145 上帝造题的七分钟 2 / 花神游历各国
https://www.luogu.com.cn/problem/P4145
这题做法很多，可以线段树，树状数组，分块。
本来是写分块的，结果发现无法对区间开平方，想不出来。看题解，对于小于1e12的数，最多开6次平方，太有道理了！
看到了树状数组的写法，用树状数组进行区间修改，其实就是对区间中的每个点修改，修改复杂度为（nlogn*6），但是这需要保证当前值为1的点不再被修改，用并查集维护，直接跳过值全部为1的段，复杂度为（mlogn），实在是高级。对于询问，直接用树状数组进行查询，复杂度（mlogn）。
继续写分块做法，方法大致同上。如果一个块内的元素个数等于块内元素的和，那么这个块就满足元素的值全部为1，可以跳过。对于不满足的块，直接暴力修改即可。复杂度（m*sqrt（n））。结果写完就挂了，有wa有re，很是奇怪啊，怎么看都很完美。于是找cy帮忙，但是他也觉得我写的可好。就在我感叹真是神奇时，突然发现原来是id数组的下标搞错了，这波大意了，没有闪。
GSS4 - Can you answer these queries IV
https://www.luogu.com.cn/problem/SP2713
很上题一样，双倍经验，改一下输入就好了。但是不知道为什么树状数组写法tle了，会的优化全部都搞上去了，还是卡不过去，找cy帮忙还是卡不过。换成分块的写法，跑过了。
P2607 [ZJOI2008] 骑士
https://www.luogu.com.cn/problem/P2607
基环树。什么时基环树呢？我的理解就是一棵树上加了一条边，使它有且仅有一个环。
做法就是先找到环，将环的任意一条边断开，分别以断开的边的两个端点为根做树形dp（没有上司的舞会）。注意两个端点不能同时选。
怎么找换呢？记录每个点的父亲，设当前点为u，如果u的父亲没有访问过，那么令u=fa[u]，重复。直到u的父亲被访问过，那么u与fa[u]之间的边就是环上的一条边。
发现这题之前做过，但竟然一点印象都没有。翻看之前的写法，竟然时用并查集来找环的，对于当前的点，将他放入并查集中，如果已经在其中了，那么说明之前已经有一条边是他很树连接，如果此时又来一条边，那不就构成一个环了吗。这个做法真是太聪明了，也不知道之前是怎么想出来的，可能大概似乎好像应该不是抄的题解吧。?
P1453 城市环路
https://www.luogu.com.cn/problem/P1453
还是基环树。和上题做法相似。
自信打完直接交，tle了一个点，怎么回事呢。改不出来，再次找cy，话说最近找cy调代码的次数好像越来越多了。
cy一眼就发现并查集没有路径压缩，真是太强了。
话说今天代码里的低级错误好像还挺多的，下次注意。
近几天早读天天睡觉，就站起来才能读10分钟，有点颓废了，不能这样下去了，明天早读不睡了。
挑战早读不睡觉day1。
10.13
今天模拟赛考的有点炸裂，主要是第二题它勾引我。
今天比赛第一题看完题就想到了n3的做法，但在继续优化时，思路仿佛被什么堵塞了一般，毫无进展，然后放弃。但是考后看题解才发现，我的思路离正解已经很接近了，我是枚举每个当前点可以到达的地方，但是这个完全是没有必要的，直接到当前点可以到达的最右端一定是最优的。再说第二题，因为昨天晚上刚复习完骑士这道题，对基环树印象格外深刻。一看T2，什么，基环树，哈哈哈，好哇，昨天刚好复习过，T1虽然少点分，但T2补上不就好了。于是就被它深深的吸引，越陷越深，最后发现这题比我想象的要复杂许多，但是已经打了一百多行代码了，也不愿放弃，就接着搞。最后搞了一坨屎山，两百多行，调也调不出来，样例都没过，没时间了，直接交。好家伙，竟然还有10分，嘿嘿，果然爱笑的男孩运气都不会差。T3T4没时间写zhe了，寄。
没这回主要是没有规划好时间。
今天早读又睡着了，可恶。每天再挑战早读不睡觉吧。但好像明天早上运动会，不用早读，这么早到机房也没事干，还是睡吧，这样模拟赛才有精神，不会沉迷于“思考”。