自主学习类笔记，没有学习价值。
”曾经沧海难为水，除却巫山不是云。“——元稹《离思五首·其四》
——————————————————————————————————————————
休息日排一下要做的题目：
1.5道线段树 3.5h
2.2道树状数组 2.5h
3.简单贪心3道 1.5h
4.简单搜索2道（带剪枝）2h
5.简单搜索1道（A*） 1h
6.简单搜索1道(ID A*) 1h
7.复习凸包，尝试再次理解
8.简单动态规划3道（线性，背包。橙-黄）
9.二分答案两题 2h
感觉是写不完，挑点想写的砸吧砸吧好了。
线段树
线段树1：复习模板 https://www.luogu.com.cn/problem/P3372
容易写错的地方：
1.开 long long
2.四倍空间
3.函数传参位置错误（改了一下get_lzy传入参数的位置从(u,l,val,r)改成了(u,l,r,val)）但是前面写的用get_lzy函数的地方没有改，所以错了（这个错误还挺难调出来的，所以建议一开始就弄好）
小白逛公园
求动态最大子段和喵。
发现不能只维护“当前区间内的最大子段和”，否则就无法汇总到父节点上。
父节点的最大子段和只存在以下三种情况：
1.是左子节点的最大子段和
2.是右子节点的最大子段和
3.是左子节点和右子节点的两段相邻数值拼在一起的和
不难发现左子节点被拼起来的那一段肯定包含左子节点的右端点，反之，右子节点被拼起来的那一段则一定包含右子节点的左端点。
所以我们可以对于每一个节点维护它的最大子段和，左连续和（以左子节点右端点为起点向左找的最大连续和）与右连续和（以右子节点左端点为起点想左找的最大连续和）。（同时，为了维护左连续和与右连续和，我们还需要维护当前节点区间和）
发现对单点修改区间查询的操作不是特别熟悉，所以重新去做一下线段树2
https://www.luogu.com.cn/problem/P3373
哦，再提一下吧：线段树2并不只是单点查询区间修改
它还有两个标记：乘法标记和加法标记（要记得先乘再加喵），而且在打tag的时候，如果打的是乘法标记，要记得把加法标记给乘一下。
唔。其实我一直觉得#define int long long很危险，但是有时又不得不承认它是好用的。
好了，重新回去做小白逛公园。
等一下，突然发现我不会的好像是单点修改单点查询。
?
算了直接写吧。
写代码的时候一直想出去买东西吃，导致产生了一大堆错误，一点点梳理一下.
1.在写合并函数(mer)的时候，我是照着上面的pushup抄的，结果抄错了。
错误代码1:
错误代码2：
正确代码：
也就是说，不是要把两个最大子段和拼起来。（因为最大子段和不一定是连续的）
2.最开始的时候，我不太清楚应该怎么写ask函数。所以我是这样写的：
实际上，这应该是一个求哪个子节点所包含的值更大的倒霉催函数。
事实上，我们应该让ask也返回node，然后按照写pushup的方法全部完成返回值的编写。
接着来写一道简单题。
我记得我应该在我线段树那里写过的，结果当时写炸了。
唔。感觉挺简单。一眼板。
不过有点神秘的是，我第一次写的TLE大爆炸了：
因为我在pushup那边犹豫了一下怎么拼接01数组，而后用了string，超时。
所以要记得不要乱使用STRING，有可能会超时。
后面转念一想，其实我们根本不用维护包含节点数大于等于二的节点（也就是说可以直接把pushup去掉，所以就新弄了一份代码）
最后一个线段树题目！
权值线段树。
对一个数列a构造一个数列b，其中b[i]表示a中数值i出现过的次数，这样的数列b称为a的权值数列。对b构造的线段树称为数列a的权值线段树。
权值线段树在很多计数问题中有着重要的应用，因为它可以轻松地修改对a维护的统计信息。容易发现，当将a[i]从x修改为y时，只需要对其权值线段树做两次单点修改，即给b[x]间1，给b[y]加上1.
（由于大部分的a会很大，所以需要使用离散化）
除了一堆问题，我先放下代码，然后逐一分析问题所在：
1.还是会忘记要把N*4
前面很好奇为什么一共只有线段树一共只有n * 2个节点，但是要开N *4的空间，这是因为：
2.懒标记的作用
懒标记存在的意义是区间修改时暂时不去修改下面的子节点，只是放置一个标记，等到查询或者再次打表记时再下放。
但是注意：这是只争对区间的，如果你只是想要修改单点，是不需要懒标记的
3.逆序对开long long
其实我经常会漏掉哪里要开long long，遂偷懒写define int long long
但是这样是不对的（define int long long 是有很大概率出错的）
所以如果你要用long long answer，你需要记得把返沪结果的ask函数也开成long long
4.我发现当我用离散化，我还是会搞混数组。所以可以多做一点离散化的题目。
树状数组
注意到现在已经15:38。
注意到我完全忘记了树状数组。
我去。
那就重新做一下树状数组的模板好了，然后再弄一道别的什么玩耍一下。
树状数组是线段树的平替，经典的操作只有两个：1.单点修改 2.区间查询
其精髓在于，它不会直接去存储原数组，而是用一个辅助数组去存储一小段区间和（这一小段的区间和取决于iii的二进制的最后一个一在哪个位置，即lowbit函数）
(碎碎念：树状数组真的比线段树好写很多)
https://www.luogu.com.cn/problem/P5677
配对统计
感觉有点太难了，换一道简单点的题吧，我们要循序渐进！
https://www.luogu.com.cn/problem/P5459
回转寿司
唔。这道题目的大概意思是：寻找一个序列中>=l且<=r的连续子段和的数目
注意到，树状数组的单次查询时间复杂度是O(nlogn)O(nlogn)O(nlogn)
想十五分钟。欧克来讲怎么做。
我一开始先摸了这样一份代码：
但它其实是错的（因为有负数的存在）
然后我去看了树状数组题解。
正解是这样的：
先预处理前缀和，对于每一个区间的右端点pos，找出有多少个pre[i](i≤pos)pre[i] (i\le pos)pre[i](i≤pos)是≤R\le R≤R且大于等于L的，由于pre有可能很大，所以使用离散化。
感觉是个比较基础的做法，但是没想出来。待会儿要不再连一道树状数组？
不过在这之前先玩耍一下代码。
所以，从理论上而言，这是不是算权值树状数组？
果然，女儿像妈妈。
突然发现自己应该补一下二分答案。
等一下，我前面好像写错了，理论上而言，应该是对于每个右端点pos，找出[pre[pos]-r,pre[pos]-l]这个区间内的数字有多少个，推理过程如下：
有点坏菜。感觉状态好差。可不能这样啊。六点钟之前一定得把这题做完了，不然效率太低了。
没做完。七点了。我去。
我重新把这道题目的思路梳理一遍：
题目大意：给定一个数组，统计有多少个连续子段，使得子段和在[l,r]区间之内。
第一步：把子段和转化成前缀和的差（子段和是一个区间的累加值，需要O(n2)O(n^2)O(n2)时间复杂度处理。而前缀和只需要O(n)O(n)O(n)时间复杂度就能处理出来，这是一个常见的思路转变）
第二步：固定右端点，统计合法的左端点（上面放过deepseek的截图，我们用数学处理的方法将其简化成了：查找有多少个值落在了[pre[r]-R,pre[r]-L]）
其实我们想要统计的是：L<=pre[r]-pre[x-1]<=R
这个时候引入关键的一点：从上面的分析中，我们可以看出，我们需要在树状数组中加入这些值：1.pre[1]-pre[n]
2.pre[i]-L pre[i]-R
3.pre[0]（由于是pre[x-1]，x从1开始，所以x-1=0，得放进去）
感觉还是不够懂，我先放置一下代码，过几天再来看一遍：
贪心
https://www.luogu.com.cn/problem/P1803
线段覆盖
这是一个相当基础的贪心，我应该做过挺多次了（虽然不知道为什么这个号没有A）
把代码放一下，然后重新讲一讲吧。
算了。这里内容太多，打字已经开始卡顿，我就不把内容放在这里了。
