暴力操作（opt）30pts这个错解可反悔贪心30pts；考虑正解，我们只需考虑前$\fracn2+1$小的数即可；考虑二分出一个中位数$mid$，那么我们要让大于它的都用最小的代价变小；考虑如何求这个最小的代价，因为$\lfloor\frac{\lfloor\fracab\rfloor}{c}\rfloor=\lfloor\frac{ab

A暴力操作（opt）B异或连通（xor）C诡异键盘（keyboard）D民主投票（election）这道题很简单。。。首先，对于一个节点\(u\)，如果\(siz[u]-1\)大于了其他所有节点能得到的最大值，那么它一定能胜利。那考虑怎么找到一个值，满足所有节点能得到的最大值最小？用二分答案即可。对于一次

南开高级语言程序设计2-1的oj题目答案，本人亲测AC，供大家参考。2-2的见主页字符串旋转题目描述定义字符串的旋转操作为：左旋转L:把字符串前面的若干个字符移动到字符串的尾部，如把字符串abcdef左旋转2位得到字符串cdefab。右旋转R:把字符串后面的若干个字符移动到字符串的头

Rank反向挂分大王A.暴力操作（opt）签，但是没有人签。都想到了二分和更新c值，但是c多多少少没更到最优。首先还是调和级数预处理，倒序取min。然后考虑到超过\(m\)的也有可能产生更小的代价，因此\(\mathcal{O(n)}\)枚举一遍找到最小的\(j\)使\(i\timesj\gtm\)，全部赋

喜欢每个包绑一个hack是吧。暴力操作（opt）容易发现答案具有单调性，考虑二分答案。还发现只需要处理\(1\sim\left\lceil\frac{n}{2}\right\rceil\)即可。发现如果\(c_{i}>c_{j}且i<j\)，那么选\(j\)肯定更优。有\(\left\lfloor\frac{a}{bc}\right\rfloor=\left\lfloor\frac{\left\l

题目大意有\(n\)个点，点有点权，维护一个完全持久化的数据结构并支持：将点\(x\)和\(y\)之间连接一条边。询问点\(x\)所在的连通块的第\(k\)小权值。数据范围：\(1\len,q\le10^5,0\lea_i\le10^9\)。时间限制：500ms，空间限制：20MB思路写一种比较简单的做法。先不考

全局平衡二叉树(GBST)小记以下全局平衡二叉树简称\(\text{GBST(GlobelBalancedSearchTree)}\)。我认识的大多数人，对\(\text{GBST}\)的理解基本上都是静态\(\text{LCT}\)，或者静态\(\text{TopTree}\)，不过我对\(\text{LCT}\)的理解可能还差一点，所以我不打算从阉割\(

这种问题一看满足条件就知道，一般不用想着怎么模拟题意。考虑转化问题。假如节点\(u\)满足了条件一，也就是仅有子树节点全部开启。那么我们把转化具象为：进行\(\text{siz}_u\)次操作直接清空；进行\(\text{siz}_{\text{fa}(u)}-\text{siz}_u\)次操作使\(\text{fa}(u)\)满足

暴力错解大赛玩游戏82pts乱糊的错解，正确性和时间复杂度都不对，但是拿了82pts；对于正解，考虑从$k$将原序列分成两个部分，左边和右边，然后分别求一次前缀和（注意这里，可以省去很多分讨和常数），设前一个前缀和数组为$a$，后一个为$b$，那么问题就转化成有两个指针$i,j$，可以任

模拟赛题，不知道为什么放在最后一题，感觉评分过高了。首先是经典问题，最大值是\(\sum\min(siz,n-siz)\)，证明考虑每条边上界。考虑证明的构造，对于重心的每个儿子拉出子树，求出子树大小即可转为序列上问题：每个点不跟内部匹配即可满足最大，容易证明充要。朴素dp发现怎么也避不开两

P4178Tree题目描述：给定一棵n个节点的树，每条边有边权，求出树上两点距离小于等于k的点对数量。数据范围：\(1≤n≤4×10^4\)\(1≤k≤2×10^4\)说句闲话感谢著名CB大师red_fire倾情推荐%%%在机房三个人唇枪舌剑了一小会，我们的CB大师直接开搞线段树，而仔细研读了数据范围的本

思路首先可以发现这个期望其实是假的，我们只需要把所有方案的答案加起来，最后除以\((\frac{n(n-1)}{2})^2\)即可，现在考虑如何统计所有方案的答案。我们先考虑一条路径的方案数：假设存在一条从\(x\)到\(y\)的公共路径，其中\(x\)是\(y\)的祖先，那么小红和小蓝分别选择的路径，

Splay技巧/记忆点：1、Rotate()中，使用变量记录位置关系和下标；2、Find()（找元素\(x\)所在位置）减少重复代码；3、求前驱/后继时先把这个数插进去再删掉；4、Splay()父子同侧先翻父亲，再翻儿子，否则翻两边儿子；5、siz[]在Splay()前先Pushup()到树根，这样在Rotate()维护会轻松一点；6、Delet

洛谷题目传送门博客园可能食用更佳题目大意：给定一棵权值为\(0\)或\(1\)的树，\(n\)个点，\(q\)次操作：0i把结点\(i\)的权值取反；1ij询问点\(i\)到点\(j\)的最短路径上权值是否全为\(0\)或全为\(1\)。题目分析：树上操作，看了下操作发现是树剖板子题。开

source：zr2024二十联测http://zhengruioi.com/contest/1717/problem/3061题意给定一棵以\(1\)为根的树，树边有两种形态：实边和虚边。初始这棵树的所有边都为虚边。定义assert(x)操作为：对于根到\(x\)上所有点，将其与所有儿子的连边置为虚边，然后给根到\(x\)这条链上的边置

原题链接：https://www.luogu.com.cn/problem/P3369题意解读：平衡树的基本操作，模版题。解题思路：1、二叉搜索树-BST二叉搜索树满足这样的性质：每一个节点的权值大于它的左儿子，小于它的右儿子。对BST进行中序遍历，将得到一个从小到大的有序序列，因此BST是为了维护一个有序序列的动态

多校A层冲刺NOIP2024模拟赛16T1四舍五入签到题注意到一个数是否会入上去只和其剩余系有关，即满足\(i\modj<\frac{1}{2}j\)，会入上去，考虑枚举j的倍数，其贡献就成了一个区间，差分即可。时间复杂度是调和级数的，为\(O(n\lnn)\)。T2填算符贪心，特殊性质显然将所有\(\&\)放

说句闲话这个东西已经20多天没写了，感觉已经忘没了，非常糟糕，只好赶快补一补，确实还是得多打代码，不然都忘光就丸辣。前言树链问题通常是关于树上路径的操作，将路径拆分成一条条链，然后用线段树维护链的权值。注：本题解并不适用于毫无基础的oier，只是做简单讲解，想了解具体定义请自行查

一、前言&基本理论来自笔者的肯定：最容易理解且比较好写的平衡树（不过就是常数有点大了），可能是笔者花了较长的时间去理解旋转Treap和Splay的旋转吧（）。FHQ不仅比旋转法编码简单，而且能用于区间翻转、移动、持久化等场合。——《算法竞赛》FHQ_Treap的所有操作都只用到了分

简述题面：你有两棵树，\(T_1\)，\(T_2\)，然后你需要对于每个点求出\(\min_{j\not=i}(dist(T_1,i,j)+dist(T_2,i,j))\)要求时间复杂度\(O(n\log^2n)\)或更优做法：考虑点分治，假如在\(T_1\)固定\(i,j\)一定要经过某个\(x\)，然后把\(x\)作为分治点，那么实际上\(val[i,j]=

mt19937rnd(time(0));structFHQtreap{ intlc[N],rc[N],val[N],key[N],siz[N],pool,root; intcreate(intx){ intp=++pool; val[p]=x; siz[p]=1; key[p]=rnd(); lc[p]=rc[p]=0; returnp; } voidupdate(intp){ if(!p)return; siz[p]=siz[lc[p]]+si

静态邻域数颜色-题目-ZhengruiOnlineJudge题目描述静态树上邻域数颜色。给一棵\(n\)个点的无根树，第\(i\)个点颜色为\(a_i\)。有\(q\)次询问，每次询问如下：给定\(x,d\)，考虑所有距离\(x\)不超过\(d\)的点，求有多少种不同的颜色。形式化地，给定\(x,d\)，求\(|\{a

什么是树的重心？树上选取一个点，使得最大的子树大小最小的点叫做重心。重心有很多优美的性质，求重心是容易的，不再阐述。1.以重心为树根时，最大的子树的大小不超过全树大小的一半，同时条件是充要的对于充分性：考虑调整法。不妨现在钦定一个重心\(u\)作为树根，有一个儿子\(v\)且

先挂一张jijidawang的图所以学这玩意就是被TopTree薄纱的有人把这玩意叫静态的LCT，然而可能只需要一些LCT的知识，并不需要会LCT。起码我不会注意这叫GBT，不叫GPT，能聊天的那个是CatGPT，不是CatGBT。前置知识：树链剖分用途\(O(\logn)\)处理树上链修改、链查询、子树修改、子树查