【题解】玄学 (UOJ46) -boshi
【清华集训 2014】玄学 (UOJ46) 题意 给定一个数列,一个取模用的数字 $m$,和一些形如 “ 将 $[l,r]$内的数 $x$变为 $(ax+b)\bmod m$” 这样的形式的操作。每次可能新增一个操作,或者询问:如果将已经出现的编号为 $[l,r]$的这些操作 阅读更多…
【清华集训 2014】玄学 (UOJ46) 题意 给定一个数列,一个取模用的数字 $m$,和一些形如 “ 将 $[l,r]$内的数 $x$变为 $(ax+b)\bmod m$” 这样的形式的操作。每次可能新增一个操作,或者询问:如果将已经出现的编号为 $[l,r]$的这些操作 阅读更多…
// 这题是个双倍经验题,另一道是 BZOJ – 4398 福慧双修 比较奇妙的做法,记录一下 这题正解有两个,第一个是一个 $\log$的重构图法,还有一个是两个 $\log$的二进制分组法,都很强。 今天考试刚好考到这题,大部分 AC 的同学用的都是二进制分组法,也就是每次按二进制分 阅读更多…
今天无意中碰到这么一道题: 由乃救爷爷 作为一个 WOT 玩家感觉题面十分亲切 值得一提的是我还真和 lxl 语音联机打过 WOT 题目就是裸的 RMQ 问题 然而数据非常大,普通的 $O(n \log _ 2 n)-O(1)$rmq 肯定是无法通过得了的 笛卡尔树欧拉序 $\pm$rmq 的 $O 阅读更多…
无法提供摘要。这是一篇受保护的文章。
题目链接 树链剖分模板题,子树的 dfs 序是连续的,因此这题询问用树剖也是一个 $\log$的,修改 $\log _ 2 ^ 2$ 然而我是来复习 lct 的,发现自己忘得差不多了 lct 维护一下虚子树和就行了,在 access 的时候修改即可,修改询问复杂度都是一个 $\log$的啦 然而跑得 阅读更多…
其实这道题叫 $a$ …. 但是总不能直接贴 $a$ 吧 $QwQ$ ,所以干脆叫 $Tree$ 好了。 我不会告诉你们我组合数打反了导致本来 A 的爆 0 了 TAT 听说 $DP$ 不是正解,不过,$DP$ 复杂度高达 $O(n^4)$ ,听说本应该 $T$ 的,却仗着小常数不仅 $ 阅读更多…
题目链接 树上启发式合并(dsu on tree)模板题 就是先轻重链剖分,dfs 算答案的时候,先去计算轻儿子的答案,为了防止儿子之间互相影响,每计算完一个儿子就要清空统计信息 然后 dfs 算重儿子答案,此时不清空统计信息,然后再去把所有轻儿子的统计信息算进来就能得到当前点的答案了 这样子每个点 阅读更多…
记两个 last 然后分别维护。 注意一下当整个字符串变成一个回文串时,两个 last 应该指向同一个节点。 #include<bits/stdc++.h> using namespace std; #define RI register int typedef long long LL 阅读更多…
比如说有一个平面直角坐标系。 两个基向量是 $(1,0)$和 $(0,1)$。 现在要把基向量改成 $(x _ 1, y _ 1),(x _ 2,y _ 2)$。 只需要将所有点的坐标都右乘矩阵 $\left[ \begin{matrix} x _ 1 & y _ 1 \\ 阅读更多…