【题解】滑动窗口 拆贡献+单调栈

题目 有一个数列,长度为 $n$ 。有 $q$ 个询问,每次询问所有长度为 $k$ 的区间的最大值之和。 $q\leq 1e6$ ,$n\leq 1e6$,$k\in [1,n]$ 。 题解 先拆一波贡献,把答案转化为每一个数对与每一个询问的贡献。 可以发现,一个数对一个询问有贡献 (即被当做最大值 阅读更多…

【题解】Everything on It 容斥 ARC096C —Qiuly

题意: 给你 $n$ 种酱。 你需要若干碗拉面,并且满足: 你可以在每碗拉面上放若干酱,也可以不放,容易发现方案数为 $O(2^n)$ 。 不能出现放的酱一样的两碗甚至更多拉面。 每一种酱至少在两碗拉面中加了。 求拉面集合的方案数。 考虑容斥,设 $S(i)$ 表示有 $i$ 个不合法的酱,其他的 阅读更多…

【题解】Campus 树状数组 CF571D —Qiuly

建两个森林,每次合并两棵树的时候新建一个点作为两棵树的根的父亲,就像 $\rm{Kruskal}$ 重构树一样。 考虑修改操作和询问操作,对于每一个询问操作维护一个 $[l,r]$ $(1\leq l\leq r\leq m)$,表示该询问操作的有效时间,也就是说 $l=1$ 或者 $l-1$ 是一 阅读更多…

【题解】Walking! 贪心, 堆 CF578E —Qiuly

题意转化过来就是,你需要将原序列拆分成尽可能少的形如 LR….RLR 或者 RL….LRL 子序列,最终的答案就是子序列数 $-1$ 。 首先令 AB 表示 A 为子序列开头,B 为子序列结尾的子序列,上面的分别是 LR 和 RL 子序列。 需要注意的是,假设只存在 LR 和 RL 子序列, 阅读更多…

【数学】傅里叶大家族 -boshi

傅里叶变换大家族 信息学中经常用到的 “快速傅里叶变换”,其实只是傅里叶大家族的冰山一角。这篇文章将带你了解真实的傅里叶变换家族。 一. 傅里叶变换 (FT) 1. 傅里叶变换的物理意义 简单来说,傅里叶变换是一个从 “时域” 到 “频域” 的变换。 什么意思呢? 它可以将一个有关时间的函数 $f( 阅读更多…

【题解】Trinity NTT,DP AGC021F

考虑设 $f(i,j)$ 表示 $i$ 行每行都有至少一格黑色的大小为 $i\times j$ 的表格的方案数。 最终的答案就是 $\sum {n\choose i}f(i,m)$ 。 考虑如何转移,每一次加入一列,并且加入若干行,最终的行数分成小于等于 $i$ 和大于 $i$ 两种。 考虑小于等于 阅读更多…