蒟蒟独行

线段树

01分数规划(1) AC自动机(2) bbp(1) cf(8) dp(35) FFT(4) fleury(1) floyd(1) k-d树(1) kmp(1) kruskal重构树(1) lca(4) main(1) manacher(2) markdown(1) st表(1) trie(1) 一中(4) 主席树(1) 二分(2) 前缀和(1) 单调队列(1) 博弈论(3) 卡常(1) 双联通分量(5) 图论(1) 左偏树(1) 并查集(1) 强联通(2) 思维(11) 感想(6) 扫描线(1) 找规律(1) 技巧(1) 拓扑排序(2) 搜索(7) 数位dp(3) 数学(25) 斜率优化dp(1) 暴力(1) 最小树形图(1) 最短路(2) 未归档(1) 杂(15) 树(5) 树套树(2) 树形dp(4) 树状数组(5) 概率dp(1) 模拟(14) 模拟赛(2) 模板(30) 欧拉函数(1) 点分治(1) 状压dp(1) 生成树计数(1) 离散化(1) 算法复习(14) 线段树合并(1) 网络流(2) 置换群(1) 虚树(1) 计算几何(1) 贪心(12) 轮廓线dp(1) 高斯消元(1) 高精度(2)

/ 注册

全部文章 / 线段树（共20篇）

POJ1177 Picture

题目思路题意：给n个矩形，求它们重叠后的周长题解：用线段树的扫描线从下到上扫一遍，与面积并思想有些相似，下面重边的处理相似，但是周长的并需要求的是竖边的个数然后乘以高度，而面积并求的是底边的长乘以高度，这里我们用了区间合并时的l和r 结构体kk中，l表示当前节点区间左侧是否有竖边...

2020-01-21

0 736

bzoj1798: [Ahoi2009]Seq 维护序列seq

题目题解：与普通线段树基本相同，要注意的是乘的运算级别比加高，所以在做加法是不用管乘法，在做乘法时要管加法标程： #include<bits/stdc++.h> using namespace std; #define update tr[t].su=tr[t<<...

2020-01-21

0 431

洛谷P3957 跳房子

普及组的题。。。我不会。。。题目题解：思路很简单，就是二分答案+dp+单调队列（线段树也可以），但是要注意细节，一个细节错了，一半分数就没了。引用洛谷上某大佬的一段话：发现答案的可行区间是单调的，所以二分答案，容易推出f[i]表示到达第i个格子的最大值，枚举上一步跳了多...

2020-01-21

0 341

洛谷P3953 逛公园

题目 #题解： f[u][k] 表示 dis(u,n)<=MinDis(u,n)+k的方案数,答案就是 f[1][K] f[u][k]=∑f[v][k−MinDis(v,n)+MinDis(u,n)-w] 这样怎么判 0环呢?只要在搜索的时候记录个 instack 就 ok 了如果当前的 v...

2020-01-21

0 419

洛谷P3960 列队

题目题解：我们发现其实就是维护n+1个序列，支持查找和删除第x个元素，以及在最后添加元素前n个序列维护每一行的前m-1个元素，最后一个序列维护最后一列的元素但是这样的话需要建n+1颗线段树，无法承受但是可以发现一开始线段树中的元素是满的，并且一开始的元素编号十分有规律，可以...

2020-01-21

0 339

线段树

题目博客 PKU1177 Picture hdu3954 level up hdu4027 can you answer these queries? hdu3333 turing tree hdu3016 man down hdu3340 rain ...

2020-01-21

0 635

洛谷P3384 【模板】树链剖分

题目题解 #include<bits/stdc++.h> using namespace std; const int N=100002; #define up(t) tr[t]=(tr[t<<1]+tr[t<<1|1])%M; #define mid ((...

2020-01-21

0 362

bzoj1067: [SCOI2007]降雨量

题目题解：因为每个点都对应年份和降雨量，我就用i，j代表年份，i值，j值代表这年的降雨量四种情况：（1）i，j均未知：输出可能；（2）i知，j未知：因为j值最大可以和i值相等，所以如果i到j之间有大于i值的需输出错，否则输出可能；（3）i未知，j知：如果i到j之间有大于j值的...

2020-01-21

0 654

洛谷P1983 车站分级

这题有三种做法 1.O(nm2) 1. O ( n m 2 ...

2020-01-21

0 417

bzoj1018: [SHOI2008]堵塞的交通traffic

题目题解 Solution 一道用线段树维护连通性的题。第一做这种题，其实这类问题我们需要维护一下区间内的联通关系，再用我们维护的这些关系去查询。对于这道题，我觉得可以有两种建树的方法： ①：以每一列为一个叶子节点。 ②：以每一个区间（就是每1条横向道路连接的左右两个节点）...

2020-01-21

0 377