首页 > 代码库 > 【bzoj2724】[Violet 6]蒲公英 分块+STL-vector
【bzoj2724】[Violet 6]蒲公英 分块+STL-vector
题目描述
.gif)
输入
.gif)
修正一下
l = (l_0 + x - 1) mod n + 1, r = (r_0 + x - 1) mod n + 1
输出
.gif)
样例输入
6 3
1 2 3 2 1 2
1 5
3 6
1 5
样例输出
1
2
1
题解
分块+STL-vector
一个显而易见的结论：区间众数一定是一段连续的块的众数或块外的数，证明略（逃
先把数据离散化，然后分块预处理出f[i][j]，表示从块i到块j的众数位置。具体实现的话直接开个桶存一下就好了。
然后考虑询问，整块的直接拿出来求一下出现次数，块外的单独拿出来求一下出现次数，只要求$2\sqrt n+1$次。
现在只要想出怎样求出来出现次数即可。一个简单地方法是：对于每个数开一个vector存一下出现位置，然后在vector上二分查找出现位置。
总时间复杂度为$O(n\sqrt n\log n)$，常数有点大...
#include <cstdio>#include <cmath>#include <vector>#include <cstring>#include <algorithm>#define N 50010#define bl(x) (x - 1) / siusing namespace std;vector<int> v[N];int a[N] , c[N] , cnt[N] , f[250][250] , ref[N];int query(int p , int l , int r){ return upper_bound(v[p].begin() , v[p].end() , r) - lower_bound(v[p].begin() , v[p].end() , l);}int main(){ int n , m , si , i , j , t , maxn , x , y , ans , last = 0; scanf("%d%d" , &n , &m) , si = (int)sqrt(n); for(i = 1 ; i <= n ; i ++ ) scanf("%d" , &a[i]) , c[i] = a[i]; sort(c + 1 , c + n + 1); for(i = 1 ; i <= n ; i ++ ) t = a[i] , a[i] = lower_bound(c + 1 , c + n + 1 , a[i]) - c , v[a[i]].push_back(i) , ref[a[i]] = t; for(i = 0 ; i <= (n - 1) / si ; i ++ ) { memset(cnt , 0 , sizeof(cnt)) , maxn = 0; for(j = i * si + 1 ; j <= n ; j ++ ) { cnt[a[j]] ++ ; if(cnt[a[j]] > maxn || (cnt[a[j]] == maxn && a[j] < t)) maxn = cnt[a[j]] , t = a[j]; if(j % si == 0) f[i][bl(j)] = t; } } while(m -- ) { scanf("%d%d" , &x , &y) , x = (x + last - 1) % n + 1 , y = (y + last - 1) % n + 1 , maxn = 0; if(x > y) swap(x , y); if(bl(y) - bl(x) < 2) { for(i = x ; i <= y ; i ++ ) if((t = query(a[i] , x , y)) > maxn || (t == maxn && a[i] < ans)) maxn = t , ans = a[i]; } else { for(i = x ; i <= (bl(x) + 1) * si ; i ++ ) if((t = query(a[i] , x , y)) > maxn || (t == maxn && a[i] < ans)) maxn = t , ans = a[i]; if((t = query(f[bl(x) + 1][bl(y) - 1] , x , y)) > maxn || (t == maxn && f[bl(x) + 1][bl(y) - 1] < ans)) maxn = t , ans = f[bl(x) + 1][bl(y) - 1]; for(i = bl(y) * si + 1 ; i <= y ; i ++ ) if((t = query(a[i] , x , y)) > maxn || (t == maxn && a[i] < ans)) maxn = t , ans = a[i]; } printf("%d\n" , last = ref[ans]); } return 0;}
【bzoj2724】[Violet 6]蒲公英 分块+STL-vector
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。