朝田诗乃 的博客

朝田诗乃 的博客

题解 P3709 【大爷的字符串题】

posted on 2019-03-20 18:29:03 | under 题解 |

题意:求区间众数出现次数。

%%%莫队的神仙

写一发分块瞎搞的题解

先随便离散化一下,然后随便分个块。分块后,预处理出第 $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)$ 。

代码:

// 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);
    }
}