ACM--线段树
关注
分享
扫一扫
animalcoder
NULL
展开
-
洛谷P2221 线段树+概率
考虑每条路做的贡献，比左端点小的端点数*比右端点大的端点数推一下柿子就发现要在线段树上分别维护 vi, i*vi, i*i*vi的区间和，好久没写了QAQ考虑区间加操作对区间和的影响，在pushdown,update里加上影响#include<bits/stdc++.h>#define lll long long#define l o<<1#define...原创 2019-08-13 17:05:09 · 306 阅读 · 0 评论 -
hdu5692 线段树+DFS序
题意：中文题思路：维护DFS序，得到点i的时间戳le[i]，跟子树最大时间戳re[i]，由于DFS序le[i]跟re[i]必定连续线段树维护每个点到根节点的路径最大值，叶子节点代表路径的值修改就是修改le[i]~re[i]的值，查询就是查询最大值WA点：long long， 线段树更新了，但是点值忘记更新了，线段树数组开小，inf开太小2286ms#include<iostream>...原创 2018-04-20 01:18:36 · 186 阅读 · 0 评论 -
hdu4027 线段树啦啦啦
题意：查询：【l,r】数列的和修改：【l,r】ai->向下取整sqrt(ai)思路：修改：暴力更新到叶子剪枝：只要区间内所有数都是1就不用向下更新了即sum==r-l+1或者维护区间最大值来判断也可以难度0.6733ms//hdu4027 区间修改：区间内所有数开根号下取整，区间查询：加法和//思路：维护sum 暴力修改叶子，回溯时pushup修改其他非叶子节点，//剪枝：修改时若当前...原创 2018-02-25 23:11:26 · 240 阅读 · 0 评论 -
POJ3264 线段树
题意：查询：【l,r】最大值与最小值的差思路：搞查询：维护区间最大值，最小值难度：0.42219ms//2219ms POJ3264 区间查询2e5 最大最小值的差 分别维护最大值，最小值即可 #include<iostream>#include<stdio.h>#include<string.h>using namespace std;cons...原创 2018-02-25 23:05:10 · 257 阅读 · 0 评论 -
ZOJ1610 线段树染色
题意：8001个点【0,8000】，颜色【0,8000】修改：将点【l,r】之间的段染色为c最后一次查询：对每种颜色i 输出 出现连续颜色i的段数（没有颜色i的段就不用输出）跟poj2528异曲同工思路：不要维护点。。维护段。。【0,1】看成第一段【1,2】看成第二段，以此类推修改：区间维护col：区间颜色（区间内多于一种颜色，col为-1）查询： 暴力查询到叶子，tem【i】表示第i段是什么颜...原创 2018-02-25 23:01:02 · 372 阅读 · 0 评论 -
poj2528 线段树染色+离散化
题意：共n段，俩操作修改：第i段【li，ri】染成颜色i仅最后一次查询：最后的颜色数li ri<=1e7 n<=1e4思路：POJ2777 颜色数只有30 维护颜色状态S就能A这题颜色数那么多。。怎么办？修改：维护颜色替换标记col：区间颜色（多个颜色则col为0），满足区间加法显然叶子col不为0为什么维护这个呢，我的理解是：如果没有col那么就需要暴力查询，修改到每个叶子。修改复...原创 2018-02-25 22:21:22 · 238 阅读 · 0 评论 -
POJ3468 线段树 数据较严
题意：查询：【l,r】数列的和修改：【l,r】数列的值+=c思路：查询：维护区间加法和sum修改：维护修改叠加标记lazy注意：llC++ 1750ms G++2650ms难度：0.6#include<stdio.h>#include<math.h>#include<iostream>using namespace std;#define ll long...原创 2018-02-25 21:13:37 · 230 阅读 · 0 评论 -
Codeforces 920F 线段树
题意：查询：区间查询【l,r】数列的和修改：区间修改【l,r】ai->d(ai)d(x)是x的因子个数 比如d(6)=4 (1,2,3,6四个)思路：查询：维护区间数列和sum，满足区间合并修改：尝试暴力修改到叶子+剪枝发现x多次d(x)是会收敛的d（2）=2，d（1）=1所以当区间内的值都是<=2的话我们就不用向下继续更新了那怎么知道区间的值都<=2呢。。维护区间最大值即可d(...原创 2018-02-25 21:06:31 · 321 阅读 · 0 评论 -
BZOJ1012 线段树插入？？？
题意：维护一个数列，俩种操作，2e5Q查询：末尾开始，数L个数，问最大的数A插入：末尾插入值(n+t)%D，t为上次查询的结果，最开始t=0思路：学习大佬的思路查询：维护区间最大值插入：这种是尾插入，每次插入都暴力build到叶子,并向上更新（logn）注意：线段树一般来说是不支持插入删除的，想想都觉得蛋疼920ms思维难度：0.7 实现难度：0.4#include<stdio.h>...原创 2018-02-25 20:49:54 · 557 阅读 · 0 评论 -
POJ2777 线段树染色
题意：初始颜色均为1，俩操作修改：将【l,r】染为颜色Z查询：【l,r】的不同颜色数1e5个点，1e5个操作，30种颜色思路：查询：如果查询维护区间颜色数，不满足区间加法颜色数较少，维护区间颜色状态S (val)pushup：当前子树S=左子树S | 右子树S修改：维护颜色替换标记lazy注意pushdown跟update中的对lazy跟val的写法难度：0.8391ms#include<...原创 2018-02-25 20:33:17 · 309 阅读 · 0 评论 -
hdu 1556 线段树
题意：N个气球涂色：将【l,r】涂一次颜色查询：最后输出每个气球被涂了多少次色思路：查询：区间维护加法和，查询到叶子修改：维护可叠加标记lazy，每次区间内气球的次数+=1难度：0.61263ms#include<stdio.h>#include<math.h>#include<iostream>using namespace std;const in...原创 2018-02-25 14:00:04 · 213 阅读 · 0 评论 -
hdu1166 线段树单点更新区间查询
题意：单点修改：人数+= c区间查询：【l,r】人数和思路：单点暴力修改到叶子区间信息：维护加法和难度：0.5866ms#include<stdio.h>#include<math.h>#include<iostream>using namespace std;const int inf=0x3f3f3f;struct Stree{ int va...原创 2018-02-25 13:52:07 · 181 阅读 · 0 评论 -
hdu1698 线段树
题意：初始钩子为1区间修改：【l,r】钩子数都改为Z最后仅一次查询：钩子总数思路：查询：维护区间加法和sum修改：维护替换标记lazy难度：0.6 1014ms#include<stdio.h>#include<math.h>#include<iostream>using namespace std;const int inf=0x3f3f3f;st...原创 2018-02-25 13:44:48 · 158 阅读 · 0 评论 -
hdu1754 线段树
难度：0.5题意：区间查询：l,r最大值区间修改：单点修改下标A的值为B思路：区间信息：维护区间最大值区间修改：单点暴力修改到叶子AC:1074ms#include<stdio.h>#include<math.h>#include<iostream>using namespace std;const int inf=0x3f3f3f;struct St...原创 2018-02-25 13:37:43 · 191 阅读 · 0 评论