标签：总结 早读 cn luogu 每日 https com 复杂度

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]之间的边就是环上的一条边。 发现这题之前做过，但竟然一点印象都没有。翻看之前的写法，竟然时用并查集来找环的，对于当前的点，将他放入并查集中，如果已经在其中了，那么说明之前已经有一条边是他很树连接，如果此时又来一条边，那不就构成一个环了吗。这个做法真是太聪明了，也不知道之前是怎么想出来的，可能大概似乎好像应该不是抄的题解吧。

标签：总结,早读,cn,luogu,每日,https,com,复杂度
From： https://www.cnblogs.com/strokefish/p/17760709.html