hackerchef - 博客园

2025年1月

洛谷题单指南-线段树的进阶用法-P4093 [HEOI2016/TJOI2016] 序列

摘要：原题链接：https://www.luogu.com.cn/problem/P4093 题意解读：一个序列，m个变化，求任意一个变化后不受影响的最长上升子序列长度。解题思路：设原序列为a[N]，原序列经过变化后能得到的最大值序列为maxa[N]，最小值序列为mina[N] 设f[i]表示以第i个阅读全文

posted @ 2025-01-07 17:23 hackerchef 阅读(80) 评论(0) 推荐(0)

洛谷题单指南-线段树的进阶用法-P3810 【模板】三维偏序（陌上花开）

摘要：原题链接：https://www.luogu.com.cn/problem/P3810 题意解读：题意很明显，有n组三元组，对于f(i)，表示j!=i的情况下，所有的aj<=ai,bj<=bi,cj<=ci，这样的j的数量。求f(i)=0,1,2...n-1的i的个数。解题思路：先将三元组按a排阅读全文

posted @ 2025-01-06 11:08 hackerchef 阅读(144) 评论(0) 推荐(0)

洛谷题单指南-线段树的进阶用法-P3380 【模板】树套树

摘要：原题链接：https://www.luogu.com.cn/problem/P3380 题意解读：对于序列，实现5个操作：1.查询区间[l,r]范围数值k的排名 2.查询区间[l,r]范围第k小值 3.单点修改某一个位置的值 4.查询区间[l,r]范围数值k的前驱 5.查询区间[l,r]范围数值k的阅读全文

posted @ 2025-01-03 16:18 hackerchef 阅读(166) 评论(0) 推荐(0)

2024年12月

洛谷题单指南-线段树的进阶用法-P4587 [FJOI2016] 神秘数

摘要：原题链接：https://www.luogu.com.cn/problem/P4587 题意解读：对于序列a[n]，查询m个区间[l,r]数值对应集合的神秘数。集合 S 的神秘数定义为最小的不能被 S 的子集的和表示的正整数。解题思路：对于区间[l,r]，从小到大将数值选入集合，来观察神秘数的变阅读全文

posted @ 2024-12-30 14:01 hackerchef 阅读(101) 评论(0) 推荐(0)

洛谷题单指南-线段树的进阶用法-P3834 【模板】可持久化线段树 2

摘要：原题链接：https://www.luogu.com.cn/problem/P3834 题意解读：静态区间第k小问题，可持久化线段树（也称为主席树）模版题。解题思路：一、朴素想法：如何求完整区间[1,n]第k小 1、权值线段树设n个数构成序列a，b数组代表a中元素出现的次数，即b数组的构建方式阅读全文

posted @ 2024-12-26 18:35 hackerchef 阅读(164) 评论(0) 推荐(0)

洛谷题单指南-线段树-Points

摘要：原题链接：https://www.luogu.com.cn/problem/CF19D 题意解读：坐标系支持几种操作：1.添加一个点(x,y)，保证不会重复 2.删除一个点(x,y) 3.查询刚好比一个点(x,y)的x，y都大的点，优先看刚好比x大的位置，如果该位置有多个点，取y最小的一个，找到则输阅读全文

posted @ 2024-12-19 19:20 hackerchef 阅读(137) 评论(0) 推荐(0)

洛谷题单指南-线段树-P2572 [SCOI2010] 序列操作

摘要：原题链接：https://www.luogu.com.cn/problem/P2572 题意解读：对于01序列，支持几种操作：0.将区间值全变成0 1.将区间值全变成1 2.将区间值全部取反 3.查询1的个数 4.查找连续最多1的个数解题思路：区间修改，区间查询，又是线段树的典型应用。要查询的值阅读全文

posted @ 2024-12-13 10:56 hackerchef 阅读(126) 评论(0) 推荐(0)

洛谷题单指南-线段树-P4145 上帝造题的七分钟 2 / 花神游历各国

摘要：原题链接：https://www.luogu.com.cn/problem/P4145 题意解读：对于序列a[n]，支持两种操作：1.对区间[l,r]内每个数开方 2.查询区间[l,r]每个数的和解题思路：区间修改，区间查询，可以用线段树解决。咋一看，需要借助于懒标记来修改节点，但仔细分析，开方阅读全文

posted @ 2024-12-12 14:30 hackerchef 阅读(116) 评论(0) 推荐(0)

洛谷题单指南-线段树-P5522 [yLOI2019] 棠梨煎雪

摘要：原题链接：https://www.luogu.com.cn/problem/P5522 题意解读：有若干0/1/?组成的字符串，支持两种操作：1.将指定位置字符串修改成新字符串；2.查询区间内字符串能否统一成一个字符串，求有多少种可能；将2的所有结果异或起来，再和0异或，输出最终答案。注意：?表示可阅读全文

posted @ 2024-12-11 09:05 hackerchef 阅读(104) 评论(0) 推荐(0)

洛谷题单指南-线段树-P1558 色板游戏

摘要：原题链接：https://www.luogu.com.cn/problem/P1558 题意解读：给定序列a[n]，初始都为1，支持两种操作：1.将区间[a,b]所有值都改为c；2.查询区间[a,b]范围有多少个不同的数；输出所有操作2的结果。解题思路：又是线段树的典型应用，要支持区间修改，需要用阅读全文

posted @ 2024-12-09 10:51 hackerchef 阅读(148) 评论(0) 推荐(0)

公告