Luogu P5048 Yuno loves sqrt technology III
题意
给定一个长度为 \(n\) 的序列 \(a\)。
有 \(m\) 次询问：查询区间 \([l,r]\) 中众数的出现次数。
强制在线。
数据范围与约定
\(1 \le n,m,a_i \le 5*10^5\)。
题解
十年前《蒲公英》的做法，这道题只能拿 \(80\) 分，因为这道题卡了空间。下面来讲一个现代的在线区间众数做法。
看到区间查询，首先还是想到线段树。我们发现这题线段树没办法 pushup。但是与《由乃打扑克》这题不同的是，这题不能 pushup 的原因是我们不会 merge 两个区间的信息，而不是因为层数。所以乍一看分块也无能为力，想要莫队却被强制在线 ban 了。
如果可以像区间数颜色一样，通过某种方式转化成二维数点，或者类似于区间 mex 进行一些转化，也许能做。但遗憾的是区间众数起码我所知道的，并不能进行转化。
还是考虑分块，不考虑区间信息合并的情况下，看看该怎么办。分类讨论一下：
-
查询区间在一个块内：开个桶计数，暴力扫一遍每个元素即可。特别强调不要用 memset 清空桶，复杂度不对。
-
查询区间在多个块内：这里也分两种情况，整块和角块：
-
整块：既然不会信息的 merge，那我们就不 merge 了。直接预处理出任意两个块之间的众数。因为块只有 \(O(\sqrt{n})\) 个，所以只会有 \(O(n)\) 个区间，如同《蒲公英》的预处理一样。假设整块合并后，众数为 \(mode\)，出现次数为 \(cnt\)。
-
角块：如果我们已经有了中间整块的众数信息了，那么考虑到角块最多有 \(2*\sqrt{n}\) 的数，考虑角块上的数的影响。如果我们能获取一个数在区间中出现的次数，就能更新 \(mode,cnt\) 了。但遗憾的是，这个做法就是已经过时的《蒲公英》的做法，需要开一个 \(n*\sqrt{n}\) 大小的前缀和数组，被卡空间了。
如果我们转成判定问题呢？考虑到，\(cnt\) 最多加上 \(O(\sqrt{n})\) 次，总势能是固定的。可以进行判定，一个数如果在区间 \([l,r]\) 中出现次数大于 \(cnt\)，就可以给 \(cnt+1\)，然后进行 while 循环。剩下的问题就是如何判定了。
我们可以开一个 vector 数组，记录每种数字出现的下标。然后我们再记录一下每个数在对应的 vector 中的下标。对于左角块的每个数，如果在 vector 中的下标，向右偏移 \(cnt\) 次后，下标小于等于 \(r\)。则说明在区间 \([l,r]\) 中至少出现了 \(cnt+1\) 次。右角块的数同理。
-
最后我们就得到了时间复杂度 \(O(n\sqrt{n})\)，空间复杂度 \(O(n)\) 的做法了。最后根据实测，块长取 \(400\) 时跑得最快。
代码
#include<bits/stdc++.h>
using namespace std;
/*====================*/
#define endl "\n"
/*====================*/
typedef long long lnt;
/*====================*/
const int N = 5e5 + 10;
const int C = 5e5 + 10;
/*====================*/
const int S = 400;
const int B = N / S + 10;
/*====================*/
int n, m;
int col[N];
/*====================*/
int belong[N];
struct Block
{
int l, r;
Block(void)
{
l = r = 0;
}
}block[B];
int mode[B][B];
/*====================*/
int idxincolidx[N];
vector<int>colidx[C];
/*====================*/
int cnt[C];
/*====================*/
int Ask(int l, int r)
{
int res = 0;
if (belong[l] == belong[r])
{
for (int i = l; i <= r; ++i)
{
res = max(res, ++cnt[col[i]]);
}
for (int i = l; i <= r; ++i)
{
cnt[col[i]]--;
}
}
else
{
res = mode[belong[l] + 1][belong[r] - 1];
for (int i = l; i <= block[belong[l]].r; ++i)
{
while ((idxincolidx[i] + res < colidx[col[i]].size()) && (colidx[col[i]][idxincolidx[i] + res] <= r))
{
res++;
}
}
for (int i = block[belong[r]].l; i <= r; ++i)
{
while ((idxincolidx[i] - res >= 0) && (colidx[col[i]][idxincolidx[i] - res] >= l))
{
res++;
}
}
}
return res;
}
/*====================*/
void Solve(void)
{
do
{
cin >> n >> m;
for (int i = 1; i <= n; ++i)
{
cin >> col[i];
}
} while (false);//读入
do
{
for (int i = 1; i <= n; ++i)
{
colidx[col[i]].push_back(i);
idxincolidx[i] = colidx[col[i]].size() - 1;
}
} while (false);//预处理各颜色下标
do
{
for (int i = 1; i <= n; ++i)
{
belong[i] = i / S + 1;
if (block[belong[i]].l == 0)
{
block[belong[i]].l = i;
}
block[belong[i]].r = i;
}
} while (false);//分块预处理
do
{
for (int i = 1; i <= belong[n]; ++i)
{
for (int j = i; j <= belong[n]; ++j)
{
mode[i][j] = mode[i][j - 1];
for (int k = block[j].l; k <= block[j].r; ++k)
{
mode[i][j] = max(mode[i][j], ++cnt[col[k]]);
}
}
memset(cnt, 0, sizeof(cnt));
}
} while (false);//处理块间众数
do
{
int lastans = 0;
for (int i = 1; i <= m; ++i)
{
int l, r; cin >> l >> r;
l ^= lastans; r ^= lastans;
cout << (lastans = Ask(l, r)) << endl;
}
} while (false);//回答询问
}
/*====================*/
int main()
{
#ifndef ONLINE_JUDGE
freopen("IN.txt", "r+", stdin);
#endif
ios::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int T = 1; //cin >> T;
while (T--)Solve();
return 0;
}