题解 P3709 【大爷的字符串题】
诗乃
2019-03-20 18:29:03
题意：求区间众数出现次数。
%%%莫队的神仙
写一发分块瞎搞的题解
先随便离散化一下，然后随便分个块。分块后，预处理出第$i$~$j$块之间的众数出现次数，记为$MAX[i][j]$
搞一个$vector$按顺序记录存每个元素的出现位置，然后再记录一下每个元素在$vector$中的位置，记为$pos[i]$。
查询的时候，整块的整个统计。对于散块中的数，考虑一下它的出现次数有没有可能超过众数。
对于左边角的数，设当前数为$x$，我们在$vector$里面找到下标为$pos[x]+ans$的元素$y$，若$y≤r$，那么元素$y$的出现次数一定超过了$ans$，我们把$ans+1$。对于右边角的数，同理瞎搞一下。
总复杂度$O((n+m)\sqrt n)$。
代码：
```cpp
// luogu-judger-enable-o2
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 500050, BLNM = 5050;
void read(int &x) {
char ch; while(ch = getchar(), ch < '!'); x = ch - 48;
while(ch = getchar(), ch > '!') x = (x << 3) + (x << 1) + ch - 48;
}
int belong[MAXN], L[MAXN], R[MAXN], a[MAXN], MAX[BLNM][BLNM], blsz, n, q, w[MAXN], siz[MAXN], blnm, cnt[MAXN], lastans;
vector <int> lis[MAXN];
int main() {
read(n); read(q); blsz = sqrt(n);
for(int i = 1; i <= n; ++i) read(a[i]), w[i] = a[i], belong[i] = (i-1) / blsz + 1;
sort(a+1, a+n+1); int _n = unique(a+1, a+n+1) - a - 1;
for(int i = 1; i <= n; ++i) {
w[i] = lower_bound(a+1, a+_n+1, w[i]) - a;
siz[i] = lis[w[i]].size();
lis[w[i]].push_back(i);
} blnm = belong[n];
for(int i = 1; i <= blnm; ++i) L[i] = (i-1) * blsz, R[i] = L[i] + blsz - 1;
L[1] = 1; R[blnm] = n;
for(int i = 1; i <= blnm; ++i) {
memset(cnt, 0, sizeof cnt);
int mx = 0, ima = i;
for(int j = L[i]; j <= n; ++j) {
++cnt[w[j]];
mx = max(cnt[w[j]], mx);
if(j == R[ima]) {MAX[i][ima] = mx; ++ima;}
}
}
while(q--) {
int l, r; read(l); read(r);
int lblock = belong[l], rblock = belong[r]; lastans = 0;
if(lblock == rblock) {
for(int i = l; i <= r; ++i) while(siz[i] + lastans < lis[w[i]].size() && lis[w[i]][siz[i] + lastans] <= r) ++lastans;
} else {
if(lblock + 1 < rblock) lastans = MAX[lblock+1][rblock-1];
for(int i = l; i <= R[lblock]; ++i) while(siz[i] + lastans < lis[w[i]].size() && lis[w[i]][siz[i] + lastans] <= r) ++lastans;
for(int i = L[rblock]; i <= r; ++i) while(siz[i] >= lastans && lis[w[i]][siz[i] - lastans] >= l) ++lastans;
}
printf("%d\n", -lastans);
}
}
```