算法考虑求小于给定值的数的个数，可以给每个块再维护一个已经排好序的数组，整块加法对于这个块排好序的数组没有影响，零散块加法直接在原序列上加，再将零散块所处的整块从新排序。查询时零散块暴力查找，整块二分查找代码#include<bits/stdc++.h>#defineintlonglongconstintM

Statement先把串reverse，多次给\(l,r\)，求\[\max_{l\lei<j\ler}\{\text{LCP}(i,j)\}\]Solution\(\text{sqrtlog}\sim\text{sqrt}\)：莫队+线段树/树状数组/set，用SA做\(nm/\omega\)：bitset乱搞\(\log^2\)：SAM+LCT+BIT在parent树上，LCP等于LCA的

题给代码意为\[\begin{align*}&\sum\limits_{i=1}^n\sum\limits_{j=1}^{\lfloor\fracni\rfloor}\sum\limits_{k=1}^j[\gcd(j,k)=1]\\=&\sum\limits_{i=1}^n\sum\limits_{j=1}^{\lfloor\fracni\rfloor}\varphi(j)\\

Statement问区间本质不同回文串数，强制在线，\(n\le10^5\).其实还有个四倍经验：BZOJ5384.Solution1考虑一个结论：\(s\)的所有回文后缀按长度排序后，可以划分为\(O(\log|s|)\)段等差数列。考虑离线怎么做：移动右端点\(i\)，新增一个串\(s\)，设其上一次出现的起点为\(q\)，则\([q+

Description在IOI王国，人们使用Byou作为时间单位。IOI王国中的一天被分为了\(S\)个时间单位。每天从最开始经过\(x\(0\lex<S)\)Byou后的时间称为时刻\(x\)。IOI王国由\(N\)个城市组成，以\(0\)到\(N-1\)编号。其中有\(M\)条双向道路连接某些城市，以\(0\)

对拍器在此。https://www.luogu.com/discuss/81283献忠！AC代码modoiread{usestd::{io::{stdin,Read},ops::{Add,Mul,Neg},};pubfnnext()->u8{letmuta=stdin().lock();letmutc=[0u8];matcha

Description小Y有一个大小为\(n\)的背包，并且小Y有\(n\)种物品。对于第\(i\)种物品，共有\(i\)个可以使用，并且对于每一个\(i\)物品，体积均为\(i\)。求小Y把该背包装满的方案数为多少，答案对于\(23333333\)取模。定义两种不同的方案为：当且仅当至少存在一种物品的

Description有\(N\)个物品，编号分别为\(1\ldotsN\)。物品\(i\)的重量为\(w_i\)，价值为\(v_i\)。给出每个物品依赖于哪个物品。我们用\(d_i=j\(i>j>0)\)表示：如果要选取物品\(i\)，就必须先选取物品\(j\)。另外，我们用\(d_i=0(i>0)\)表示：该物品不依赖于任何物品。

前置知识时间戳在树的\(DFS\)中，以每个节点第一次被访问的顺序，依次给予\(N\)个点\(1-n\)的标记，通常用\(dfn[x]\)表示\(x\)号节点的时间戳。\(DFS\)序进行\(DFS\)时，对每个节点进入递归后以及回溯前各记录一次该点编号，最后产生\(2-n\)的序列即是\(DFS\)序，可设\(L[X]\)和\(R[X]\)

数据结构——线段树优化学习笔记比较基础，因此讲的很快。我们主要关注单点修改、区间查询的线段树，这是应用最广泛的。线段树问题我们以LOJ的这道题为例，例题：LOJ#130.树状数组1：单点修改，区间查询。洛谷上面也有类似的题：P3374【模板】树状数组1。因为洛谷的题的数据范

这道题是一道最短路径树问题。首先，什么是最短路径树呢？定义一个图的最短路径树表示一个图上的生成树，且根节点到图上任一点的距离等于原图上两者之间的距离。而不难发现，题目其实是在求图上最短路径树记数。首先，建出最短路径树。枚举每条边，判断边两个端点到根的距离之差是否为

搞了很久，题解区有线段树爆改pushup高妙做法说下cdq分治先将点都按横坐标从小到大排序，cdq分治，那我们现在只需要考虑分治过程中\([l,mid]\)和\([mid+1,r]\)互相形成的合法点对，显然左边的横坐标都小于右边的横坐标。能够发现，如果右边有一个点插在一对本来合法的点之间，那么那对合法

为了提高在线评测系统的功能性，需要选择和集成一个强大的代码纠错大模型，用于自动分析和纠正用户提交的代码中的错误。这里的大模型我们选择使用清华大学开源的ChatGLM-CodeGeeX2。在该模型的基础上，选用程序设计试题的专门数据，进行Fine-turning的训练（即微调）。为了令CodeGeeX在

有一道题LOJ没有，就没做了。LOJ#3774.「BalticOI2022Day1」ArtCollections注意到询问次数为$n$，我们希望每次确定一个数的位置。考虑增量法，前$i-1$次操作构建出$[1,i-1]$的排列，在第$i$次操作的时候插入$i$。首先询问$p={1,2,3,\dots,n-1,n}$，设返回值为$B_1$。

首先，不存在\(H_i<H_j\)时增高\(H_i\)至\(H_j+1\)后连\(i\toj\)更优，因为增高后原来能连\(i\)的点现在不一定能连\(i\)了，原来能连\(j\)的点还是能连\(j\)，此时的方案集必然是原方案集的子集，答案一定不会更优，又因为你付出了增高的费用，所以这样一定劣。那么我们

记事件\(A\)为「当\(s_i=\texttt<\)时\(p_i<p_{i+1}\)」，事件\(B\)为「当\(s_i=\texttt<\)时\(p_i<p_{i+1}\)，且存在\(s_j=\texttt>\)，满足\(p_i<p_{i+1}\)。所求即\(n(A)-n(B)\)。\(n(A)\)是好求的，相当于部分定序排列，记每个递增段的长度为\(a_1

\(\mu\)取值即所选边权的中位数。把每条边拆成两条（黑边和白边），边权分别为\(\mu-w_i\)和\(w_i-\mu\)，要求黑边和白边各选\(\left\lfloor\dfrac{n-1}2\right\rfloor\)条，求最大生成树。可以直接wqs二分，时间复杂度\(\mathcalO(nm\logw~\alpha(n))\)。把所有边的边权

裸的01BFS，时间复杂度\(\mathcalO(nm)\)。相邻的无障碍行可以缩成一行，列同理，所以全图的规模可以缩成\((k+1)\times(k+1)\)，再01BFS，时间复杂度\(\mathcalO(k^2)\)。进一步地，所有\(1\timest\)或\(t\times1\)大小的无障碍连通块均可缩成一个点，两个连通块相交，则

由题述，\(X\)满匹配，根据Hall定理，有对于任意一个有\(k\)个妹子的集合，她们能配对的男生的人数\(\gek\)。把每个妹子看作她所连接的两个（可能是同一个）男生间的无向边，则每个连通块必然是树或基环树。问题转化为给每条无向边定向，满足每个点的入度不超过\(1\)，求最大边权和。对

linkofproblem。依旧是非常精妙的做法呢！问了神仙lca才知道怎么做了，目前网上是没有题解的，有的只是一份带注释的代码的英文题解。我的细节实现也是看了这份代码得以补足的。我们定义一些量：原树重心为rt，rt的某个儿子叫做son，son子树内的某个节点为x。首先考虑哪些连通块

非常巧妙的转化。考虑仅计算半边的序列，那么这样的话\(len\)削了一半，要达成的色彩值也开平方了。问题就转化为，将\(l\)拆分为序列\(a\)，使得\(\sum_{i=1}^{n}(a_i+1)=l\)，且使得\(\prod_{i=1}^{n}a_i\geqk\)的最小\(l\)。经过一些计算，可以发现2的段不超过一个，3的段不

小声吐槽：如果不是拍了200000组没问题后瞪眼瞪出来了，我才不写呢Decribe:给定一棵\(n\)个节点的树，初始时该树的根为\(1\)号节点，每个节点有一个给定的权值。下面依次进行\(m\)个操作，操作分为如下五种类型：换根：将一个指定的节点设置为树的新根。修改路径权值：给定两个节点

Describe:\(n\)个点，\(m\)条边，每条边\(e\)有一个流量下界\(\text{lower}(e)\)和流量上界\(\text{upper}(e)\)，给定源点\(s\)与汇点\(t\)，求源点到汇点的最小流。Solution：首先因为仍然有流量的限制，第一步就是要找可行流。想到上题无源汇做法，尝试转换。上题中可行流实际

与ntt不同,处理fft的单位根要更加复杂,主要原因是考虑精度的问题.我们可以认为直接从三角函数计算出的单位根精度是最高的.当然由于\(\sin(x)\)和\(\cos(x)\)的渐进估计涉及到高次项,因此使用longdouble计算单位根再转成double是一点点意义的(如果longdouble精

平衡树的题能不打平衡树尽量别打，除非你闭着眼都能打对。Describe:维护一个多重集S，初始为空，有以下几种操作：把\(x\)加入\(S\)删除\(S\)中的一个\(x\)，保证删除的\(x\)一定存在求\(S\)中第\(k\)小求\(S\)中有多少个元素小于\(x\)求\(S\)中小于\(x\)的最