GoldenPotato137的小屋

整体二分
数据结构

[Luogu P2617] Dynamic Rankings

题面 P2617 Dynamic Rankings Solution 这题需要一个比较妙的操作。 首先,我们阅读题面,发现题目要求我们处理区间K大带单点修改的问题。我们考虑用整体二分来解决这个问题。 总所周知,整体二分中的修改只能以“添加”的形式进行,而不能以“覆盖”的方式进行。但这里,我们修改一个位置的数之后,新的数会把原来的数覆盖掉。如果我们不能处理好这个问题,整体二分一定会错。 因此,我们考虑添加一个“删除”操作来解决这个问题。我们可以把这里的修改变为:删除原有的数+加入一个新的数。这样子,我们就把原来的“覆…

2019年4月7日 0条评论 637点热度 0人点赞 GoldenPotato137 阅读全文
数据结构

[Luogu P3332][ZJOI2013]K大数查询

题面 P3332 [ZJOI2013]K大数查询 Solution 这是一道不辣么模板的整体二分题。 首先,我们先来假设一下只有一个询问应该怎么搞。 考虑这样做:我们先二分一个答案,修改中,如果所要修改的数大于mid,则在这段区间中每个数加上1。否则什么都不做。这样一来,最后我们只需要看一下询问的区间的区间和是否大于$K$即可。 接下来,我们考虑如何把所有询问一起来二分。 同样还是二分一个答案,把所有答案大于mid的询问丢到右边,其余丢到左边即可。 接下来,我们可以显然发现对于右边的区间,所有修改$<=mid…

2019年3月27日 0条评论 798点热度 0人点赞 GoldenPotato137 阅读全文
数据结构

[Luogu P3527] [POI2011]MET-Meteors

题面 P3527 [POI2011]MET-Meteors Solution 我是一直奉行坚决不写树状数组只写线段树理论的,直到这题....... 这题是一道整体二分的模板题。 首先,我们考虑只有一个国家的情况。这不SB问题么 我们可以二分一个答案,然后我们用线段树暴力模拟,暴力Check,复杂度$O(mlogn)$。 显然,如果我们每一个国家都这么搞一轮,复杂度达到了惊人的$O(n\cdot m logn)$,这显然是要T飞的。 因此,我们就得请出伟大的整体二分了。整体二分,顾名思义,就是把所有询问一起二分答案。…

2019年3月27日 0条评论 522点热度 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号