洛谷 5048 Yuno loves sqrt technology III

发表于 | 分类于 |

众所周知对于区间静态众数我们有经典曾经的洛谷水黑题「蒲公英」。
众所周知那一题的做法是分块，预处理块到块的众数，预处理块内某个值出现次数的前缀和，用散块的值尝试更新众数。

但是注意到一点：设整块到整块内的众数出现次数为 \(\newcommand\ans{ {\rm ans} }\ans\)，当尝试用散块更新的时候，我们真的需要知道其出现次数吗？
容易发现经过散块，\(\ans\) 的增量是 \(O(\sqrt n)\) 级别的，也就是说可以想个办法直接检查这个值能否使答案增加 \(1\)。
那么，若把每个值的出现位置存入 vector，则直接在 vector 里访问当前位置的后 \(\ans\) 个出现位置是否在 \([l,r]\) 内即可。
如此便得到了一个常数极小的 \(O(n \sqrt n)\) 解法（视 \(n,m\) 同阶）。

以及，用这个做法拿到了蒲公英的 Rank2（

代码： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;

const int BUFF_SIZE = 1 << 20;
char BUFF[BUFF_SIZE],*BB,*BE;
#define gc() (BB == BE ? (BE = (BB = BUFF) + fread(BUFF,1,BUFF_SIZE,stdin),BB == BE ? EOF : *BB++) : *BB++)
template<class T>
inline void read(T &x)
{
    x = 0;
    char ch = 0,w = 0;
    for(;ch < '0' || ch > '9';w |= ch == '-',ch = gc());
    for(;ch >= '0' && ch <= '9';x = (x << 3) + (x << 1) + (ch ^ '0'),ch = gc());
    w && (x = -x);
}

const int N = 5e5;
const int BLK = 799;
const int CNT = N / BLK + 1;
int n,m,a[N + 5],num[N + 5];
int block,pos[N + 5];
int ind[N + 5],len;
int cnt[N + 5],f[CNT + 5][CNT + 5];
vector<int> vec[N + 5];
int lastans;
inline int query(int l,int r)
{
    int ret = f[pos[l] + 1][pos[r] - 1];
    for(register int i = l;i <= min(pos[l] * block,r);++i)
        for(;num[i] + ret < vec[a[i]].size() && vec[a[i]][num[i] + ret] <= r;++ret);
    if(pos[l] ^ pos[r])
        for(register int i = (pos[r] - 1) * block + 1;i <= r;++i)
            for(;num[i] - ret >= 0 && vec[a[i]][num[i] - ret] >= l;++ret);
    return ret;
}
int main()
{
    read(n),read(m),block = BLK;
    for(register int i = 1;i <= n;++i)
        read(a[i]),ind[i] = a[i],pos[i] = (i - 1) / block + 1;
    sort(ind + 1,ind + n + 1),len = unique(ind + 1,ind + n + 1) - ind - 1;
    for(register int i = 1;i <= n;++i)
        a[i] = lower_bound(ind + 1,ind + len + 1,a[i]) - ind,
        num[i] = vec[a[i]].size(),vec[a[i]].push_back(i);
    for(register int i = 1,l,cur;i <= pos[n];++i)
    {
        memset(cnt,0,sizeof cnt),l = (i - 1) * block + 1,cur = 0;
        for(register int r = l;r <= n;++r)
            cur = max(cur,++cnt[a[r]]),
            (pos[r] ^ pos[r + 1]) && (f[i][pos[r]] = cur);
    }
    for(int l,r;m;--m)
        read(l),read(r),l ^= lastans,r ^= lastans,printf("%d\n",lastans = query(l,r));
}