[DFS序换根+线段树]BZOJ5379【Tree】题解
题目概述有一棵 $n$ 个点的点权树，刚开始根是 $1$ ，现在有 $q$ 次操作：把根换成 $x$ 。把 $LCA(x,y)$ 子树中节点的权值均加上 $w$ 。询问 $x$ 子树的权值和。解...
[贪心+树状数组]COCI2012【RASPORED】题解
题目概述有 $n$ 个任务，第 $i$ 个任务需要 $T_i$ 的时间完成，加分为 $L_i−s_i$ ，其中 $s_i$ 表示完成该任务的时间。有 $q$ 组修改，会变动 $L_i$ 和 $T...
THUSC2018划水记
6.1 Day-1由于要给两位签PKU的大佬当陪衬，所以提前了一天去BJ。儿童节好评，暗示我只有小学生水平。6.2 Day0早上睡到9点，看了看Emacs配置。12点左右和教练去看望两位AK数学...
[霍尔定理+线段树]LOJ6062(2017 山东一轮集训 Day2)【Pair】题解
题目概述两个数 $x,y$ 可以匹配定义为 $x+y\ge H$ 。现在给出 $\{a_n\}$ 和 $\{b_m\}$ ，问 $\{a_n\}$ 有多少个连续子序列满足：存在一种方法...
[随机+Trie]LOJ2313(HAOI2017)【供给侧改革】题解
题目概述给出一个 $n$ 位随机 $01$ 串，定义 $data(L,R)=max\{LCP(Suf_i,Suf_j)|i\not=j,L\le i,j\le R\}$ 。给出 $m$ 个询问 ...
[计数]BZOJ5366(Lydsy1805月赛)【代码派对】题解
题目概述有 $n$ 个矩阵，问多少三元组 $(i,j,k),i<j<k$ 满足三个矩阵至少有一个相交的格子。解题报告我怎么连计数题都不会……这种题目肯定要考虑枚举相交的格子来统计贡献...
[随机+主席树二分]BZOJ5361(Lydsy1805月赛)【对称数】题解
题目概述给出一棵 $n$ 个节点的树，每个节点有权值，一条路径上的对称数定义为最小的出现次数为偶数（包括 $0$ ）的数，现在给出 $m$ 个询问 $(x,y)$ 表示询问 $(x,y)...
[随机]BZOJ5365(2018年5月赛)【回文树】题解
题目概述给你 $n$ 个点，每个点有一个 $[1,n]$ 的随机权值，问有多少回文路径。解题报告因为是随机的……所以你要有信仰，假装回文路径长度最多只有 $5$ 就行了。然后因为他只有 $3s$...
[线段树动态开点]BZOJ5358(Lydsy1805月赛)【口算训练】题解
题目概述给你 $\{a_n\}$ ，给出 $m$ 个询问 $l,r,d$ 表示询问 $a_l\times a_{l+1}\times\cdots\times a_r$ 是不是 $d$ 的倍数。解...
NTT
快速数论变换(Fast Number-Theoretic Transform)，简称NTT(FNTT)。然而这货和FFT基本上一样，就是求 $A(x)B(x)$ ，只不过系数要对 $p$ 取模。...
