POJ 1330 Nearest Common Ancestors ST表LCA

BZOJ 3173: [Tjoi2013]最长上升子序列 splay dp 思维题

我们发现他按照从小到大插入,如果我插入一个值,那可能会影响非常多的上升子序列。但是如果我们反着来,每次删除一个最大的,我们只影响以他为结尾的子序列,相对而言就容易处理多了。所以我们先用平衡树,求出最终序列。

然后我们考虑常规的nlogn最长上升子序列做法,我们可以边做dp,边维护出,保持一个长[……]

Read more

OI康复训练 BZOJ2957 楼房重建

很有意思的一道题,看完题解还想了一小会才明白,不过代码很好写。

我们考虑一下,我们可以只看每栋楼的关于原点的斜率,只要一栋楼,其左侧没有斜率大于等于他的楼,那么他就是可见的。

我们考虑线段树,我们每个点维护两个量,ans代表只看这片区域最多可看见的楼的数量(是忽略这篇区域左侧对其影响的)[……]

Read more

OI康复训练 BZOJ1858: [Scoi2010]序列操作

开始一看,这不是线段树模板题么。然后,就掉坑里了。太久不敲线段树了,处理lzy标记的时候,没处理好下放的lzy和子树原有lzy的关系,然后WA了好久。

//代码写得好长啊,感觉太久不写了,写得蛮冗杂的

Noi模拟 市场 线段树

考场上想到了以前写的这道题 :http://oi.self-jqe.win/?p=787

觉得开根号,除法之类的越整,序列越相似,那种不能批处理就暴力,能批量处理就批量处理的算法复杂度都有保证,看数据范围10^5发现貌似比正常的10^6的小一些,觉得很有可能就是这种做法,然后就写了。

具[……]

Read more

bzoj 3207: 花神的嘲讽计划Ⅰ 主席树

我们对于每个k长度的字符串求hash,然后用主席书区间查询是否存在即可。第一次写不离散化的主席树QwQ。调了好久,,QwQ。

bzoj 4690: Never Wait for Weights 带权并查集

好久不写,相对关系又维护的一团糟。。QwQ。。。还是我太菜了。

不过这题倒是真真切切的裸题

bzoj 4653: [Noi2016]区间 线段树

开始我只考虑到了,我们最后选的线段在在坐标上应该有些连续性。在考虑能不能单调搞一下,但是发现处理起来十分困难。后来想想我们选的边在边权上也有一些性质,我们只管两头,中间多选就多选,够了就行。

这样子我们离散化以下,维护一个线段树。然后把区间按边权排序,每次我们都不断加入边,直到有一个点重复过m[……]

Read more