莱士新闻网

这个东西几天前就整完了，今天整理一下思路。 首先这里讨论的是可持久化权值线段树。可持久化的普通线段树我不会写，但是我猜思想应该是相同的。通过将新版本上没有修改的节点接回上一个版本来实现最大限度的重用数据。 区间第k大用可持久化权值线段树的做法如下： 将n个值按照顺序逐个插入树中，产生n个... 阅读全文...

两个字符串间的最长连续公共子串是后缀数组能解决的经典问题之一。其方法为将两个子串连接，中间用一个没有出现过的字符间隔，之后求这个新字符串的SA数组和height数组，对于每个有效的height值，我们判断它对应的两个后缀的开始位置是否属于两个不同的初始串，是的话，用这个height来更新结果。... 阅读全文...

http://www.cnblogs.com/staginner/archive/2012/02/02/2335600.html... 阅读全文...

我感觉我彻底理解后缀数组是无望了。不过只要牢记几个定义，背板就不是那么难了。 sa[i] 表示所有后缀排序后排在第i个的后缀的起始位置是几。 rank[i] 是sa[i]的逆映射 板子里的x[i]在最后swap之前表示的是起始位置为i，长度为j的串的rank是几 y[i] 表示的是第二关键字... 阅读全文...

准备订文化衫啦。仪式的成分更多一些呢。为了统计尺码，我重新部署了以前自己写的Ez InfoCollector，竟然还可以用。因为是私下里收集信息，所以不贴演示界面了。项目我同时托管在了我的github和coding上，欢迎fork... 阅读全文...

得从大上个po开始说。我不是根据矩形周长的AC代码了解了扫描线的思想么，然后我就开始根据矩形并周长的做法来yy矩形面积并的做法。事实上，我第一次yy出来的代码已经是正确的能够AC的了，然而因为http://wallacenews.tk/2016/05/01/囧/上所提到的原因，我没有AC。于是... 阅读全文...

一开始自己yy出了一份代码，调了好久都是WA。后来照着AC代码写了一份，本地过，交上去，WA。又调了好久，后来贴了两份标程上去，WA！ mdzz！ 后来发现是poj的锅，把提交语言从g++改成c++就过了。 完全不清楚原因啊！！、 完了，一开始yy出来的代码我没stage过，根本不知道自己yy... 阅读全文...

今年省选有道题是圆面积的异或并，是扫描线的经典问题。徐人权的大纲上有太多东西我都不会，我恰好又翻到了扫描线，于是决定研究一下扫描线。目前为止我只做了一道扫描线的题，是POJ 1177，也是IOI 98的试题，Picture，学习的还不深，在此记录一些心得。 先将平面上的元素按照一个固定的方向... 阅读全文...

今天有一发提交莫名其妙的MLE了，题目内存上限10M，不过根据计算我的内存应该只消耗1M多一点。像下图一样处理，问题解决woc！！、我以前一直都不加括号的啊，这么长时间没有因为这件事情爆零（说不定有）真是奇迹、、、... 阅读全文...

tag中存储的是左右子树中stree的待加的单位值，也就是说当一个节点他的祖先tag全为0时，我们保证它的stree值是准确的。 除此之外pushdown/update的时机需要注意，一个是在query/edit中对左右子树递归之前进行pushdown，另一个是add区间左右子树都递归的add... 阅读全文...