当前位置: 首页 > news >正文

Codeforces 2149G Buratsuta 3 题解 [ 蓝 ] [ 摩尔投票 ] [ 线段树 ] [ 随机化 ] [ 主席树 ] [ 根号分治 ]

Buratsuta 3:典中典中典中典中典了属于是。

Sol.1 摩尔投票

首先维护区间出现次数大于等于 $\left \lfloor \dfrac{len}{k} \right \rfloor $ 次的数是摩尔投票板子,每次把 \(k\) 个不同的数相消即可。然后因为摩尔投票具有结合律,所以可以上线段树维护,时间复杂度 \(O(n + q\log n)\)。注意需要判断解是否合法。

注意到此题没有修改操作,所以如果直接上猫树可以做到 \(O(n\log n + q)\) 的复杂度。

#include <bits/stdc++.h>
#define fi first
#define se second
#define eb(x) emplace_back(x)
#define pb(x) push_back(x)
#define lc (p << 1)
#define rc ((p << 1) | 1)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
using pi = pair<int, int>;
const int N = 200005;
int n, q, a[N], b[N], bn;
int getrk(int x)
{return (lower_bound(b + 1, b + bn + 1, x) - b);
}
struct Node{int l, r;int val1, cnt1, val2, cnt2;
};
struct Segtree{Node tr[4 * N];void pushup(Node &p, Node ls, Node rs){if(rs.cnt1 && rs.val1 == ls.val1) ls.cnt1 += rs.cnt1;else if(rs.cnt1 && rs.val1 == ls.val2) ls.cnt2 += rs.cnt1;else if(rs.cnt1){int mn = min(rs.cnt1, min(ls.cnt1, ls.cnt2));rs.cnt1 -= mn;ls.cnt1 -= mn;ls.cnt2 -= mn;if(rs.cnt1 && ls.cnt1 == 0) ls.val1 = rs.val1, ls.cnt1 = rs.cnt1;else if(rs.cnt1 && ls.cnt2 == 0) ls.val2 = rs.val1, ls.cnt2 = rs.cnt1;        }if(rs.cnt2 && rs.val2 == ls.val1) ls.cnt1 += rs.cnt2;else if(rs.cnt2 && rs.val2 == ls.val2) ls.cnt2 += rs.cnt2;else if(rs.cnt2){int mn = min(rs.cnt2, min(ls.cnt1, ls.cnt2));rs.cnt2 -= mn;ls.cnt1 -= mn;ls.cnt2 -= mn;if(rs.cnt2 && ls.cnt1 == 0) ls.val1 = rs.val2, ls.cnt1 = rs.cnt2;else if(rs.cnt2 && ls.cnt2 == 0) ls.val2 = rs.val2, ls.cnt2 = rs.cnt2;   }p.val1 = ls.val1;p.val2 = ls.val2;p.cnt1 = ls.cnt1;p.cnt2 = ls.cnt2;        }void build(int p, int ln, int rn){tr[p] = {ln, rn, a[ln], 1, 0, 0};if(ln == rn) return;int mid = (ln + rn) >> 1;build(lc, ln, mid);build(rc, mid + 1, rn);pushup(tr[p], tr[lc], tr[rc]);}Node query(int p, int ln, int rn){if(ln <= tr[p].l && tr[p].r <= rn) return tr[p];int mid = (tr[p].l + tr[p].r) >> 1;if(rn <= mid) return query(lc, ln, rn);if(ln >= mid + 1) return query(rc, ln, rn);Node tmp;pushup(tmp, query(lc, ln, rn), query(rc, ln, rn));return tmp;}
}tr1;
vector<int> vis[N];
int query_num(int l, int r, int v)
{return (upper_bound(vis[v].begin(), vis[v].end(), r) - lower_bound(vis[v].begin(), vis[v].end(), l));
}
void solve()
{cin >> n >> q;bn = 0;for(int i = 1; i <= n; i++){cin >> a[i];b[++bn] = a[i];vis[i].clear();}sort(b + 1, b + bn + 1);bn = unique(b + 1, b + bn + 1) - b - 1;for(int i = 1; i <= bn; i++) vis[i].push_back(0);for(int i = 1; i <= n; i++){a[i] = getrk(a[i]);vis[a[i]].push_back(i);}for(int i = 1; i <= bn; i++) vis[i].push_back(n + 1);tr1.build(1, 1, n);for(int i = 1; i <= q; i++){int l, r;cin >> l >> r;Node res = tr1.query(1, l, r);int ans1 = res.val1, ans2 = res.val2;if(ans1 > ans2) swap(ans1, ans2);int lmt = (r - l + 1) / 3, cnt3 = 0;if(ans1){int cnt1 = query_num(l, r, ans1);if(cnt1 > lmt){cout << b[ans1] << " ";cnt3++;}}if(ans2){int cnt2 = query_num(l, r, ans2);if(cnt2 > lmt){cout << b[ans2] << " ";cnt3++;}}if(cnt3 == 0) cout << -1 << " ";cout << "\n";}
}int main()
{//freopen("sample.in", "r", stdin);//freopen("sample.out", "w", stdout);ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t;cin >> t;while(t--) solve();return 0;
}

Sol.2 随机化

随机在区间内选若干个点,然后判断一下出现次数最多的解是否合法。具体我没试选多少个点可以通过,但应该在 \(200\) 个左右。

Sol.3 根号分治

\(len \le \sqrt n\) 的区间暴力求解,对 \(len > \sqrt n\) 预处理出现次数在 \(\dfrac{\sqrt n}{3}\) 以上的数的出现位置,查询的时候二分即可。容易发现预处理的点大概就是 \(\sqrt n\) 量级的。所以时间复杂度为 \(O(n\sqrt n\log n)\)

http://www.hskmm.com/?act=detail&tid=21571

相关文章:

  • 2025 年最新推荐软件开发机构榜:聚焦微服务架构与 724 小时服务的优质厂商精选指南人力资源管理系统/资产管理系统/数据中台管理系统/流程管理系统软件开发公司推荐
  • 【半导体物理 | 学习笔记】第一章 半导体中的电子状态
  • 计数(5):多项式相关
  • 最新WTAPI开发微信机器人教程说明
  • 线性DP - 学习笔记
  • 2025 年最新制氮机厂家权威推荐排行榜:聚焦行业优质厂商综合实力,助力企业精准选购优质设备制氮机产生氮气/氮气纯化/设备改造/维修/保养/半导体用制氮机厂家推荐
  • 2025 年氨分解设备厂家最新推荐榜单:含半导体 / 冶金 / 稀土行业专用设备及品牌综合实力排名
  • 2025 阳台装修公司推荐榜:最新优质厂商资质 / 技术 / 服务测评,杭州浙江地区优选指南杭州阳台装修/浙江阳台装修公司推荐
  • bitset
  • 网易雷火胡志鹏:AI驱动未来,游戏科技重塑虚拟创造力与现实生产力
  • idea打包推送maven仓库及同时推送到不同的maven仓库,本地和云上的腾讯云
  • 2025 阳台柜厂家最新推荐榜:企业资质 / 材质 / 服务全景解析,选对品牌少走弯路杭州阳台柜/浙江阳台柜厂家推荐
  • 2025 年除湿机厂家最新权威推荐排行榜:实力厂家技术口碑评测及场景适配选购指南吊顶/泳池/车库/防爆/调温/新风除湿机厂家推荐
  • 2025 年液氨蒸发器厂家联系方式,众众电热:多领域加热设备供应与定制化解决方案提供商
  • 【Batch】批量修改文件后缀
  • 【solace】基于docker部署solace环境
  • 2025 年阿里巴巴开通实力商家店铺开通代运营 / 阿里巴巴新手开店全托管代运营公司推荐:南鑫粤网络 —— 全域运营解决方案与实战服务优势解析
  • Vue-element-admin开发指南 - 教程
  • 2025 年国内工作服厂家最新推荐排行榜:聚焦工艺设计与服务,精选权威榜单助企业采购冬季/春季/工人/车间/防静电/餐饮/劳保工作服厂家推荐
  • ClickHouse 窗口函数使用详解(一) - 若
  • ClickHouse 窗口函数详解:告别 GROUP BY 的局限性,实现灵活数据分析 - 若
  • 简单WEB网站
  • AtCoder AGC044 总结
  • UOJ#32【UR #2】跳蚤公路 题解
  • 2025 年窗帘杆源头厂家最新推荐榜单:包含支架 / 环 / 全自动 / 可伸缩等多类产品及配件,帮助选到品质与交期双优的优质厂家
  • 2025 年电动窗帘厂家推荐榜单:聚焦国内优质企业定制实力与口碑,为采购者提供最新选择参考电动窗帘系统/电机/轨道/配件/智能电动窗帘厂家推荐
  • Vue3 使用注意事项
  • ClickHouse ReplacingMergeTree 去重陷阱:为什么你的 FINAL 查询无效? - 若
  • js中?? 和 || 的区别详解
  • 微信机器人API接口| 个人开发者必备