考虑g1=gcd(al,al+1,...,ar),g2=gcd(al,al+1,...,ar,ar+1)g_1=gcd(a_l,a_{l+1},...,a_{r}),g_2=gcd(a_l,a_{l+1},...,a_r,a_{r+1})g1​=gcd(al​,al+1​,...,ar​),g2​=gcd(al​,al+1​,...,ar​,ar+1​) 显然有g1g_1g1​为g2g_2g...

传送门 这道题思路还是比较巧妙的，考虑如何判断矛盾。 首先，发现题目中说 每个位置上的数都不同的序列a[1…n] 所以任意两个不相交的区间中，最小值一定是不同的（性质111），因为如果最小值相同，那么最小值对应到的那个数是相同的，说明两段区间都包含那个数，即两段区间相交。 再继续考虑，我们考虑二分答案，现在二分到一个位置pospospos，我们首先把位置≤pos\le pos≤pos的操...

传送门 考虑把A+B+C+D=0A+B+C+D=0A+B+C+D=0转换成−A−B=C+D-A-B=C+D−A−B=C+D，于是预处理出C+DC+DC+D的数组，sort一遍以后二分查找即可。 时间复杂度O(n2log⁡(n2))O(n^2\log (n^2))O(n2log(n2))（反正不会爆就是了） 我以前写的代码，码风可能有点清奇。 1234567891011121314151617...

传送门 这题其实有两种做法： 1.1.1. 我一开始想到的是二分加并查集，考虑二分最近部落的距离，如果两点iii，jjj距离小于等于midmidmid那么连边，并查集维护，最后统计有多少集合。 考虑如何证明单调性：如果两点iii，jjj在mid1mid1mid1情况下能连边，那么在mid2mid2mid2情况下也能连边（mid2>mid1mid2>mid1mid2>mid1...