工大最菜
工大最菜
全部文章
分块
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)
归档
标签
去牛客网
登录
/
注册
liweihang的博客
全部文章
/ 分块
(共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
636
分块入门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
543
分块入门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
578
分块算法-区间修改+区间最值
给定一个长度为n数列,现对这个序列有两种操作: U L R X:将区间 [L, R] 每个数加X; Q L R:查询从第L个数到第R个数得最大值和最小值。 所有的数都 <=1000 输入格式: 第一行给定一个整数n, m,表示有n个数。m个操作 以下接着一行,n个数。 再接下来m行每行一个...
2019-07-09
0
914
首页
上一页
1
2
下一页
末页