工大最菜

分块

01规划(3) ACM比赛总结(3) ACM训练日记(11) bfs(7) dfs(5) Dilworth定理(1) dp(80) exgcd(1) gcd(2) java(1) KM(1) kmp(4) map(4) MOD运算(1) os(3) rmq(1) set(2) STL的操作(1) __int128(1) 一般图带花树的最大匹配(2) 三分(2) 中位数(1) 主席树(6) 二分(8) 二分图匹配(9) 二分图最大匹配(1) 二分图的多重匹配(1) 二维偏序(2) 二进制(2) 优先队列(2) 倍增DP(2) 其他(1) 分层图最短路(1) 分治(5) 分组背包(3) 前缀和(6) 动态最短路(1) 区间dp(18) 单调队列(2) 单调队列dp(2) 博弈论(11) 双连通(5) 同余最短路(1) 后缀和(1) 后缀数组(2) 因数(1) 大整数(1) 大模拟(2) 字典树(1) 字符串哈希(16) 完全背包(1) 容斥(1) 尺取(4) 并查集(3) 序列自动机(2) 康托展开(1) 异或(4) 强连通(1) 思维(6) 扩展KMP(3) 扫描线(2) 技巧(11) 拉格朗日插值法(1) 拓扑排序(3) 数位dp(8) 数学推导(2) 数论(18) 整体二分(2) 暴力(6) 最大权闭合子图(1) 最小生成树(5) 最小表示法(1) 最短路(15) 未归档(2) 构造(2) 构造树(1) 染色问题(1) 树(9) 树dfs序(2) 树上分块(2) 树上启发式合并(6) 树上差分(2) 树形dp(16) 树状数组(3) 树的BFS序(1) 树链剖分(6) 概率(24) 模拟退火(6) 欧拉函数(3) 欧拉回路(4) 点分治(5) 状压dp(11) 珂朵莉树(2) 生成函数(4) 矩阵快速幂(3) 矩阵计数(1) 离散数学(1) 离线(1) 线性基(1) 线性规划(1) 线段树(18) 线段树合并(2) 组合数学(1) 组合计数(1) 网络流(14) 莫比乌斯反演(1) 莫队(6) 表达式求值(1) 计数(5) 计算几何(4) 调度问题(1) 贪心(8) 费用流(6) 费用背包(1) 递归(2) 长链剖分(1) 题解(14)

/ 注册

全部文章 / 分块（共11篇）

分块入门9:P4168 区间众数查询O(n*sqrt(n))

题目链接：https://www.luogu.org/problemnew/show/P4168 题目大意：思路一：在线区间众数的分块做法比较多，这里提供一个思路：首先离散化一下比较方便。可以推导出：[L, R]的众数一定是整数块的众数，或者两个边块的数。所以对于每次查询，众...

2019-07-11

0 1833

分块入门8:区间修改为同一值查询区间元素=c的

题目链接：https://loj.ac/problem/6284 题目大意：区间修改没有什么难度，这题难在区间查询比较奇怪，因为权值种类比较多，似乎没有什么好的维护方法。模拟一些数据可以发现，询问后一整段都会被修改，几次询问后数列可能只剩下几段不同的区间了。我们思考这样一个暴力，还是分块...

2019-07-10

0 581

分块入门7:区间乘+加

题目链接：题目大意：很显然，如果只有区间乘法，和分块入门 1 的做法没有本质区别，但要思考如何同时维护两种标记。我们让乘法标记的优先级高于加法（如果反过来的话，新的加法标记无法处理）若当前的一个块乘以m1后加上a1，这时进行一个乘m2的操作，则原来的标记变成m1 * m2，a1 * ...

2019-07-10

0 640

分块入门6: 动态插入+分块重构

题目链接：https://loj.ac/problem/6282 题目大意：先说随机数据的情况之前提到过，如果我们块内用数组以外的数据结构，能够支持其它不一样的操作，比如此题每块内可以放一个动态的数组，每次插入时先找到位置所在的块，再暴力插入，把块内的其它元素直接向后移动一位，当然用链表也是...

2019-07-10

0 0

分块入门5: 区间开方+区间查询和

题目链接：https://loj.ac/problem/6281 思路：这里有一个定理：一个int范围内的数，最多开5次方(向小取整)。那么就是说：一个块在几次操作后很容易全部变成1，这个时候再操作开方，就不用修改了。当然没有变为0的时候只能暴力修改了，复杂度不会太高。 #include&...

2019-07-10

0 516

分块入门4: 区间修改+区间查询和

题目链接：题目大意：直接上代码： #include<bits/stdc++.h> using namespace std; typedef long long LL; //由块号寻找第一个块元素的下标 #define LL(x) ((x-1)*Len+1) const LL m...

2019-07-10

0 544

分块入门3: 区间修改+区间查询小于 c的最大数(set二分)

题目链接：https://loj.ac/problem/6279 题目大意：思路：和上一题不同的是，查询小于c的最大元素，那么只要把整块查询改一改就可以了。当然写了个sb错误，把ans赋最小值为 (1<<32)内存溢出。因为int 下1最多<<31 #include ...

2019-07-10

0 497

分块入门2: 区间修改+区间查询小于 c元素的个数(vector 二分)

题目链接：https://loj.ac/problem/6278 题目大意：询问操作: 不完整的块枚举统计即可；而要在每个整块内寻找小于一个值的元素数，于是我们不得不要求块内元素是有序的，这样就能使用二分法对块内查询，需要预处理时每块做一遍排序，复杂度O(nlogn)，每次查询在√n个块内二分，...

2019-07-10

0 725

分块入门1:区间修改+单点查询

题目链接：https://www.luogu.org/problemnew/show/P3368 题目大意：这题分快很容易T。 /* 给出一个长为n的数列，以及n个操作，操作涉及区间加法，单点查值。 5 5 1 5 4 2 3 1 2 4 2 2 3 1 1 5 -1 1 3 5 7 2 4...

2019-07-10

0 579

分块算法-区间修改+区间最值

给定一个长度为n数列，现对这个序列有两种操作： U L R X：将区间 [L, R] 每个数加X； Q L R：查询从第L个数到第R个数得最大值和最小值。所有的数都 <=1000 输入格式: 第一行给定一个整数n, m，表示有n个数。m个操作以下接着一行，n个数。再接下来m行每行一个...

2019-07-09

0 922