又见到了山东的朋友们。感觉我已经不再年轻了。
D1
爆力50+50+100=200/xia
A. nset
给一棵树，给每个点分配一个权值，求对于所有\(i\)，权值\(\geq i\)的点构成一个连通块的方案数。但是这个问题太简单了，于是多次查询，每次钦点一个点的权值，求答案。\(n,q\leq 10^5\)，答案膜\(998244353\)。1.5s。
考虑这个看起来就是把树分层之类的。容易想到枚举权值最大的点然后换根dp，但是换根就不是很好，考虑在权值最大的连通块的lca处统计，直接设\(dp(u,i,0/1)\)表示\(u\)的权值是\(i\)，权值最大的连通块的lca不在/在子树内的方案数。为了优化这个，看起来把转移写成合并，然后整体dp就好了。但是我不会写线段树啊?
B. sequence
给\(n,c\)，考虑所有正整数序列，满足和为\(n\)，并且相邻两项差的绝对值不超过\(1\)，设其中有\(k\)个下降，则贡献是\(c^k\)。求所有贡献之和。\(n\leq 2\times 10^5\)，答案膜\(998244353\)。3s。
考虑一个简单dp，设\(dp(i,j)\)表示和为\(i\)，最后一项为\(j\)的答案，那么有\(dp(i,j)=dp(i-j,j-1)+c\cdot dp(i-j,j+1)\)。这让我们很难不想起某个简单dp转成多点求值的牛逼题，但是我们还是先不要尝试法。
注意到如果这个序列的第一项至少是\(K\)，那么项数不超过\(K-\sqrt{K^2-2n}\)(如果\(K^2<2n\)那么这个性质啥用没有)，否则每一项不超过\(\sqrt{K^2+2n}\)。后者是简单的，但是前者看起来比较复杂。让我们感觉一下项数很少有啥用。
考虑一开始那个dp的问题出在我们的第一个数可能很大，但是第一个数很大的话，小一些的数就不可能出现了。于是考虑把所有数都向下平移，平移到最小的数变成了\(1\)，然后计算它向上平移之后有没有可能变成\(n\)，也就是设\(dp(i,j,k,0/1)\)表示\(i\)项，和为\(j\)，最后一项是\(k\)，没有/有一个\(1\)的方案数。发现状态数是\(O(n^2)\)的，然后搞了很多想法都没有把这个状态数砍\(\Theta(n^\epsilon)\)，但是砍\(\log\)看起来比较容易。
会不了/fn
C. memory
求\(\mu^2\)的前缀和，以及\(\mu^2(n)\mu^2(n+1)\)的前缀和。\(n\leq 2\times 10^{10}\)。4s 2GB。
分段打表。跑出所有素数之后，埃筛筛\(\mu^2\)是线性的，所以还是很快的，所以这是真正的签到题。看起来有什么牛逼做法?
D2
爆力100+43+30=173。但是挂了，只剩下90了。然而dwt老师才是今日挂分王/se
A. sequence
平衡树。调了我3h，并且卡空间/fn
B. partition
给\(n,m,k\)，求
\[[z^n]\frac{1}{(1-z)\prod\limits_{i=0}^\infty(1-z^{m^i})^k}\]，\(n,m\leq 10^{18},k\leq 20\)。
好像是某种套路。考虑我们让分母变成关于\(z^m\)的多项式，那么问题变成求某种\(\displaystyle [z^n]P(z)\frac{1}{F(z^m)}\)这样的，而后面那个是\(z^m\)的幂级数，所以前面那个\(P\)中的某个\(a_kz^k\)在卷积中只能贡献到\(z^{k+tm}\)，所以只有\(k\equiv n\pmod{m}\)的项才有用，于是我们对分子分母同时折半。
考虑怎么凑这个，直接上下同乘一个形如\(\frac{(1-z)^m}{(1-z)^c}\)的东西就好了。
C. problemprovidercreep
给\(s,t,n,m\)，求
\[\sum_{i=0}^n(-1)^i\binom{n}{i}\binom{s-it}{m}\]，\(s\leq 10^{18},t,n,m\leq 10^9,m-n\leq 1000\)。
注意到它是\(f(x)=\binom{s-tx}{m}\)的\(n\)阶差分的点值\((\Delta^n f)(0)\)，而\(f\)是\(m\)次多项式，所以我们知道低于\(n\)次的都被差分没了，只有至少是\(n\)次的有贡献。
如果把这些东西都转到下降幂，问题就变得简单起来。但是我们需要考虑一下怎么转，发现它的普通幂可以翻转之后取\(\ln\)得到，它的翻转看起来是\((sx-t)((s-1)x-t)...((s-m+1)x-t)\)，我们提出\((-t)^m\)然后取\(\ln\) :
\[\begin{aligned} &\ln\prod_{i=0}^{m-1}\left(\frac{s-i}{t}x+1\right) =&-\sum_{j=1}^\infty\frac{(-1)^jx^j}{j}\sum_{i=0}^{m-1}\left(\frac{s-i}{t}\right)^j \end{aligned}\]后面是一个自然数幂和，可以插一插插出来，或者用自然数幂和的egf搞定。于是再求一个第二类斯特林数行后缀，然后递推\(m-n\)轮，强行把它们都转成下降幂就结束了。能否做到\(O(n\log n)\)?
多项式基
其实杜爷并没有讲这个，但是我对这个很没感觉（
很多时候我们会希望把一个什么东西拆成若干个多项式的和，比如把普通幂转成下降幂之类的，这可能可以让它们和式子的其它部分结合起来从而简化式子。
简单想法是，关于\(x\)的\(0,...,n\)次多项式各一个显然可以线性表示任意\(n\)次多项式。我猜测一般我们也只会用这个。
线性递推
计算\([z^n]\frac{P(z)}{Q(z)}\)。
上下同乘\(Q(-z)\)，发现分母变成对\(z,-z\)对称的东西，所以它只有偶次项。和刚才那个B类似的，分子的奇偶次项中只有一种会贡献，然后就容易发现可以把\(n\)折半了。复杂度\(O(d\log d\log n)\)。
特征多项式
一个矩阵\(A\)的特征多项式定义为\(\det(xI-A)\)。代入\(x=A\)可以知道这个多项式的值为\(0\)。
考虑它有什么用。发现矩阵乘
完全背包
求
\[[z^n]\frac{1}{\prod\limits_{i=1}^m(1-z^{c_i})}\]，\(n\leq 10^{100},m\leq 50,c_i\leq 500\)。
上下同乘\(\prod\limits_{i=1}^m(1+z^{c_i})\)，那么所有\(c_i\)会翻倍，于是大家都是偶数了，可以一样折半，上面的次数是\(1+\frac{1}{2}+\frac{1}{4}+...\)这样的。次数是\(O(nc)\)，乘\(1+z^c\)是线性的，总复杂度\(O(n^2c\log n)\)。
loj noi round #2 简单算术
给\(n\)次多项式\(F\)和\(m,k\)，求\([z^k]F^m\)，\(n\leq 50,m,k\leq 10^{18}\)，膜素数\(p\leq 50\)，\(1000\)组多测。
结论是，\(f(x)^p=f(x^p)\)，看起来比较的经典，但是经典结论我也不知道/cy。于是问题变成算\(F^{\lfloor\frac{m}{p}\rfloor}(z^p)F^{m\bmod{p}}(z)\)，右边是\(O(np)\)次，所以
luogu7512 Byakkai OI 2021 Eaquira
虽然我并不会把这个写成gf啊（
给\(n\)，设\(F=\frac{z}{(1-z)^3},G(z,w)=\frac{zw(1+w)}{(1-zw)^2}\)，求
\[[z^n]\frac{2+F}{1-FG(F,w)}\]。\(n\leq 2\times 10^5\)。
考虑把它看成一个关于\(w\)的多项式组成的线性递推序列，直接套用刚才的线性递推算法，它的分子分母都是\(O(1)\)个关于\(z\)的项所以可以爆力乘，乘的时候对\(w\)的多项式之间用法法塔来算，这个\(w\)的次数看起来在指数级增长，但是好消息是显然它每轮只会\(\times 2\)，所以我们就赢麻了，复杂度\(O(n\log n)\)。
ode
之前写过了，不过好像不是很深刻。现在也不打算写，摸了。
D3
A. garlic
给一个序列和\(x\)，求有多少区间的\(\min+\max=x\)。复杂度线性。
但是没有卡\(\log\)，所以签到了（
考虑直接解决 两个序列，求有多少区间的\(\max\)相等 这个问题。我们同时在两个序列上跑同一个单调栈，相同的数两个序列分别保留最多一个，然后就可以讨论一下处理掉max相等的段了。这个讨论，和ss老师讨论了一下，好像不是很好讨论，但也不是很难。
B. cow
懒得写题意了（
考虑如果没有一开始和最后强制按的那个按钮，这个权值可以看成一个gf \(F_k=1+z\sum_{i=0}^{k-1}F_i^2=zF_{k-1}^2+F_{k-1}\)。
考虑如果有一开始那个按钮，那么是\(S_k=S_{k-1}+zS_{k-1}F_{k-1}\)。有最后那个，记为\(T\)，是对称的。
考虑如果两边都有，那么是\(G_k=G_{k-1}+zS_{k-1}T_{k-1}\)。
C. frog
序列，每次查询一个区间的所有和它颜色数相同的子区间中，最短的那个的长度。\(n,q\leq 2\times 10^6\)，5s。
瞬间就会了一个回滚莫队，但是只卡进10s/hanx
考虑扫描线批量处理所有子区间对查询的贡献。先搞一个阳间一点的限制。可以拆出这么两个看起来比较好的东西 : 它的右端点在这个查询区间中最右的 某个数的第一次出现 的右边，并且右端点到左端点
CF1349F2 的代数部分
得到gf的过程好像很恐怖。
(xtq)求
\[[z^n]\frac{1}{(1-F(z))(1-tzF(z))}\]，其中\(F(z)=\frac{e^z-1}{z}\)。
这是拉反例题，所以我们考虑\(F\)的复合逆，但是发现它有常数项所以没有复合逆，于是转而考虑\(zF\)的复合逆，它是\(G(z)=\ln(1+z)\)。问题是如何写出\(H\)，这要求我们把\(F\)表示成\(G\)的函数，根据\((zF)(G)=z\)，可以直接\(F(z)=F(G(zF))=(F(G))(zF)\)，所以\(H=\frac{1}{(1-(F(G))(z))(1-tz)}\)这样的。拉反即可。
\[[z^n]\left(\frac{1}{(1-(F(G))(z))(1-tz)}\right)(zF)=[z^n]\left(\frac{1}{(1-F(G))(1-tz)}\right)\left(\frac{1}{1+z}\right)\left(\frac{z}{\ln(1+z)}\right)^{n+1}\]除了\(\frac{1}{1-tz}\)，别的东西都可以硬算。于是问题变成\([z^n]\frac{A}{1-tz}\)这样的，看起来可以展开\(\frac{1}{1-tz}\)直接做。
(EI)求
\[[z^n]\frac{t(e^{z(1-t)}-1)}{(1-z)(1-te^{z(1-t)})}\]这个式子看起来就很恐怖啊/xia
斯特林数
第二类斯特林数关于下指标的egf是
\[{n\brace k}=n![z^n]\frac{1}{k!}(e^x-1)^k\]这个式子的含义就是分成\(k\)个非空集合。
关于上指标的ogf是
\[{n\brace k}=[z^n]\frac{z^k}{\prod\limits_{i=1}^k(1-iz)}\]第一类斯特林数关于下指标的egf是
\[{n\brack k}=[z^n]\frac{1}{k!}(\ln\frac{1}{1-z})^k\]关于上指标的ogf是
\[z^{\overline{n}}\]sdoi2022 多边形
考虑\(n\)个点的多边形三角剖分的数量是卡特兰数\(C_{n-2}\)。这里的不同在于，同一条边上不能连，并且有一些点可以在三角形的边上(但是不能一整条边都没有被连到)。
考虑为了处理第二个，我们对于每条边枚举上面有多少点，然后组合数选出来。现在问题是同一条边上不能连。考虑容斥，可以注意到现在各边是独立的，它们之间全靠那个卡特兰数拼起来，所以我们只需要考虑一条长\(l\)的边应该分配何种容斥系数，然后把它们的ogf分治呐塔塔卷起来就好了。
发现直接对 任意两点之间没有线 容斥看起来是不彳亍的，因为直接钦点的话这些线可能会交叉，看起来它很复杂。可以想到对 任意一点不被一条线跨过 容斥，但是这个看起来和上一个没啥区别。
考虑一个牛逼想法，我们对 没有一条线连接相隔一个点的两个点 容斥。可以发现如果一个方案包含同一条边上两个点之间的线，那么它就把这条边的一部分和外部隔开了，而这里面还会被完全剖开，所以必然存在一个三角形，也就是连接相隔一个点的两个点的线。这个东西的好处是它看起来非常局部，我们可以直接把这个三角形挖掉再上卡特兰数。我们钦点一些这样的线，设它的ogf是\(T(z,t)\)，其中\(z\)表示总边数而\(t\)表示挖掉那些三角形之后的边数，可以写出\(T=1+t(zT-z^2T)\)，也就是决策最后一个点怎么连，于是\(T=\frac{1}{1-t(z-z^2)}\)。
但是算完这个好像还没结束，因为我们还需要考虑留下了多少个点。
\[\begin{aligned} &\sum_{i=0}^{a-1}\binom{a-1}{i}[z^{i+1}]T\\ =&\sum_{i=0}^{a-1}\binom{a-1}{i}[z^{i+1}]\frac{1}{1-t(z-z^2)}\\ =&[z^a]\sum_{i=0}^{a-1}\binom{a-1}{i}\frac{z^{a-(i+1)}}{1-t(z-z^2)}\\ =&[z^a]\frac{1}{1-t(z-z^2)}\sum_{i=0}^{a-1}\binom{a-1}{i}z^{a-1-i}\\ =&[z^a]\frac{(1+z)^{a-1}}{1-t(z-z^2)} \end{aligned}\]于是问题就是最后这个式子。为了把\(t(z-z^2)\)拆开，考虑对\(F=z-z^2\)进行拉反，我们计算它的复合逆。为了凑出一个不带二次项的东西，首先配方成\(1-4z+4z^2=(1-2z)^2\)，然后就结束了，所以它的复合逆是\(G(z)=\frac{1-\sqrt{1-4z}}{2}\)。然后考虑如何表示\((1+z)^{a-1}\)，它看起来就是\((1+G(F))^{a-1}\)，这可真是太直接了，不过为什么感觉很爽啊?所以我们知道这里\(H\)就是\(H(z)=\frac{(1+G(z))^{a-1}}{1-tz}\)。反一手。
\[[z^a]\frac{(1+G(F))^{a-1}}{1-tF}=[z^a]\frac{(1+G)^{a-1}}{1-tz}G^\prime\left(\frac{z}{G}\right)^{a+1}\]那个\(\frac{1}{1-tz}\)，我们最后枚举\(t\)的次数，问题就是要求出剩下的东西的乘积。但是这个\((1+G)^{a-1}\)看起来不是很好办啊?可以注意到\(G\)跟卡特兰数看起来很像，实际上它就是\(z\mathcal B_2\)，可以用广义二项级数的结论来做，据说可以线性。不过如果不知道广义二项级数，由于\(G\)的复合逆\(F\)很简单，我们可以再对\((1+G)^{a-1}\)和\(\left(\frac{z}{G}\right)^{n+1}\)进行拉反。为了练习我实践一下。先来看\((1+G)^{a-1}\) :
\[\begin{aligned} &[z^n](1+G)^{a-1}\\ =&\frac{1}{n}[z^{n-1}]((1+z)^{a-1})^\prime\left(\frac{z}{z-z^2}\right)^n\\ =&\frac{1}{n}[z^{n-1}]\frac{(a-1)(1+z)^{a-2}}{(1-z)^n} \end{aligned}\]，可以一次卷积求出。再看\(\left(\frac{z}{G}\right)^{n+1}=\left(\frac{F(G)}{G}\right)^{n+1}\) :
\[\begin{aligned} &[z^n]\left(\frac{F(G)}{G}\right)^{n+1}=[z^n]\frac{(z-z^2)(1-2z)}{z(1-z)^n}=[z^n]\frac{(1-2z)}{(1-z)^{n-1}} \end{aligned}\]，可以线性。于是分治法法塔卷起来，乘上卡特兰数即可。
zjoi2020 抽卡
考虑我们不要停下来就不抽了，而是在停下来之后不继续贡献，这样每个卡数量相同的状态是等价的。对于有\(i\)张卡的状态，它在期望\(\frac{n}{n-i}\)轮之后获得一张新卡，所以如果它还没停下来就会贡献\(\frac{n}{n-i}\)。于是问题变成算还没拿到足够长连续段的方案数。考虑怎么算还没拿到一个足够长连续段的方案数。
注意到序列分成若干段，每一段之间是独立的，所以只需要考虑一个长\(l\)的段。没有拿到长\(k\)的连续段，也就是拿到了若干长度\(<k\)的极长连续段接起来，我们，所以可以写出\(\frac{}{}\)
q-analog
loj round #9 Tangjz 的背包
q-lucas定理
\[\binom{n}{m}_q=\binom{n/p}{m/p}\binom{n\bmod p}{m\bmod p}_p\]哈希杀手
D4
A. cilrag
求周长为\(n\)的三角形个数，\(n\leq 10^{18}\)，边是无序的。
可以考虑合法当且仅当每条边都小于一半，所以考虑\([z^n]\left(\frac{z-z^{\lfloor\frac{n-1}{2}\rfloor}}{1-z}\right)^3\)，这个看起来很好算，然后再容斥一下把等腰等边减去就好了。
B. milk
用若干个自然数区间给出的一个集合，求从中选择三个数，两两\(\operatorname{xor}\leq k\)的方案数。\(n\leq 2\times 10^4,k,v\leq 10^9\)。
考虑在trie上dp。设\(\)
C. zx
原题 集训队胡策2018 完美的队列。有点经典了（
考虑对每次操作处理出它影响的时间区间，然后扫描线扫过去统计答案。把操作挂到线段树上，可以感觉到每个点上的操作显然是先进来的先弹没。考虑这个点会被它的祖先和后代影响，后代的影响总量是\(O(n\log n)\)，因为一个操作会影响到所有定位它的时候经过的点，而祖先的影响总量很大，不过祖先总是覆盖这个点，可以每次查询一段时间内祖先插入的总个数。把当前结点和它的后代的所有操作排序，然后一边扫一边考虑祖先的影响。
ahoi2022 山河重整
求有多少个\(1,...,n\)的子集的子集和包含\(1,...,n\)的所有数。\(n\leq 5\time 10^5\)，膜任意数。
既然要表示一个前缀，考虑每个集合的最小的不能表示的数。
转置原理
尝试重连…
重连失败。尝试重连…
重连失败。尝试重连…
重连失败。尝试重连…
重连失败。尝试重连…
重连失败。尝试锤子。
也就是如果一个问题可以表示为计算对一个输入向量的线性变换(很多计数问题可以)，并且我们可以用一个线性算法(不会用到二次项，并且流程和输入的值无关的算法)计算它，那么就可以通过对这个算法进行转置，也就是把参数和返回值转置并把所有步骤倒过来，来计算这个线性变换的转置所对应的问题。具体一点就是这个算法可以表示为把所乘矩阵分解成若干个便于计算的矩阵的乘积，而转置原理给出\((M_1M_2M_3...M_m)^T=M_m^T...M_2^TM_1^T\)这样的。
几个简单问题的转置
多项式乘法
计算\(C=AB\)，固定\(A\)的话，多项式乘法是线性算法。它看起来是乘了矩阵\(M_{i+j,j}=[z^i]A\)。
dft
dft的转置是自己。
如何转置一个算法
一个算法是一个函数(可能是递归函数)。
我们颠倒它的输入和返回值，然后把所有步骤倒过来。有的步骤可能并不需要倒过来，比如某些并列的步骤。
小练习
蝴蝶变换是
\[\begin{bmatrix} A_{p+i}\\ A_{p+\frac{l}{2}+i} \end{bmatrix} := \begin{bmatrix} 1&\omega_l^i\\ 1&-\omega_l^i \end{bmatrix} \begin{bmatrix} A_{p+i}\\ A_{p+\frac{l}{2}+i} \end{bmatrix}\]那么转置就是
\[\begin{bmatrix} A_{p+i}\\ A_{p+\frac{l}{2}+i} \end{bmatrix} := \begin{bmatrix} 1&1\\ \omega_l^i&-\omega_l^i \end{bmatrix} \begin{bmatrix} A_{p+i}\\ A_{p+\frac{l}{2}+i} \end{bmatrix}\]翻译过来就是\(x:=A_{p+i}+A_{p+\frac{l}{2}+i},y:=\omega_l^i(A_{p+i}-A{p+\frac{l}{2}+i}),A_{p+i}:=x,A_{p+\frac{l}{2}+i}:=y\)。
区间加
区间加，最后求整个序列。
把加的数看作输入，可以画一画它的矩阵，看起来是每一列表示一个加操作。使用转置原理，此时输入一个序列，输出会变成这些区间的区间和。于是可以继续发现差分-前缀和和前缀和-差分是一对转置算法。
dif-dit fft
dft的转置是自己。我们把法法塔转置，此时它的bit rev这一步还是bit rev，只是到了最后。而idft使用未经转置，bit rev在最前的算法，那么这两个bit rev就对掉了，于是我们的法法塔不再需要bit rev。
多项式乘法
固定\(A\)，计算\(C=AB\)。
写出来转一转，它是
\[b_i=\sum_{j-k=i}c_ja_k\]也就是差卷积。
多点求值
把点称为\(x\)，系数是\(a\)，答案是\(b\)。考虑多点求值的矩阵是啥。它是\(m_{i,j}=x_i^j\)，所以它的转置是\(m_{i,j}=x_j^i\)，此时我们要计算
\[a_i=\sum_jb_jx_j^i\]用gf写成
\[[z^i]\sum_j\frac{b_j}{1-x_jz}\]于是这个东西和\(i\)无关了，我们只需要算它的前\(n\)项这样的。考虑直接分治，两边是两个有理分式，我们乘一乘就可以把它们合并起来，最后还要求一个逆。于是问题变成转置乘法和转置求逆，看起来还是可以做到的!
gym102978D XXI Open Cup, Grand Prix of Tokyo D. Do Use FFT
计算
\[ans_k=\sum_{i=1}^nc_i\prod_{j=1}^k(a_i+b_j)\]把\(c\)看成输入，则变换是\(M_{i,j}=\prod\limits_{k=1}^i(a _j+b_k)\)。进行转置，问题变成计算
\[c_i=\sum_{i=1}^nans_j\prod_{k=1}^j(a_i+b_k)\]可以发现此时\(a_i\)变得固定了，问题变成分治法法塔算出后面那个多项式，然后多点求值。先执行多点求值的转置，也就是刚才我们做的东西，然后执行分治法法塔的转置即可。
luogu7440 KrOI2021 Feux Follets
考虑长\(m\)的错排恰有\(k\)个环的方案数
\[[z^mt^k]\exp(t\ln D(z))=[z^mt^k]\exp(t(-\ln(1-z)-z))\]我们要求的就是
\[ans_i=\sum_{k=1}^mf_k[z^mt^k]\exp(t(-\ln(1-z)-z))\]，其中\(f_k\)是那个多项式的值，拍一个多点求值上去就可以让你的代码长度增加2k了。
考虑其转置
\[f_k=\sum_{i=1}^mans_i[z^mt^k]\exp(t(-\ln(1-z)-z))\]sdoi2022 多边形
计算
\[[z^n]\frac{A(z)}{1-tz(1-z)}\]也就是
\[ans_i=\sum_{}\]容斥
luogu7275 计树
求有多少有标号无根树，满足每个点都有一个和它在编号上相邻的邻接点。
考虑树必然是若干极长的编号连续的链拼出来的，或者说生成一棵树的方法是，把编号划分成若干长度\(>1\)的连续段，然后连成一棵树，不能连相邻两条链的首尾。如果不要求极长，我们可以用prufer序列的结论把它们拼起来，但是此时可能出现两条链首尾相接形成一条更长的链。
考虑对极长进行容斥，我们要给每个连续段分配一个容斥系数，使得一条极长链以所有方式被算到的容斥系数之和恰好是\(1\)，当然长\(1\)的链是\(0\)。设它的ogf是\(F\)，那么\(\frac{1}{1-F}\)就枚举了所有它被算到的方式的容斥系数之和，所以我们知道\(\frac{1}{1-F}=z^2+z^3+...=\frac{1}{1-z}-1-z\)，解得\(F=\frac{z^2}{z^2-z+1}\)。
然后就prufer就好了。gf写写容易做到$O(n\log n)$。据说这东西是线性递推，所以可以$O(\log n)$啦。
loj6728 u群把妹王
D5
A. tmcpq
树，每个点有一个权值，一开始内部结点的权值都是\(0\)，接下来进行若干轮操作，每轮把每个点的权值变成儿子们上一轮权值的\(\max\)。多次查询某一轮之后链min,max,sum。\(n,m\leq 2\times 10^5\)，4s。
考虑一个简单结论，一条祖先-后代链的权值是从下往上递减的。
考虑这个相当于有一些段在树上往上走，然后可能会发生某些碰撞这样的。树剖，每条链上用平衡树维护连续段。可能发生这么几种事情 :
开一个堆维护下一个发生的事件即可。
B. rsrams
序列，每次查询一个区间，求它的所有子区间的绝对众数之和，没有则认为是\(0\)。\(n,q\leq 10^6\)，12s。
考虑一个数的贡献，把它置为\(1\)，别的置为\(-1\)，于是绝对众数是这个数等价于区间和\(>0\)。拆成前缀和，问题变成区间逆序对，所以上个二次离线就好了。
现在问题是数很多，我们希望把序列变短一点这样的。可以发现如果一个数\(k\)出现次数很少，那么在很大量的区间里面和都是负的。考虑一个牛逼想法，我们往左往右跑两遍，第一次让每个\(k\)匹配左边第一个未匹配的\(\neq k\)的位置，第二次匹配右边，如果一个数两次都没被匹配，那么包含它的所有区间和必然\(<0\)，那么就可以把它扔掉了。把剩下的这些区间拼起来，中间塞上\(-\inf\)，跑区间逆序对即可。
现在问题是我们每次二次离线还是要遍历所有查询，所以复杂度就\(O(nm)\)了。考虑对一个颜色的出现次数根号分治，出现次数超过根号的颜色二次离线，少于根号的直接枚举一对逆序对，然后要做有\(n\sqrt{n}\)个点\(m\)次查询的二维数点，根号平衡即可。复杂度\(O(n\sqrt{q}+q\sqrt{n})\)。
C. hpmo
原题icpc2022 Shenyang H.
平面上有一些点，做半平面的莫队。\(n\leq 10^5,q\leq 2\times 10^5\)，总变化量上限是\(1.8\times 10^8\)，4s。
我也想问spj怎么写的，但是很遗憾，spj是\(n^2\)的/jy
比较牛逼。随机在这些点中取根号个关键点，对于每个半平面找到距离最近的关键点，然后从每个关键点出发旋转扫描线，扫到一个查询的时候直接平移过去。显然这个期望次数是\(O(n\sqrt{n})\)。
但是这个莫队具体怎么移动，看起来不是很容易啊（
Ynoi2077 3dmq
三维空间中有\(n\)个点，支持左下3-side长方体加/乘/求和。\(n\leq 5\times 10^5\)，数据随机。
lxl表示Ynoi2077的意思是卡不掉爆力的题，因为2077年的评测机才足够快（
lxl表示要先讲一个类似的题。
序列，支持下标的等差数列加/求和。
直接根号分治不是很好办。
考虑对时间分块，块之间重构序列，发现此时一个修改对一个查询的贡献可以exgcd出来，然后问题是怎么\(O(1)\) exgcd，发现可以\(O(n)-O(1)\) gcd来除掉gcd，问题变成求逆，然后全都离线下来线性求逆结束战斗。剩下的问题是块间怎么重构以及怎么解决静态问题，发现这俩都要带根号，所以我们只好平衡一下做到\(O(n^{\frac{3}{5}})\)了，具体一点是时间分块块长\(\frac{2}{3}\)，而根号分治\(\frac{1}{3}\)。
于是对于3dmq，继续时间分块，发现一个修改对一个查询的贡献还是可以快速算，但是看起来需要3-side数点，但是可以发现我们可以离线扫描线，上一个根号平衡，所以就结束了，
cts2022 袜子
半平面小z的袜子。\(n\leq 5\times 10^4,q\leq 5\times 10^5\)。
半平面莫队真的能写吗（
随机数据下kdt是正确的。
考虑一个颜色的贡献，可以发现\(ax+by+c<0\)是限制\((x,y)\)的一个半平面，也是限制\((a,b)\)的一个半平面。于是一个点的贡献可以写成什么答案+=当前这个颜色的出现次数，当前出现次数++，然后颜色之间是当前出现次数=0这样的，可以在kdt上打矩阵标记。
未知来源题
时代的眼泪上半平面。
它看起来不是很能直接上时代的眼泪的树套树之类的。
但是这是半平面，所以它不一定比时代的眼泪强。
可以注意到由于是顺序对，如果查询半平面斜率都是负的，假设是下半平面，我们知道对于任意一对顺序对，有贡献当且仅当右上的那个出现，所以每个点的贡献就是左下方的点数。
但是如果斜率是正的，考虑转而计算顺序对，结束了。
luogu4062 Code+#1 Yazid 的新生舞会
序列，求有多少个区间有严格众数。\(O(n)\)。
考虑还是用那个trick。往左找，往右找，这两个可以用并查集做到几乎线性，可以\(\log\)大小分块，块间开并查集，块内四毛子做到真的线性。
然后逆序对怎么线性啊?考虑序列的性质就是它是\(\pm 1\)，所以我们扔掉BiT，直接考虑画一条折线，可以发现此时移动一步的变化量可以直接用桶维护，于是复杂度是线性。
luogu8283 MCOI-08 Dantalion
序列，每次查询一个区间，求有多少子区间满足任意两个数的xor和仍在这个子区间中。\(n\leq 6\times 10^5,q\leq 10^6\)，1.37s。
发现任意两个数的xor都在区间中，则任意子集的xor都在区间中。于是我们知道这个区间中所有能被它的线性基xor出来的数都在区间中。于是它的颜色数是某个\(2^k\)，所以我们对每个\(k\)双指针求出所有这样的区间，然后可以扫一扫右端点，维护\(\log\)个线性基，从而扫出每个区间的线性基大小，然后数点就结束了。复杂度是俩\(\log\)。
考虑怎么砍一个\(\log\)。瓶颈在于求这些区间的线性基大小，以及数点。
考虑数点，我们先差分一下得到两种系数的区间，然后容易知道对于一个\(k\)，同种区间左右端点都是单调的，于是问题变成求查询区间中最后一个右端点和第一个左端点，可以双指针扫出来，但是这个题强制在线，不过我们可以直接预处理前驱后继。
考虑线性基，我们维护一个加入时间最大的线性基，也就是在加入一个已经存在的数的时候尝试把前面的数换掉，然后把换出来的继续往下插入，求出来的就是最右的。
另一个做法是类似于thupc2022 rsraogps，这里是扫右端点，所以前缀的答案变化是有均摊的。差分成$[1,r]\times [1,r]-[1,l-1]\times [1,r]+[1,l-1]\times [1,l-1]$，前缀的答案是好求的，对每个$l$维护$[1,l-1]\times [l,r]$的答案，那么$r$移动的时候答案就增加$[1,l-1]\times r$这些区间。$[l-1,r]$的线性基大小只会变化$O(\log n)$次，如果它不变化的话$[i<l-1,r]$的线性基大小也必然不变，于是只需要维护有多少个到$r$距离$2^k$的点落在$[1,l-1]$中，就相当于打了一个$a\leftarrow a+b$的标记，而这玩意的变化也有均摊。复杂度$O(n\log v+q)$。
luogu7889 MCOI-06 Eert Tuc Knil
容易感觉到这是一个凸的\(O(n)\)段分段函数，然后凸函数的和还是凸函数，所以只要线段树合并或者平衡树启发式合并就好了。
考虑了ktt，不知道是否可行。据说在静态top tree上ktt是可行的。
随机数据半平面数点
把横纵坐标分别分成根号块，那么每块点数期望是\(O(1)\)。半平面只会经过根号个零散块，整块可以前缀和，复杂度是期望根号。
D6
兄弟会背叛你，女人会离开你，金钱会诱惑你，生活会刁难你，只有ds不会，不会就是不会，怎么学都不会/fn
A. rpfrdtzls
序列，每个位置有一个序列，还有一个数\(x\)，定义一个序列的权值是一开始拿着一个\(x\)进去，依次除第一项，第二项，……，直到变成\(0\)，此时所在的项。支持区间push_front一项，查询区间权值和。\(n,q\leq 5\times 10^5,x\leq 10^9\)，操作数可能是\(1\)。
操作数是\(1\)相当于给前一个操作的某种权值\(+1\)，问题变成权值和这样的。
离线，扫描线扫序列，平衡树维护时间。把查询差分成前缀，那么我们可以用线段树维护每个时刻答案的历史和这样的，然后每次插入一个操作就爆力考虑前后\(\log\)个操作，重算答案然后在线段树上爆力改即可，复杂度\(O(n\log^2 n)\)。
好消息是计算变化可以双指针，在线段树上改的时候可以直接同时改这\(\log\)个位置，所以就变成一个\(\log\)了。
B. rsas
cf633H加强版。
定义一个集合的hash值是排序后和\(1,b,b^2,...\)的点积。平面上\(1,...,n\)每个\(x\)坐标有一个点，每次查询一个矩形中的点的\(y\)坐标去重后的hash值。\(n,q\leq 2\times 10^5,y\leq 10^{18}\)，答案膜大素数。
我的想法是什么对\(y\)分治，然后就要求有一个\(q\sqrt{n}\)的做法解决\(x\)的区间的问题，但是我只会\(n\sqrt{q}\) kdt所以就死了/hanx
考虑对值域分块，块间是可以合并的。一个值可能出现多次，于是类似于势能均摊莫队，按出现次数加权分块即可。
对于零散块和只有一个值的块，只需要查它有没有出现，莫队并维护一个桶就好了。
对于整块，只考虑一块的话，本质不同的询问只有\(O(\sqrt{n}^2)=O(n)\)种，但是好像不是很好算出所有可能的询问的答案。考虑对值域进行分治，我们选择中位数分成两部分，然后递归下去做，然后爆力合并即可。
总复杂度\(O(n\sqrt{n})\)。
C. rfrqwq
序列，支持区间推平，查询一个区间中给定某个颜色，在这个颜色中所有选两个位置的方案，它们之间颜色段数之和。\(n,q\leq 5\times 10^5\)。
发现这个东西看起来很离奇，但是它居然可以合并。具体地，设在处理颜色\(c\)，我们考虑合并相邻两部分的时候，它们之间的贡献，发现左边每个段会贡献 它左边的\(c\)的个数 乘上 右边这部分的\(c\)
分块。每次操作只会增加\(O(1)\)个不全相同的块，对于完全相同的块修改查询都是容易的，对于不完全相同的块可以爆力重构，但是坏消息是我们不能对每个颜色都重构，但是好消息是我们只需要重构影响到的颜色，而这个也有连续段均摊。
uoj515
单点修改，查询一个后缀的严格后缀min个数。\(n,m\leq 10^6\)。
扫描线扫序列，数据结构维护时间。用线段树维护每个时刻当前后缀的答案，要支持区间取\(\min\)，单点查询一个位置被取\(\min\)多少次，上个吉老师线段树就好了。
cometoj ocntest14 D
有一个序列，初始全为\(0\)，还有一个区间推平的操作序列，每次查询从左往右执行一个操作序列的区间之后，序列中所有数的和。\(n,m,q\leq 10^6\)。
扫描线扫右端点，发现我们维护了执行\(1,...,r\)之后的序列的话，要求\(l,...,r\)的答案，就是只考虑最后被更新的时间\(\geq l\)的位置。考虑往右走一步会发生什么事，看起来我们需要推平掉前面的一些操作，平衡树处理一下变化，用BiT维护答案即可。复杂度是一个\(\log\)。
Ynoi2006 rprmq2
平面，满点集，一开始全是\(0\)，支持四个方向的共顶点2-side矩形分别加任意数，求全局max。\(v,n\leq 2\times 10^5\)，20s。
可以规约到4-side矩形加，矩形max，后者的规约是给查询矩形加上inf，查完再减去。lxl说操作这么奇怪是因为std做这个常数和做一个2-side矩形加是一样的。
rprmq1是先修改再查询矩形max。可以俩\(\log\)。做法是对横坐标分治，然后从分治中心往左右扫，开一个线段树支持区间加区间历史\(\max\)，和kdw考虑了一下感觉这可以写max,+矩阵标记?对于分治每一层从左往右扫，离开一个区间时清空历史和。复杂度\(O(n\log^2 n+q\log n)\)这样的。
考虑对时间分块，块大小是\(K\)，一块内的查询和修改矩形把横纵坐标分别分成$K$段，块内修改对查询的贡献直接四分树，复杂度$O(K^2)$；块间的问题是\(O(K)\)次查询一个矩形在前面块的\(O(n)\)次操作之后的max，可以用rprmq1解决。但是这样是俩\(\log\)啊?
考虑这里的查询性质很好，因为平面是被画成了网格。于是我们直接从左往右扫，扫到一条竖线就处理这条和上条竖线间所有的查询，然后清空线段树，复杂度$O((n+B^2)\log n)$。然后这个trick比较牛逼，因为从左往右扫的过程中横线是固定的，考虑我们建立线段树的时候，在所有的竖条上合并出上一半，从每个横条出发分治地建立下一半，那么每个查询就对应于线段树上一个点，遇到竖线直接把上一半的tag全push到底，复杂度$O(n\log n+K^2)$。取$K=\Theta(\sqrt{n\log n})$，我们得到总复杂度$O(n\sqrt{n\log n})$。
Ynoi2008 rsmemq
序列，定义一个区间是好的，当且仅当它的长度是奇数，并且它的中点(位置)等于它的(非严格)众数(值)。多次查询一个区间的好子区间数量。
好区间的段数是线性的，具体一点就是固定一个中点，可行的左端点构成段的总数是线性的。考虑如果一个中点和一个左端点不是好区间，那么为了再搞出好区间，必然需要中点出现更多次，于是每一段至少对应一次出现，于是总段数是线性。
现在问题是找到所有这些段，然后就变成斜线加直角三角形数点了，这个看起来像是比较好做。考虑根号分治，超过根号的直接做，不超过根号的，扫右端点，维护根号个左端点，表示众数出现次数为\(1,...,\sqrt{n}\)的区间的最右的左端点。
cf1491H
有根树，每个点的父亲编号比自己小，支持编号区间的父亲编号减正数(\(<1\)则变成\(1\))，求两个点的lca。
弹飞绵羊。对于每个点维护跳出这一块的需要跳几步以及会跳到哪，那么减正数最多减根号次，可以找到还没能跳出块的爆力改，求lca的时候可以直接跳出根号个祖先，然后就可以知道这些祖先的深度，然后就可以从上往下找到最后一个交，那么答案必然是那个交或者在前一块里面，爆力扫这一块把它们经过的点都找出来。
据说可以类似于树剖lca做，不是很懂。
cf700D
能不能讲点没讲过的（
序列，每次查询一个区间，对每个颜色的出现次数合并果子。
考虑根号分治，不超过根号的可以每次把一个大小都合并完，超过根号的不超过根号个。这个看起来像是那个经典的\(\frac{n\sqrt{n}}{w}\)的背包。
cf1476G
序列，支持单点修改，查询区间所有非零出现次数排序后所有长\(k\)的区间的极差的\(\min\)。\(n,q\leq 10^5\)，5s。
考虑带修莫队。使用平衡树查rank和kth，容易做到根号\(\log\)。
考虑到不同的出现次数只有根号种，我们可以跑出这个东西，然后就直接双指针了。
luogu7290 EZEC-5 暴力出奇迹
Klee’s measure problem 3d
三维空间中有一些长方体，求体积并。\(n\leq 10^5\)，时限10s。
扫一维，问题变成矩形\(\pm 1\)，求非零位置个数。
套用rprmq2的做法即可。