搞了很久，题解区有线段树爆改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\)的最

DescriptionJOI君所居住的IOI市以一年四季都十分炎热著称。IOI市被分成\(H\)行，每行包含\(W\)块区域。每个区域都是建筑物、原野、墙壁之一。IOI市有\(P\)个区域是建筑物，坐标分别为\((A_1,B_1),\)\((A_2,B_2),\)\(\ldots,\)\((A_P,B_P)\)。JOI君只能进入建

题目哈希记录每个\(k\)长度的串，询问的时候可以拿主席树或二分，这里说下二分。将\(n-k+1\)个串从小到大排序，以哈希值为第一关键字，序号为第二关键字。每次询问直接查找大于等于当前哈希值的位置即可，找到之后判断一下合不合法即可。具体看代码：#include<bits/stdc++.h>typede

恶魔的低语，会送来天堂的福音。题意有一个\(n\)个点的有向无环图，第\(i\)（\(1\lei\len\)）个点有mi条有序的出边\(e_{i,1},e_{i,2},...,e_{i,m_i}\)。每个点要么是黑点，要么是白点。有\(k\)个程序，第\(i\)个程序形如从\(r_i\)开始，对\(r_i\)的直接或间接后继

题面传送门什么缝合怪（以下默认判掉一步走到。Section1:P容易发现不会改变纵坐标，简单判断即可。Section2:R两步，两种方案。Section3:Q因为\(n\geqm\)，所以直走两种方案，先斜着走再竖着走两种方案是一定有的。以下默认其先往左下走，往右下走翻转再做一遍就好了。如果

\(LOJ\10115\).「一本通4.1例3」校门外的树一、题目描述校门外有很多树，学校决定在某个时刻在某一段种上一种树，保证任一时刻不会出现两段相同种类的树，现有两种操作：\(K=1\)，读入\(l,r\)表示在\(l\)到\(r\)之间种上一种树，每次操作种的树的种类都不同；\(K=2\)，读入\(l,

给定\(n\)个物品，第\(i\)个物品有体积\(c_i\)，价值\(v_i\)。给定\(K\)，对\(1\simK\)的所有\(i\)求大小为\(i\)的背包的最大价值。\(n\leq10^6\)，\(K\leq5\times10^4\)，\(c_i\leq300\)，\(0\leqv_i\leq10^9\)，时限\(\text{2.0s}\)。注意到\(c_i\)范

真的卡不动了，但是我感觉我的思路还是有一些价值的，就来写一篇题解吧。考虑使用回滚莫队（不增）来维护，当区间删去一个点时相当于全局加入一条边，这个询问的本质是询问是否是二分图，所以考虑扩展值域并查集，这里使用路径压缩加按秩合并，记录下修改，在回滚时全部还原。总复杂度是\(O(n\sqr

link思维+容斥计数。首先的转化比较妙，二分图转化为\(n\timesn\)的网格图染色。与网络流的转化方向相反，值得注意。然后发现两种颜色（红、蓝）如果独立染色，同一个格子可能会重复染色。考虑容斥，式子很好列，直接容斥即可。\[ans=\sum\limits_{i=0}^n(-1)^n\times\binom{n}{i

LOJ#10132异象石题目简述：支持对树上一点集删单点和加单点的操作，询问点集组成的虚树的边权之和（虚树边权为原树上两点间距离）。做法：考虑给定点集答案的求法，将其中的点按dfs序排序，使dfs序从小到大的点依次相邻，同时使dfs序最大和最小的相邻，构成一个环。环上相邻点的距离就是答案。

2023.7.3ProblemLink交互库有一棵\(n\)个点的二叉树，你每次可以询问两个点之间的距离，猜出这棵二叉树。\(n\le3000\)，询问次数上限\(30000\)。首先给你距离一定是先把每个点的深度问出来，确定一个大致的考虑顺序。然后我们开始仔细思考“距离”这个条件怎么用。发现询问两个

这道题恶心之处在于区间向下取整。这里给出两种思路：区间覆盖做法如果最大值和最小值向下取整后相等，则对此区间进行区间覆盖。我考场写的是这个，但是码错了，加上习惯不好,\(100\to64\),再加上烦了弱智错误，\(64\to9\)，不给出代码。差值相等做法注意到相邻两数的向下取整的差值不