bzoj5178 [Jsoi2011]棒棒糖 主席树+线段树二分
2024-09-05 23:10:01
题目传送门
https://lydsy.com/JudgeOnline/problem.php?id=5178
https://lydsy.com/JudgeOnline/problem.php?id=2223
https://lydsy.com/JudgeOnline/problem.php?id=3524
三倍经验。
题解
这道题目很容易转化为求区间的众数。
但是很显然这个和区间众数还是有一些区别的,因为这里要求出的众数的数量一定大于一半。
也就是说,这个众数的出现次数比别的数的和还要多。
所以可以考虑用主席树维护,每一次都往区间和最大的点走。
最后比较一下是不是大于一半就可以了。
时间复杂度 \(O(n\log n)\)。
#include<bits/stdc++.h>
#define fec(i, x, y) (int i = head[x], y = g[i].to; i; i = g[i].ne, y = g[i].to)
#define dbg(...) fprintf(stderr, __VA_ARGS__)
#define File(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)
#define fi first
#define se second
#define pb push_back
template<typename A, typename B> inline char smax(A &a, const B &b) {return a < b ? a = b, 1 : 0;}
template<typename A, typename B> inline char smin(A &a, const B &b) {return b < a ? a = b, 1 : 0;}
typedef long long ll; typedef unsigned long long ull; typedef std::pair<int, int> pii;
template<typename I> inline void read(I &x) {
int f = 0, c;
while (!isdigit(c = getchar())) c == '-' ? f = 1 : 0;
x = c & 15;
while (isdigit(c = getchar())) x = (x << 1) + (x << 3) + (c & 15);
f ? x = -x : 0;
}
const int N = 500000 + 7;
int n, m, Q, nod;
int a[N], rt[N];
struct Node { int lc, rc, val; } t[N * 20];
inline void ins(int &o, int p, int L, int R, int x) {
t[o = ++nod] = t[p], ++t[o].val;
if (L == R) return;
int M = (L + R) >> 1;
if (x <= M) ins(t[o].lc, t[p].lc, L, M, x);
else ins(t[o].rc, t[p].rc, M + 1, R, x);
}
inline pii qval(int o, int p, int L, int R) {
if (L == R) return pii(t[o].val - t[p].val, L);
int M = (L + R) >> 1;
if (t[t[o].lc].val - t[t[p].lc].val > t[t[o].rc].val - t[t[p].rc].val) return qval(t[o].lc, t[p].lc, L, M);
else return qval(t[o].rc, t[p].rc, M + 1, R);
}
inline void work() {
for (int i = 1; i <= n; ++i) ins(rt[i], rt[i - 1], 1, m, a[i]);
while (Q--) {
int l, r;
read(l), read(r);
pii ans = qval(rt[r], rt[l - 1], 1, m);
if (ans.fi > (r - l + 1) / 2) printf("%d\n", ans.se);
else puts("0");
printf("%d\n", ans);
}
}
inline void init() {
read(n), read(Q);
for (int i = 1; i <= n; ++i) read(a[i]), smax(m, a[i]);
}
int main() {
#ifdef hzhkk
freopen("hkk.in", "r", stdin);
#endif
init();
work();
fclose(stdin), fclose(stdout);
return 0;
}
最新文章
- Configure bridge on a team interface using NetworkManager in RHEL 7
- IDEA 配置 tomcat的数据源
- 常见ES6新属性
- 并查集(涂色问题) HDOJ 4056 Draw a Mess
- Qt开发环境中使用报表控件FastReport遇到的一些问题(一)
- UITableView全面解析,讲的好详细
- [C# 基础知识梳理系列]专题六:泛型基础篇——为什么引入泛型
- P1643: [Usaco2007 Oct]Bessie&#39;s Secret Pasture 贝茜的秘密草坪
- Qt之自定义搜索框
- JQuery上传插件Uploadify
- 求职,找工作,平台大PK
- js/css 检测移动设备方向的变化 判断横竖屏幕
- 。net MVC 序列化 反序列化
- oracle状态
- Hbase出现ERROR: Can&#39;t get master address from ZooKeeper; znode data == null解决办法
- netty的解码器和粘包拆包
- 算法实践--最小生成树(Prim算法)
- Windows.UI.Cred.dll损坏导致不能设置 PIN 密码
- Testing - 软件测试知识梳理 - 比较质量保证(QA)与质量控制(QC)
- iOS APP 在前台时弹出本地通知
热门文章
- open 函数处理文件
- k8s上的基础概念和术语
- vue-element-template模板项目使用记录(持续更新)
- 阶段1 语言基础+高级_1-3-Java语言高级_08-JDK8新特性_第3节 两种获取Stream流的方式_11_练习:集合元素处理(Stream方式)
- 阶段1 语言基础+高级_1-3-Java语言高级_1-常用API_1_第6节 static静态_15_静态代码块
- Application.Restore不起作用了
- 练习2:python-把excel表格中某张表的内容导入sqlite
- 2017埙箫简谱清单分享(附音频Demo)
- 应用安全-安全设备-Waf系列-软Waf-D盾
- 应用安全-Web安全-注入篇