9.数列分块入门 9

😊 | Powered By HeartFireY | 分块例题

#6285. 数列分块入门 9 - 题目 - LibreOJ (loj.ac)

WTF卡常？？？

首先 D P DP DP预处理出完整的块 i i i到完整的块 j j j之间的最小众数 d p [ i ] [ j ] dp[i][j] dp[i][j]。

用一个 v e c t o r vector vector邻接表保存相同的下标，

然后就根据 u p p e r _ b o u n d upper\_bound upper_bound和 l o w e r _ b o u n d lower\_bound lower_bound求出完整块里的该众数个数，然后相同的方法暴力处理不完整的块即可。

优化可以忽略不计，把块的长度设为 100 100 100就不会 T L E TLE TLE了。或者离散化一下？

#include 
#pragma GCC optimize("O3")
#pragma G++ optimize("O3")
#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC optimize("no-stack-protector")
using namespace std;

const int N = 2e5 + 10;
int id[N], blo, n, tot;
int a[N], val[N], cnt[N], dp[1010][1010];

vector block[N];
unordered_mapmp;

void init(int pos){
    memset(cnt, 0, sizeof(cnt));
    register int maxx = 0, ans = 0;
    for(register int i = (pos - 1) * blo + 1; i  maxx || (cnt[a[i]] == maxx && val[a[i]] < val[ans])) ans = a[i], maxx = cnt[a[i]];
        dp[pos][id[i]] = ans;
    }
}

inline int getlen(int l, int r, int x){
    return upper_bound(block[x].begin(), block[x].end(), r) - lower_bound(block[x].begin(), block[x].end(), l);
}

int query(int l, int r){
    register int ans, maxx;
    ans = dp[id[l] + 1][id[r] - 1];
    maxx = getlen(l, r, ans);
    for(register int i = l; i  maxx || (tmp == maxx && val[a[i]] < val[ans]))
            ans = a[i], maxx = tmp;
    }
    if(id[l] == id[r]) return ans;
    for(register int i = (id[r] - 1) * blo + 1; i  maxx || (tmp == maxx && val[a[i]] < val[ans]))
            ans = a[i], maxx = tmp;
    }
    return ans;
}

inline int read(){
    register int f = 1, x = 0; register char s = getchar(); 
    while(s < '0'||s > '9'){ if(s =='-') f = -1; s = getchar(); } 
    while(s >= '0' && s