苟且的狮子的博客

极差

线段树线段树是我的弱项我们来看这一题：要维护值得乘积对 abc如果a发生变化，那么我们要是知道b*c则只要加上a得增量就好了基于着中国想法，我们使用了线段树。我们一共开了7棵线段树！先开三棵a,b,c在我们的线段树所开的数组中记录的点seg[x]是，从点x到目前边界的极差线段树维护这个极差的...

Neat Tree

单调栈单调栈接触挺久了，一直没有仔细研究。昨天模拟赛，一道单调栈没有看出来。现在认真学学！对于这道题，因为它是连续子序列所以我们可以统计每一个值的贡献即，(作为最大值的次数-作为最小值的次数)*高度如何求作为最大值的次数？我们可以求解，向左走第一个比他大的索引，向右走第一个比他大的索引那么，在...

[HAOI2016]找相同字符

后缀数组、单调栈题意：分析：题意十分的清爽，但是却让人一筹莫仔细地分析我们便会发现，我们可以利用后缀数组来进行求解。我们比对s1和s2的每一个后缀。然后计算其和就可以了。对不对，其实题目中的也就是这个意思而已罢了。很简单，我们可以这样构造一个字符串s1+'$'+s2，我们求其SA和rmq。...