GoldenPotato137的小屋

分块
主席树

[BZOJ 3744] Gty的妹子序列

题面 3744: Gty的妹子序列 Solution 这是一道分块妙题。 区间逆序对......log数据结构应该是没法搞的。 因此,我们考虑用分块解决这个问题。 设$f[i][j]$表示第$i$块与第$j$块的所有元素的逆序对个数 这个东西我们可以考虑用线段树/树状数组直接搞,我们把所有数字从大到小插入,(数字相同的时候一起插入),每插入一种数字,我们可以直接计算它到其他所有块会新产生的逆序对数:即那个块的大小-已经填好的数字的个数。 上面的东西可以$O(n\cdot \sqrt n \cdot logn)$预处…

2019年3月20日 0条评论 553点热度 0人点赞 GoldenPotato137 阅读全文
分块

[BZOJ 4320] ShangHai2006 Homework

题面 4320: ShangHai2006 Homework Solution 这是一道分块妙题。 首先,我们发现这题是对一个比较大的任意模数取模,那我们传统的log数据结构可能还真没法下手。 既然如此,我们考虑分块。 我们把原题中的询问分为两类: 1. $p>=\sqrt{300000}$ 2. $p<\sqrt{300000}$ 对于第二种情况,我们可以开一个桶$f[x]$表示目前为止所有数字%$x$后取得的最小值。这个东西我们在插入数字的时候暴力更新一下即可。 对于第一种情况,事情有点复杂,我们这样做:…

2019年3月19日 0条评论 729点热度 0人点赞 GoldenPotato137 阅读全文
分块

[Luogu P3645] [APIO2015]雅加达的摩天楼

题面 P3645 [APIO2015]雅加达的摩天楼 Solution 与其说这题是分块妙题,我更倾向于把这题称为分层图妙题。 这题有一个一眼贪心做法:对于每只doge,我们都暴力地去建它连向它能跳到的点的边,边权为跳的次数。然后直接求一遍单元最短路即可。 很显然,这玩意的边的数量是$O(n^2)$的,求一遍最短路的复杂度达到了惊人的$n^2logn^2$ 这显然是要T飞的,但是我们会从中发现一个问题:既然一个doge的跳跃是多步的,那我们能否直接把几步拆开来,然后省略重复的边? 例如: 优化为: 这样做看起来很星…

2019年3月19日 0条评论 657点热度 1人点赞 GoldenPotato137 阅读全文
分块

[Luogu P3247] [HNOI2016]最小公倍数

题面 P3247 [HNOI2016]最小公倍数 Solution 这是一道妙题。 首先,根据常识,题面要我们求的是找一条从s,t的路径,使得路径上$max\ a=a,max\ b=b$。 这咋求呢?我们会发现,我们要求的路径本质上是一个连通块,连通块可以考虑用并查集处理。 接下来考虑对a分块,先把所有的边按照$a$来排序,再分块,每个块里连的所有边保证$<=a_{[size*x]}$,如下图所示: 接下来,我们考虑把所有询问按照b从小到大排序去一个个计算,每计算一个询问之前,把$b<=q[i].b$的…

2019年3月19日 0条评论 552点热度 1人点赞 GoldenPotato137 阅读全文
分块

[Luogu P4168] [Violet]蒲公英

题面 洛咕 Solution 题目要求求出区间众数,强制在线。 区间众数是一个比较尴尬的问题,我们无法用区间数据结构来处理这个问题,因为我们没法很好的合并区间众数的答案。 既然区间数据结构解决不了这个问题,我们可以考虑一下使用基于分块的算法,例如莫队。 这题用莫队非常好处理,不幸的是,这题要求强制在线。 因此我们考虑使用分块算法。 分块算法的核心在于把一整个块的信息压缩起来以便快速处理。 我们要查询一段区间的众数,我们可以考虑这样搞:对于这个区间内连续的块,我们先快速地查询这个连续的块中的众数,然后我们暴力处理这个…

2019年3月5日 0条评论 618点热度 0人点赞 GoldenPotato137 阅读全文

GoldenPotato137

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

最近评论
hilaolu 发布于 1 年前(03月16日) 球球屑gp翻我展示一下ua屑屑
Guava 发布于 1 年前(11月30日) @GoldenPotato137 暂时是 guavaoj.tk
碱式碳酸希 发布于 1 年前(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号