博客

算法一（针对








n


≤


300










$n\leq 300$
的测试点）

考虑枚举所有区间，然后求其众数及出现次数，并判断是否超过区间总长的一半，统计答案即可。时间复杂度








O




(






n






3








)












$O\left( n^3\right)$

算法二（针对








n


≤


2


,


000










$n\leq 2,000$
的测试点）

考虑先枚举区间的左端点








l










$l$
，再从左到右枚举右端点









r











$r$
并用数组维护每个数的出现次数，同时使用变量维护当前众数、众数的出现次数。不难发现，当右端点向右移动时，这些信息都是非常方便维护的。于是我们便可以在








O




(






n






2








)












$O\left( n^2\right)$
的时间复杂度内统计所有答案。

算法三（针对








t


y




p


e


=


1










$type=1$
的测试点）

对于








01










$01$
序列，我们不难发现，众数出现次数严格大于子区间长度当且仅当子区间内








0


,


1










$0,1$
出现次数不同（那么那个出现次数较多的就是众数）。于是我们将原序列中的








0










$0$
视作









−


1











$-1$
，并对该序列求前缀和








S












$S$
，则子区间









[


l


,


r


]











$[l,r]$

不

为“新生舞会的”，当且仅当











S










l


−


1









=





S








r















$S_{l-1}=S_r$
，因此对








S












$S$
进行排序并从小到大枚举便可求出答案。

算法四（针对









t


y




p


e


=


2











$type=2$
的测试点）

对于所有数的出现次数都较小（不超过








15










$15$
）的情况，不难发现所有“新生舞会的区间”的长度也会较小（不超过








2


×


15


−


1


=


29










$2\times 15-1=29$
）。于是使用算法二，枚举所有长度少于








30










$30$
的区间并统计答案即可。

算法五（针对








t


y




p


e


=


3










$type=3$
的测试点）

对于











A






i







≤


7










$A_i\leq 7$
的测试点，我们不妨枚举所有值作为众数的情况。考虑统计所有众数为








k










$k$
的“新生舞会的”区间，将所有等于









k











$k$
的位置取为








1










$1$
，不等于









k











$k$
的位置取为








−


1










$-1$
，得到新序列








B










$B$
并求前缀和得到序列









S













$S$
，则区间








[


l


,


r


]










$[l,r]$
需要被统计，当且仅当











S








r







−





S










l


−


1









≥


1










$S_r-S_{l-1}\geq 1$
。从左到右枚举右端点，并用线段树维护当前右端点左边每种前缀和出现的次数即可。时间复杂度








O



(


8


n


l


o


g




n


)











$O\left( 8nlogn\right)$

算法六（针对所有测试点）

考虑改进算法五。我们考虑取出所有








B










$B$
中的极长









−


1











$-1$
子区间，观察这些区间中的所有点作为右端点对答案的贡献。不难发现极长








−


1










$-1$
子区间








[


l


,


r


]










$[l,r]$
中的所有点作为右端点对答案的贡献为











∑








r


−


l


+


1










i


=


1












∑











S










l


−


1









−


i


−


1










j


=


−


∞









c


n


t


[


j


]










$\sum_{i=1}^{r-l+1}\sum_{j=-\infty}^{S_{l-1}-i-1}cnt[j]$
，其中








c


n


t


[


j


]










$cnt[j]$
表示在区间








[


0


,


l


−


1


]










$[0,l-1]$
之间前缀和为








j










$j$
的端点数目；在统计这段区间的答案后，我们还需要对区间









[





S










i


−


1









−


(


r


−


l


+


1


)


,





S










i


−


1









−


1


]











$[S_{i-1}-(r-l+1),S_{i-1}-1]$
中的所有








c


n


t










$cnt$
均进行








+


1










$+1$
操作。显然地，我们使用一个维护











B






i















$B_i$
和











C








i







=


i


×





B






i















$C_i=i\times B_i$
的线段树就可以支持这些查询、修改操作。于是我们使用这棵线段树维护相关信息，并从左到右枚举右端点，统计答案即可。

不难发现，极长








−


1










$-1$
子区间的数目与序列中








k










$k$
的数目同阶，因此，对于统计众数为









k











$k$
的“新生舞会的”区间的时间开销，不难发现我们通过上述优化将时间开销缩短到了








O




(






序








列





A





中





k





的








数








目





l


o


g




n



)












$O\left( 序列A中k的数目logn\right)$

于是，总时间复杂度即为








O




(






∑








k












序








列





A





中





k





的








数








目





l


o


g




n



)












$O\left(\sum_{k} 序列A中k的数目logn\right)$
，即








O



(


n


l


o


g




n


)











$O\left(nlogn\right)$
。

对








n


≤


100


,


000










$n\leq 100,000$
测试点的说明

对于常数较大的与标准算法时间复杂度相同的算法，以及一些时间复杂度略大于标程的算法，可能存在无法通过所有测试点的情况。这类算法可以通过这类测试点。