====== 简况 ======
[[https://ac.nowcoder.com/acm/contest/5667|比赛链接]]

AC 6题，Rank 39th 

====== 总结与反思 ======
===== cmx  =====
主要还是思维问题，EG两题一直在xsy卡题的时候思考，还是没有想出来。另外以后看一道题要把内容共享给队友，节省看题时间
===== lpy  =====

题目最好全看完，没有思路可以去看看没看过的题目，不要盲目跟榜

要与队友多分享题目内容，尽量覆盖所有题

E题这种思维+性质题还需要加强
===== xsy  =====

题目一定要及时看，比如B题H题看完没多久就做出来了，但是看得很晚，还好极限写出来了H。

要注意随时关注榜单，卡题的时候视情况去开一下其他的题。

要随时与队友进行沟通。
====== 题解  ======

===== A. All with Pairs =====

这题比赛的时候竟然没想出来，奔着后缀数组一去不回....这种前缀等于后缀的应该自然的往KMP那边联想。

首先前缀总数和后缀总数都是O(n)级别的，可以使用哈希快速统计个数，比如计数后缀然后枚举前缀，但是答案可能会有重复。

比如两个"aba"，前缀"a"和"aba"都会被算到，但是可以发现他们一定满足短的那个是长的那个的一个后缀，很容易想到是KMP中的next数组就是解决的这个问题。

于是最后从前往后使用$cnt[next[i]] = cnt[next[i]] - cnt[i]$去重即可。

by MountVoom

===== B. Boundary =====

所有的圆都会过原点$O$，如果点$A, B, O$三点共圆，那么$OA, OB$的中垂线会相交于圆心。

于是求出所有点与原点连线的中垂线并两两求交点，最后统计交点个数，出现最多的点对应的圆上有最多的点。

需要注意的是，一个圆上如果有$n$个点，那么交点的个数为$\frac{n(n-1)}{2}$

复杂度为$O(n^2\log n)$

by MountVoom

===== D. Duration =====

水题，求出从$00:00:00$到两个时刻的秒数作差即可。

by MountVoom
===== F ======

求出矩阵，然后行列分别一次单调队列
就可以求出以$(i,j)$为左上角,$(i+K,j+K)$为右下角的正方形的最大值
求矩阵时可以利用gcd优化($(a,b)=(a+b,a)=(a,b+a)$)，但我优化了炸内存，没有优化过了

by Hardict

===== H. Happy Triangle =====

题意是维护一个多重集，支持插入，删除和询问是否能在集合中找到两个数$a, b$与给定的$x$够成三角形。

分情况讨论：

$x$是三角形最长边，那么从比它小的数中选出两个最大的进行判断即可。

$x$是三角形第二长的边，那么从比它小的数中选一个最大的，从比它大的数中选一个最小的进行判断即可。

以上两种情况都可以用一个可重集直接维护。

$x$是三角形的最短边，此时从比它大的数中找两个数，且这两个数的差尽可能小，那么我们要找的两个数在多重集中一定互为前驱后继(即相邻)。把数据离线后得到每个数据最终的位置便可以很方便的用线段树来维护两个数之间的差值，查询时也可以很方便的找到线段树中不小于$x$的第一个位置。

by MountVoom
====== 补题 ======

===== E =====

线性基为$logN$个，那么$i>19$时$ans[i]=ans[i-2]$

而$i \leq 19$时利用异或卷积计算答案

by Hardict
===== G. Greater And Greater =====

好题，可惜没想出来。被数据范围迷惑，以为是分块问题，一开始还傻傻写了个超时方法。赛后看题解发现是bitset，才惊觉为什么一直没往这方面思考。

考虑bitset，对每个Ai求一个长度为m的bitset $S_i$，$S_i[j]=1$当且仅当$A_i\ge B_j$，这样我们发现只要通过下面的式子，就可以求出每个$cur_i$，$cur_i[j]$表示，A从i开始的一段和B从j开始到结尾，都是不小于的。

$$cur_i=(cur_{i+1}>>1|I_m)\&S_i$$

其中I_m是一个只有第m位为1的bitset。这样我们对于每个$cur_i$，求出$cur_i[0]$的和即可。

注意，这里有n个bitset，想要求出这些$S_i$效率似乎有问题，实际上，最多只有$m+1$种不同的bitset。我们排好序，可以求出这几种bitset，以及有哪些i是属于这个bitset。

因此效率为$O(nm/64)$

by cmx