LOJ6285 数列分块入门9（分块区间众数）题解

浅浅的花香味﹌ 2021-12-20 04:55 234阅读 0赞

题意：给出区间内的最小众数

思路：分块，离散化每个数，开vector记录每个数p出现的位置，这样就能二分出L，R以内p的个数了。众数有一个性质，用mode(a)表示集合a的众数，那么mode(a∪b) ∈ mode(a)∪b 。那么我先预处理出任意两块的众数f\[i\]\[j\]，这样众数就是f\[i\]\[j\]和旁边两块数中的其中一个了，直接遍历这些数即可。

block不能开方，开30能过。都靠玄学....

代码：

#include<cmath>
    #include<set>
    #include<map>
    #include<queue>
    #include<cstdio>
    #include<vector>
    #include<cstring>
    #include <iostream>
    #include<algorithm>
    #include<unordered_map>
    using namespace std;
    typedef long long ll;
    typedef unsigned long long ull;
    const int maxn = 1e5 + 10;
    const int M = maxn * 30;
    const ull seed = 131;
    const int INF = 0x3f3f3f3f;
    const int MOD = 1e4 + 7;
    struct Block{
        int l, r;
    }b[maxn];
    int a[maxn], belong[maxn];
    int f[10000][10000];   //i~j块的众数是
    int num[maxn];
    int n, block;
    vector<int> vv;
    vector<int> pos[maxn];
    void init(){
        for(int i = 1; i <= belong[n]; i++){    //暴力计算f数组
            for(int j = 0; j <= vv.size(); j++) num[j] = 0;
            int mode = INF, NUM = 0;
            for(int j = b[i].l; j <= n; j++){
                num[a[j]]++;
                if(num[a[j]] > NUM || (num[a[j]] == NUM && a[j] < mode)){
                    mode = a[j];
                    NUM = num[a[j]];
                }
                f[i][belong[j]] = mode;
            }
        }
    }
    int getNum(int l, int r, int v){
        int t = upper_bound(pos[v].begin(), pos[v].end(), r) - lower_bound(pos[v].begin(), pos[v].end(), l);
        return t;
    }
    int query(int l, int r){
        int bl = belong[l], br = belong[r];
        int ans = INF, NUM = 0;
        if(bl == br){
            for(int i = l; i <= r; i++){
                int tot = getNum(l, r, a[i]);
                if(tot > NUM || (tot == NUM && a[i] < ans)){
                    ans = a[i];
                    NUM = tot;
                }
            }
        }
        else{
            for(int i = l; i <= b[bl].r; i++){
                int tot = getNum(l, r, a[i]);
                if(tot > NUM || (tot == NUM && a[i] < ans)){
                    ans = a[i];
                    NUM = tot;
                }
            }
            if(bl + 1 <= br - 1){
                int v = f[bl + 1][br - 1];
                int tot = getNum(l, r, v);
                if(tot > NUM || (tot == NUM && v < ans)){
                    ans = v;
                    NUM = tot;
                }
            }
            for(int i = b[br].l; i <= r; i++){
                int tot = getNum(l, r, a[i]);
                if(tot > NUM || (tot == NUM && a[i] < ans)){
                    ans = a[i];
                    NUM = tot;
                }
            }
        }
        return vv[ans - 1];
    }
    
    int main(){
        scanf("%d", &n);
        vv.clear();
        for(int i = 1; i <= n; i++){
            scanf("%d", &a[i]);
            vv.push_back(a[i]);
        }
    
        sort(vv.begin(), vv.end());
        vv.erase(unique(vv.begin(), vv.end()), vv.end());
        for(int i = 1; i <= n; i++){
            a[i] = lower_bound(vv.begin(), vv.end(), a[i]) - vv.begin() + 1;
        }
        for(int i = 0; i <= vv.size(); i++) pos[i].clear();
    
        block = 30;
        for(int i = 1; i <= n; i++){
            belong[i] = (i - 1) / block + 1;
            pos[a[i]].push_back(i);
        }
        for(int i = 1; i <= belong[n]; i++){
            b[i].l = (i - 1) * block + 1;
            b[i].r = b[i].l + block - 1;
        }
        b[belong[n]].r = n;
    
        init();
        for(int i = 1; i <= n; i++){
            int l, r;
            scanf("%d%d", &l, &r);
            printf("%d\n", query(l, r));
        }
        return 0;
    }

转载于:https://www.cnblogs.com/KirinSB/p/10914583.html