震惊！这道题居然不卡分块

嘉年华 · 2019-11-16 16:01:22 · 题解

分块之后直接可以过掉这道题（因为数据水）。看到没有人写分块的题解我就来写一个。因为这里的a序列是升序的，所以众数一定是在一段连续的区间中，我们可以先把每一个连续的数列合并了，代码如下

class line
{
    public:
        int start,end;
}l[maxn];

inline void first(void)
{
    int la=a[1];
    int cnt=1;//个数
    l[cnt].start=1;
    l[cnt].end=0;
    for(int i=1;i<=n;i++)
   {
     if(a[i]==la) l[cnt].end++;
     else l[++cnt].start=i,l[cnt].end=i,la=a[i];
   }
}

每个line就表示了某个值在a中占的为止，这样会比直接暴力搜边界要快一些。 然后，我们按line分块就可以了，查询的时候因为是升序的所以可以二分。相信大家都会分块（蒟蒻必备骗分神器），我就不放代码了。 复杂度O（q×n×sqrt(n)）,但常数比一般的分块小一点点。