6 月 13 日闲话
如何描写思维，我遇到了我写作生涯中最大的难题。
“人与人之间是无法互相理解的。”小粉兔这样说到。人与人之间最有效率的沟通方式还是面对面的交流；其次是视频、电话聊天；然后是打字沟通；最末是通过文字的。这是按照交流的时效性排序的。但是在学习中，我们更倾向于阅读。先不扯这些有的没的了，来看一下兔队线段树：
单点修改，维护前缀最大值之和。
直接给出方法：
维护这样的信息：仅考虑节点内部的数，答案是多少，设为 $s$。在维护一个区间最大值。
考虑 pushup，左侧可以直接继承答案，对于右侧需要考虑左侧最大值 $p$ 的影响，不妨设此过程为 ${\rm calc}(k,p)$。分类讨论：
- 若 $p\ge mx_{l}$，则左侧所有位置前缀最大值都是 $p$，答案是 $p\times len_{l}+{\rm calc}(r,p)$。
- 否则，则说明 $p$ 对右侧无影响，因此答案是 $s_k-s_l+{\rm calc}(l,p)$。
注意第二步中，$s_k - s_l$ 就是考虑了左边贡献的时候右侧的值，注意这里可不能直接用 $s_r$。
但是，我们真的有必要做这次减法吗。再看看我们的整个过程，我们其实没有用到 $s_l$，只是用它来求出 $s_r$ 罢了。因此我们可以只存考虑左侧的贡献的情况下，右子树的答案。这样的话就不用做减法了。其优势在于对于前缀与、max、min 这样不可减的信息，我们也可以维护了。
struct sgt{
#define ls k<<1
#define rs k<<1|1
#define mid ((l+r)>>1)
int mx[N<<2],s[N<<2];
int ln[N<<2];
int calc(int k,int p){
if(ln[k]==1)return max(mx[k],p);
if(p>mx[ls])return p*ln[ls]+calc(rs,p);
else return s[k]+calc(ls,p);
}
void pshup(int k){
mx[k]=max(mx[ls],mx[rs]);
s[k]=calc(rs,mx[ls]);
}
void build(int k,int l,int r){
ln[k]=r-l+1;
if(l^r)build(ls,l,mid),build(rs,mid+1,r);
}
void chg(int k,int l,int r,int x,int y){
if(l^r){
if(x<=mid)chg(ls,l,mid,x,y);
else chg(rs,mid+1,r,x,y);
pshup(k);
}else mx[k]=y,s[k]=0;
}
}T;写完这一段我才发现，原来我写的和兔写的几乎一模一样。但我在我自己想出这个维护方法之前一直看不懂小粉兔的博客，但现在看起来却觉得很简单。还是阅读能力的缺失阿。或者说，是阅读时没有进行足够的思考。读书、或者说文章时，确实需要一边读，一边动一下笔，否则很容易留在表面，没有真正理解。
但不如来看一些其他有意思的东西，今天模拟赛还是挂分了。边界情况不知道咋回事没写对，挂了 18 分，四舍五入一下需要去跑一圈了。
今天写的闲话感觉和昨天的风格很不一样啊，原因是昨天有人说我写的很“意识流”，但我却感觉自己有点刻意整活了。但是其实想到哪写到哪也是很有意思的，人的思维很有意思，但难以观测，能通过文字观察自己或者别人的思维也是很有意思的。这时候就感觉人类很神奇，可以找到共性，但因为成长过程中的种种因素又形成了个性。对此的观察、或者说见识见识，也有独特的趣味。独特的趣味，这是个很有意思的词。现在的网络模因传播带来了很多共同的趣味，虽然这并没有什么高低之分，但是从自己独特的趣味中，可以获得一丝“与众不同”的感觉，从而带来一些自信。但是与众不同又可能会带来优越感，但不想再写了，话题就此打住。
仍然值得思考蜜蜂的问题。试问：蜜蜂蛰到自己会发生什么呢？我不知道，但是我观察到蜜蜂喜欢出重排和循环置换这种奇怪的变形问题。感觉从繁复的性质中找到突破的点是非常难的。蜜蜂的灵感可能来源于采蜜时寻找有花粉的花朵，但人类可能只能用计算机来发现规律。但很多性质，甚至无法用计算机来发现。例如 palindORme 是如何想到要构建非法序列到合法序列的映射的，我不清楚。我的想法是需要观察到重排的性质，即每次可以选择任意一对可以选择的数塞到两边，然后再考虑删掉也有这样的性质，不断删不断删就一定会剩下固定的一些数。我看到题解中都没有提到对这个构造的思考，我感觉有些失落。尽管脚手架看起来不够美观，但是他是利于后人的。打球去了。
不过请不要忘了操作分块。想说的话其实很多都没有说完，对这些话题有兴趣的可以来联系我聊一聊。