bzoj2724 蒲公英 区间众数+强制在线

(Updated: )
(6 mins to read)

可以离线的话怎么做？首先想到的肯定是莫队，不过删除操作有点棘手。目前只有两个想法：1.无脑上回滚莫队。2.再加一个分块来维护出现次数，移动O(1)，查询$O(\sqrtn)$。不过感觉都没有在线简单

分块之后，如果维护的信息可以递推，我们可以很方便的维护出任意两个块之间的信息。本题就是任意两个块之间的众数，这是很容易的，而且是$O(\frac{N^2}{B})$的。可以发现答案肯定要么是上面这个，要么是两个边缘块中出现的数字。所以我们只需要枚举边缘块的数字来进行更新即可。一种显然的想法就是对每个数字进行二分来求解出现次数，这样是$O(MB\logN)$的，需要对B进行权衡。另外一种很妙的思路，考虑到两个边缘块对答案的贡献最多是$2B$，那我直接O(1)去check贡献能不能再+1，这样就是$O(MB)$的了(注：M是询问次数，N是数字个数，B是块大小，根据均值不等式使两个复杂度相等，选择最优的B即可，当然具体实现时只要大致估计一个常数即可)

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <bits/stdc++.h>
using namespace std;
const int N = 4e4 + 5, B = 250;
int n, m, a[N], v[N], tot;
int f[B][B], g[B][B], cnt[N];
int blo, num, bl[N], l[B], r[B], pos[N];
vector<int> p[N];
void lsh() {
  static int tmp[N];
  for(int i=1; i<=n; i++) tmp[i] = a[i];
  sort(tmp+1, tmp+n+1);
  tot = unique(tmp+1, tmp+n+1) - tmp - 1;
  for(int i=1; i<=n; i++) {
    int pre = a[i];
    a[i] = lower_bound(tmp+1, tmp+tot+1, a[i]) - tmp;
    v[a[i]] = pre;
  }
}
void build(int x) {
  int res = 0;
  for(int i=1; i<=tot; i++) cnt[i] = 0;
  for(int y=x; y<=num; y++) {
    for(int i=l[y]; i<=r[y]; i++) {
      int cur = a[i];
      cnt[cur]++;
      if(!res || cnt[cur]>cnt[res] || (cnt[cur]==cnt[res] && cur<res)) {
        res = cur;
      }
    }
    f[x][y] = res;
    g[x][y] = cnt[res];
  }
}
void init() {
  blo = sqrt(n);
  num = (n+blo-1)/blo;
  for(int i=1; i<=n; i++) bl[i] = (i-1)/blo + 1;
  for(int i=1; i<=num; i++) l[i] = (i-1)*blo + 1, r[i] = i*blo;
  r[num] = n;
  for(int i=1; i<=num; i++) build(i);
  for(int i=1; i<=n; i++) {
    p[a[i]].push_back(i);
    pos[i] = (int)p[a[i]].size() - 1;
  }
}
int qry(int x, int y) {
  int res = 0, cnt = 0;
  if(bl[x]+1<=bl[y]-1) res = f[bl[x]+1][bl[y]-1], cnt = g[bl[x]+1][bl[y]-1];
  for(int i=x; i<=min(r[bl[x]], y); i++) {
    int nxt = (a[i]<res ? cnt : cnt+1);
    while(pos[i]+nxt-1<(int)p[a[i]].size() && p[a[i]][pos[i]+nxt-1]<=y) {
      res = a[i];
      cnt = nxt++;
    }
  }
  if(bl[x]!=bl[y]) {
    for(int i=l[bl[y]]; i<=y; i++) {
      int nxt = (a[i]<res ? cnt : cnt+1);
      while(pos[i]-nxt+1>=0 && p[a[i]][pos[i]-nxt+1]>=x) {
        res = a[i];
        cnt = nxt++;
      }
    }
  }
  return res;
}
int main() {
  scanf("%d%d", &n, &m);
  for(int i=1; i<=n; i++) scanf("%d", a+i);
  lsh();
  init();
  int lstans = 0;
  while(m--) {
    int l, r;
    scanf("%d%d", &l, &r);
    l = (l + lstans - 1)%n + 1, r = (r + lstans - 1)%n + 1;
    if(l>r) swap(l, r);
    printf("%d\n", lstans = v[qry(l, r)]);
  }
  return 0;
}