BZOJ-2724 蒲公英
2022/5/23 23:22:53
本文主要是介绍BZOJ-2724 蒲公英,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
蒲公英
求区间众数
分块
用的蓝书法二做的:预处理每个区间的最大众数,然后二分检查更新答案,同时更新边角的答案,记得分块的数量的是 \(\sqrt{m * log_{2}n}\)
这个代码过不了 acwing 的:https://www.acwing.com/problem/content/251/
#include <iostream> #include <cstdio> #include <algorithm> #include <cmath> #include <vector> using namespace std; typedef long long ll; const int maxn = 4e4 + 10; #define endl '\n' int num[maxn], a[maxn]; int L[maxn], R[maxn], pos[maxn]; int id[maxn], cnt[maxn]; int h[1010][1010]; vector<int>b[maxn]; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); // freopen("text.in", "rb", stdin); // freopen("text.out", "wb", stdout); int n, m; cin >> n >> m; for(int i=1; i<=n; i++) {cin >> num[i]; a[i] = num[i];} sort(a + 1, a + 1 + n); int tp = 0, nn = max(1, (int)(n / sqrt(m * log2(n)))); int t = n / nn; a[0] = a[1] - 1; for(int i=1; i<=n; i++) { if(a[i] != a[i-1]) { id[++tp] = a[i]; } } for(int i=1; i<=n; i++) { num[i] = lower_bound(id + 1, id + tp + 1, num[i]) - id; b[num[i]].push_back(i); // cout << num[i] << " "; } // cout << endl; for(int i=1; i<=t; i++) { L[i] = R[i-1] + 1; R[i] = i * nn; // cout << L[i] << " " << R[i] << endl; } // cout << endl << endl; if(R[t] < n) { t++; L[t] = R[t-1] + 1; R[t] = n; } for(int i=1; i<=t; i++) { for(int j=L[i]; j<=R[i]; j++) { pos[j] = i; } } for(int i=1; i<=t; i++) { for(int j=0; j<=tp; j++) cnt[j] = 0; for(int j=i; j<=t; j++) { int x = h[i][j-1]; int y = cnt[x]; for(int k=L[j]; k<=R[j]; k++) { cnt[num[k]]++; if(cnt[num[k]] > y || (cnt[num[k]] == y && num[k] < x)) { x = num[k]; y = cnt[x]; } } h[i][j] = x; } } int ans = 0, way = 0; while(m--) { int x, y; cin >> x >> y; x = (x + ans - 1) % n + 1; y = (y + ans - 1) % n + 1; if(x > y) swap(x, y); // cout << x << " " << y << endl; int tx = pos[x], ty = pos[y]; ans = way = 0; if(tx == ty) { for(int i=x; i<=y; i++) { int temp = upper_bound(b[num[i]].begin(), b[num[i]].end(), y) - lower_bound(b[num[i]].begin(), b[num[i]].end(), x); if(temp > way || (temp == way && num[i] < ans)) { ans = num[i]; way = temp; } } } else { for(int i=x; i<=R[tx]; i++) { int temp = upper_bound(b[num[i]].begin(), b[num[i]].end(), y) - lower_bound(b[num[i]].begin(), b[num[i]].end(), x); if(temp > way || (temp == way && num[i] < ans)) { ans = num[i]; way = temp; } } for(int i=L[ty]; i<=y; i++) { int temp = upper_bound(b[num[i]].begin(), b[num[i]].end(), y) - lower_bound(b[num[i]].begin(), b[num[i]].end(), x); if(temp > way || (temp == way && num[i] < ans)) { ans = num[i]; way = temp; } } if(tx + 1 <= ty - 1) { int now = h[tx+1][ty-1]; int temp = upper_bound(b[now].begin(), b[now].end(), y) - lower_bound(b[now].begin(), b[now].end(), x); if(temp > way || (temp == way && now < ans)) { ans = now; way = temp; } } } ans = id[ans]; cout << ans << endl; } return 0; }
这篇关于BZOJ-2724 蒲公英的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)
- 2024-05-30【Java】百万数据excel导出功能如何实现
- 2024-05-30我们小公司,哪像华为一样,用得上IPD(集成产品开发)?
- 2024-05-30java excel上传--poi
- 2024-05-30安装笔记本应用商店的pycharm,再安排pandas等模块,说是没有打包工具?
- 2024-05-29java11新特性
- 2024-05-29哪些无用敏捷指标正在破坏敏捷转型?
- 2024-05-29鸿蒙原生应用再新丁!新华社 入局鸿蒙
- 2024-05-29设计模式 之 迭代器模式(Iterator)