GoldenPotato137的小屋

splay
splay

[Luogu P3285][SCOI2014]方伯伯的OJ

题面 洛谷P3285 Solution 这是一道数据结构大暴力题。 我们可以很显然的发现对于询问排名,维护排名的操作,我们可以直接上一个维护下标的splay。 因为点的数量奇多,这让我们回想起NOIP2017 列队,我们可以用“splay 动态开点”这样的操作来解决,即一开始我们把所有信息全部压到一个点里面去(即一个点代表一段区间),需要的时候再用“拆点”把点拆开。 问题是这破题很让人讨厌地出了两个基于编号的操作。因为我们的splay是以下标做为权值来的,失去了维护编号的能力。 怎么办呢?我们可以考虑直接记录每个编…

2019年3月11日 1条评论 998点热度 0人点赞 GoldenPotato137 阅读全文
splay

[Luogu P4197] Peaks

题面 洛谷P4197 Solution 这题的确是可以用库鲁斯卡尔重构树+主席树来搞,但是本蒟蒻太菜了并不会,因此只能给大家讲讲离线+splay启发式合并的搞法。 首先,我们考虑把询问离线下来并按限制从小到大排序。然后我们可以考虑把边一条一条插入到图里面去,直到某个询问的限制。这样子,问题就变为了询问某一个连通块的K小值,连通块可以合并。 这个问题就肥肠简单了,我们可以用各种各样的数据结构来处理,线段树合并,splay启发式合并都可以。 考虑到每个点期望加入$logn$次,时间复杂度为$O(nlogn)$ Code…

2019年3月7日 0条评论 817点热度 0人点赞 GoldenPotato137 阅读全文
splay

[Luogu P4178]Tree

题面 传送门:洛谷 Solution 首先,长成这样的题目一定是淀粉质跑不掉了。 考虑到我们不知道K的大小,我们可以开一个splay来统计比某个数小的数的数量。 不会点分治的戳我 Code #include<iostream> #include<vector> #include<cstdio> using namespace std; long long read() { long long x=0,f=1; char c=getchar(); while(!isdigit(c)…

2019年2月25日 0条评论 656点热度 0人点赞 GoldenPotato137 阅读全文

GoldenPotato137

LLer/ACMer/HITer/数院菜鸡/ECS折磨中

最近评论
hilaolu 发布于 1 年前(03月16日) 球球屑gp翻我展示一下ua屑屑
Guava 发布于 2 年前(11月30日) @GoldenPotato137 暂时是 guavaoj.tk
碱式碳酸希 发布于 2 年前(11月30日) 可以先不要告诉老师们吗(偷偷搞的
碱式碳酸希 发布于 2 年前(11月04日) %%%%Tql 请求搬运至NNEZ校内OJ公告中。 展示链接: 请在启天楼内网中访问! :razz:...
630分苦苦挣扎的菜鸡土豆 发布于 2 年前(05月01日) 肥肠抱歉,刚刚看见呢。 那个发送留言不能立刻看见源于我站挂了个腾讯云cdn,默认会返缓存的内容qwq...
分类
  • CDQ分治
  • DAG DP
  • DP+DP
  • FFT/NTT
  • Kruskal重构树
  • LCT
  • LUCAS
  • NNEZ
  • set
  • splay
  • 主席树
  • 二分/二分答案
  • 位运算
  • 倍增
  • 其他
  • 分块
  • 动态规划
  • 卷积
  • 反演
  • 同余
  • 后缀数组
  • 后缀自动机
  • 哈希
  • 图论
  • 圆方树
  • 堆
  • 多项式
  • 字符串
  • 学习笔记
  • 容斥
  • 容斥
  • 左偏树
  • 并查集
  • 数位DP
  • 数学
  • 数据结构
  • 整体二分
  • 斯特林数
  • 最小割
  • 最短路径
  • 未分类
  • 树套树
  • 树形DP
  • 模拟
  • 深度学习
  • 游记/自闭记/滚粗记
  • 点分治
  • 状压DP
  • 生涯纪录
  • 线段树
  • 组合数学
  • 缩点/强连通分量
  • 网格DP
  • 网络最大流
  • 网络流
  • 背包DP
  • 虚树
  • 贪心
  • 边双/点双
归档
  • 2022年1月
  • 2021年9月
  • 2021年3月
  • 2021年2月
  • 2019年11月
  • 2019年4月
  • 2019年3月
  • 2019年2月

COPYRIGHT © 2022 GoldenPotato137的小屋. ALL RIGHTS RESERVED.

Theme Kratos Made By Seaton Jiang

桂ICP备20002051号