冷滟泽的个人博客

2019-10-12 lengyanze 阅读(46) 评论(0)

dream 题意 给定一个长度在 10^9 内的序列，要求维护 3 种操作： 区间加 区间翻转 区间求和 强制在线。 思路 这三个操作明显对应平衡树（Splay/Treap）。考虑到序列的长度，需要动态开点。 代...

2019-10-10 lengyanze 阅读(29) 评论(0)

Candies 算法1（10%） 依据题意，暴力模拟即可。复杂度 O(NK) 。 算法2（30%） 观察到 算法1 的瓶颈在于寻找最大值和最小值。使用 STL set 维护这一过程可以将其优化到 O(logN) 。总...

2019-10-05 lengyanze 阅读(37) 评论(0)

题目链接 Codeforces Luogu 题意 给定两个字符串s、t，求s的非空前缀后接上t的非空前缀形成的本质不同字符串种类数 思路 神仙思维题。 设一组本质相同的答案串为 AB ，且 A, B 分别为 s,...

2019-09-27 lengyanze 阅读(28) 评论(0)

思路 写个不太一样的，二分答案的题解。 考虑二分 k 。为了验证当前答案的可行性，先预处理出矩阵 c[i][j] 表示第 i 行与第 j 行间差的绝对值的最大值是否大于等于 k 。这个可以 O(n^2m) 做到。然后...

2019-09-23 lengyanze 阅读(28) 评论(0)

题目链接 Tree 题解 考虑树的欧拉序（即长度为 2N-1 的 DFS 序），用线段树维护每个点到根的距离，则修改边权的操作可以转化为区间加法。设树上有两点 u,v ，它们的欧拉序分别为 a,b ，那么这两点的最近...