249. 蒲公英

本文主要是介绍249. 蒲公英，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：249. 蒲公英

算法分析

进阶指南上算法描述已经很清晰了。这里是用vector维护的每个数在序列中出现的下标。假设总共T块，预处理出每两个块之间的最小众数，需要时间O(nT)。m个查询小块内每个数的出现次数为O(mn/T*logn)，总体时间复杂度为两者之和。

根据均值不等式，如果时间复杂度最低，应满足$nT=mn/Tlogn$，求得$T=\sqrt{nlogn}$，这里面n<=40000，用$blo$表示块的长度，$blo=n/T$，求得$blo$约等于52。

因此：$blo=52$

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <vector>
#define ll long long
#define inf 0x7fffffff 
using namespace std;
const int N = 40010;
int n, m, a[N], lsh[N], bl[N], num[N], ori[N];  // ori[]表示离散化后原来的数  
int f[1000][1000]; // 保存块与块之间的最小众数  
int blo = 52; // 根据均值不等式计算出来的块的大小  
vector<int> v[N];
int szread()
{int x = 0, f = 1; char c = getchar();while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}while (c >= '0' && c <= '9') {x = x * 10 + c - '0'; c = getchar();}return x * f; 
}
void cal(int t)  // 第t块  
{int val = 0, maxn = -1;memset(num, 0, sizeof(num));for (int i = (t - 1) * blo + 1; i <= n; ++i){++num[a[i]];if (num[a[i]] > maxn || (num[a[i]] == maxn && a[i] < val)){maxn = num[a[i]];val = a[i]; }		f[t][bl[i]] = val;  // 放到if外面  }
}
void pre()
{for (int i = 1; i <= n; ++i) v[a[i]].push_back(i);for (int i = 1; i <= bl[n]; ++i) cal(i); // 计算[i, bl[n]]块的f值  
}
int main()
{n = szread(); m = szread();for (int i = 1; i <= n; ++i) a[i] = lsh[i] = szread();// 离散化  sort(lsh + 1, lsh + n + 1);int cnt = unique(lsh + 1, lsh + n + 1) - lsh - 1;for (int i = 1; i <= n; ++i) {int t = a[i];a[i] = lower_bound(lsh + 1, lsh + cnt + 1, a[i]) - lsh;ori[a[i]] = t;  // }		// 预处理  for (int i = 1; i <= n; ++i) bl[i] = (i - 1) / blo + 1;pre(); // 处理询问  int x = 0;for (int i = 1; i <= m; ++i){int l = szread(), r =szread();l = ((l + x - 1) % n) + 1;r = ((r + x - 1) % n) + 1;if (l > r) swap(l, r);int val = f[bl[l]+1][bl[r]-1];  // 整块的众数，离散化后的  int maxn = upper_bound(v[val].begin(), v[val].end(), r) - lower_bound(v[val].begin(), v[val].end(), l);// 计算左边小块的每个数在[l,r]出现的次数 for (int j = l; j <= min(bl[l]*blo,n); ++j) {int tem = upper_bound(v[a[j]].begin(), v[a[j]].end(), r) - lower_bound(v[a[j]].begin(), v[a[j]].end(), l);if (tem > maxn || (tem == maxn && a[j] < val)){maxn = tem;val = a[j];}}// 计算右边的小块  if (bl[l] != bl[r]){for (int j = (bl[r]-1)*blo + 1; j <= r; ++j){int tem = upper_bound(v[a[j]].begin(), v[a[j]].end(), r) - lower_bound(v[a[j]].begin(), v[a[j]].end(), l);if (tem > maxn || (tem == maxn && a[j] < val)){maxn = tem;val = a[j];}}}//printf("%d\n", ori[val]);x = ori[val];} return 0;
}

反思与总结

1. 在预处理$pre$函数中，计算f[][]要放在if外面，小细节，很容易忽略。

2. 离散化后，最后求的结果，要将原始值输出，容易忘记。ori[val]代表离散化后值为val的原始值。

3. 注意upper_bound()和lower_bound()的使用。

这篇关于249. 蒲公英的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---