【分块】LOJ分块入门九

分块入门九

题目转移阵
image

思路整理

众数，就是给定一段范围，在这段范围所出现次数最多的数字（如果出现相同次数相同的），那么怎么才能称上是最多，最多是怎么来的？

最多是比较来的，通过每一种数字的数量的比较而来。

那么我们就需要能够算出所有数字在任意给定的区间的数量。

那要怎么做

首先，用vector存好每一个数字在给定区域内所有出现的位置

声明vector

vector<int> g[maxn];

g[x]存放的是值为x在区间的出现的所有的位置的有序序列（实际上是x离散化所得到的下标，我们可以通过另开一个数组去记录x所对应的value，val[x]=i）

但如果这样的话，真的合适吗？（相当于桶排，必然会带来空间的浪费）。

所以应该使用离散化的做法。

而离散化的对象是一个已经存在的数字，

而我们要如何去确定一个数字已经存在呢？

可以使用map或者unordered _map

cin>>a[i];
if(!mp(a[i]))
{
    mp[a[i]]=++cnt;//赋予a[i]一个新的下标
    val[cnt]=a[i];同时用一个数组存放这个下标对应的值
}
g[mp[a[i]]].push_back(i);

但这里仍然有个问题，也是这道题在LOJ上提交只能得到80分左右的原因。

就是用map（即便是map）取查询一个元素的时候，它所带来的代价并不是O(1),因而当多次使用map或者unordered_map的时候必然会带来一定的时间损耗。

因而这里可以再做一个调整

            if (!mp[ A[j] ])
            {
            	mp[ A[j] ] = ++cnt;
            	val[cnt] = A[j];
			}
                
            A[j] = mp[A[j]];
            pos[ A[j] ].push_back(j);

这样的话，就可以方便以后用二分搜索快速找到某个数在区间l到r的所有个数

(在整体区间中找到第一个大于位置r的位置的下标（即便是找到符合条件的，也会往外再跳一个，这样方便到时候不用再去做减一的操作），并以此减去第一个大于或等于位置l的位置的下标，从而获取个数。

int query(int l,int r,int x)
{
     greater_bound(g[x].begin(),g[x].end(),r)-lower_bound(g[x].begin(),g[x].end(),l)
}

整体思路

  1. 预先处理地动态处理好块l到块r的众数

  2. 然后查l到r的众数，分三个区域来做

  3. 就是先用l到r区域之间的整块段的众数提取出来扔到二分搜索函数里面跑一遍，得到个数（这个预先存好的众数答案在这个区间段是无敌的）。

  4. 然后再把左右俩个散块的众数提取出来各跑一遍

  5. 得到三个答案然后再取最优

80分代码

#include <bits/stdc++.h>
#define MEM(a,x) memset(a,x,sizeof(a))
#define W(a) while(a)
#define gcd(a,b) __gcd(a,b)
#define pi acos(-1.0)
#define PII pair<int,int>
#define fi first
#define se second
#define ll long long
#define ull unsigned long long
#define rep(i,x,n) for(int i=x;i<n;i++)
#define repd(i,x,n) for(int i=x;i<=n;i++)
#define MAX 1000005
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define lowbit(x) (x&-x)
#define de() cout<<"debug"<<endl;
using namespace std;
const int N = 1e5 + 10, KN = 4E4 + 10, FN = 4005;
int t, blen, n, A[N], bel[N], st[KN], ed[KN], f[FN][FN],cnt[N];
unordered_map<int, int> mp, pcnt;
vector<int> pos[N];
void predo(int x) {
    memset(cnt, 0, sizeof(cnt));
    int mmax = 0, ans = 0;
    for (int i = st[x]; i <= n; i++) {
        cnt[ mp[A[i]] ]++;
        int p = bel[i];
        if (cnt[ mp[A[i]] ] > mmax || (cnt[ mp[A[i]] ] == mmax && ans > A[i])) {
            mmax = cnt[ mp[A[i]] ];
            ans = A[i];
        }
        f[x][p] = ans;
    }
}
inline int get_num(int l, int r, int x) {
    return upper_bound(pos[ mp[x] ].begin(), pos[ mp[x] ].end(), r) - lower_bound(pos[ mp[x] ].begin(),
            pos[ mp[x] ].end(), l);
}
inline int ask(int l, int r) {
    int res, maxn = 0, val;

    if (bel[l] == bel[r]) {
        repd(i, l, r) {
            int num = get_num(l, r, A[i]);

            if (num > maxn || (num == maxn && val > A[i])) {
                maxn = num;
                val = A[i];
            }
        }
        res = val;
    } else {
        if (bel[l] + 1 <= bel[r] - 1) {
            maxn = get_num(l, r, f[ bel[l] + 1 ][ bel[r] - 1 ]);
            val = f[ bel[l] + 1 ][ bel[r] - 1 ];
        }

        repd(i, l, ed[ bel[l] ]) {
            int num = get_num(l, r, A[i]);

            if (num > maxn || (num == maxn && val > A[i])) {
                maxn = num;
                val = A[i];
            }
        }

        repd(i, st[ bel[r] ], r) {
            int num = get_num(l, r, A[i]);

            if (num > maxn || (num == maxn && val > A[i])) {
                maxn = num;
                val = A[i];
            }
        }
        res = val;
    }

    return res;
}
int main() {
    cin >> n;
    blen = 30;
    t = n / blen;
    repd(i, 1, t) {
        st[i] = (i - 1) * blen + 1;
        ed[i] = i * blen;
    }

    if (ed[t] < n)
        t++, st[t] = ed[t - 1] + 1, ed[t] = n;

    int cnt = 0;
    repd(i, 1, t) {
        repd(j, st[i], ed[i]) {
            scanf("%d", &A[j]);

            if (!mp[ A[j] ])
                mp[ A[j] ] = cnt++;

            pos[ mp[A[j]] ].push_back(j);
            bel[j] = i;
        }
    }
    repd(i, 1, t)
    predo(i);
    repd(i, 1, n) {
        int l, r;
        scanf("%d%d", &l, &r);
        printf("%d
", ask(l, r));
    }
    return 0;
}

100代码

#include <bits/stdc++.h>
#define MEM(a,x) memset(a,x,sizeof(a))
#define W(a) while(a)
#define gcd(a,b) __gcd(a,b)
#define pi acos(-1.0)
#define PII pair<int,int>
#define fi first
#define se second
#define ll long long
#define ull unsigned long long
#define rep(i,x,n) for(int i=x;i<n;i++)
#define repd(i,x,n) for(int i=x;i<=n;i++)
#define MAX 1000005
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define lowbit(x) (x&-x)
#define de() cout<<"debug"<<endl;
using namespace std;
const int N = 1e5 + 10, KN = 4E4 + 10, FN = 2005;//1e5/80
int t, blen, n, A[N], bel[N], st[KN], ed[KN], f[FN][FN],cnt[N];
ll val[N];
unordered_map<int, int> mp;
vector<int> pos[N];
void predo(int x) {
    memset(cnt, 0, sizeof(cnt));
    int mmax = 0, ans = 0;
    for (int i = st[x]; i <= n; i++) {
        cnt[ A[i] ]++;
        int p = bel[i];
        if (cnt[ A[i] ] > mmax || (cnt[ A[i] ] == mmax && val[ ans ] > val[ A[i] ])) {
            mmax = cnt[ A[i] ];
            ans = A[i];
        }
        f[x][p] = ans;
    }
}
inline int get_num(int l, int r, int x) {
    return upper_bound(pos[ x ].begin(), pos[ x ].end(), r) - lower_bound(pos[ x ].begin(),pos[ x ].end(), l);
}
inline ll ask(int l, int r) {
    int maxn = 0, ans;
    ll res;
    if (bel[l] == bel[r]) {
        repd(i, l, r) {
            int num = get_num(l, r, A[i]);

            if (num > maxn || (num == maxn && val[ans] > val[A[i]] )) {
                maxn = num;
                ans = A[i];
            }
        }
        res = val[ ans ];
    } else {
        if (bel[l] + 1 <= bel[r] - 1) {
            maxn = get_num(l, r, f[ bel[l] + 1 ][ bel[r] - 1 ]);
            ans = f[ bel[l] + 1 ][ bel[r] - 1 ];
        }

        repd(i, l, ed[ bel[l] ]) {
            int num = get_num(l, r, A[i]);

            if (num > maxn || (num == maxn && val[ans] > val[ A[i] ])) {
                maxn = num;
                ans = A[i];
            }
        }

        repd(i, st[ bel[r] ], r) {
            int num = get_num(l, r, A[i]);

            if (num > maxn || (num == maxn && val[ans] > val[ A[i] ])) {
                maxn = num;
                ans = A[i];
            }
        }
        res = val[ ans ];
    }

    return res;
}
int main() {
    cin >> n;
    blen = 80;
    t = n / blen;
    repd(i, 1, t) {
        st[i] = (i - 1) * blen + 1;
        ed[i] = i * blen;
    }

    if (ed[t] < n)
        t++, st[t] = ed[t - 1] + 1, ed[t] = n;

    int cnt = 0;
    repd(i, 1, t) {
        repd(j, st[i], ed[i]) {
            scanf("%d", &A[j]);

            if (!mp[ A[j] ])
            {
            	mp[ A[j] ] = ++cnt;
            	val[cnt] = A[j];
			}
                
            A[j] = mp[A[j]];
            pos[ A[j] ].push_back(j);
            bel[j] = i;
        }
    }
    repd(i, 1, t)
    predo(i);
    repd(i, 1, n) {
        int l, r;
        scanf("%d%d", &l, &r);
        printf("%lld
", ask(l, r));
    }
    return 0;
}

其他

关于块长长度的思考

块长不宜过长，也不宜过短
块过长的话，零散块中提取的数字就多，数字一多，单次查询的量就偏多
块过短的话，在预处理整块段的众数的时候，消耗的时间将会大大地增加。极限情况下，当块长为1的时候，将会得到(n^{2})的复杂度。

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/BeautifulWater/p/15241357.html