**P3377【模版】左偏树/可并堆**#include<bits/stdc++.h>usingnamespacestd;constintN=1e5+10;intn,m;structHeap{ intls,rs; intdist,val,fa;}tr[N];intfifa(intx){ returntr[x].fa==x?x:tr[x].fa=fifa(tr[x].fa);}intmerge(int

定义1：删去该点后最大子树最小的点定义2：删去该点后所有子树大小均不超过n/2的点两个定义是等价的。如果一个点有超过n/2的子树，那么往这个方向走一步，其最大子树会变小。性质：一棵树最多有2个重心且相邻重心到所有点距离和最小可以用调整法证明（相当于换根），P2986[USACO1

前言题目链接：洛谷；AtCoder。题意简述给你一个\(n\timesm\)的矩形\(a\)，其中已经有\(q\)个位置填上了数，你需要为剩下的位置分别填上一个非负整数，使得最终任意一个\(2\times2\)的子矩形内，左上角的数加右下角的数等于右上角的数加左下角的数，即\(\foralli\in[1,n),j\in

起因：cjx暑假集训的时候出了道题，老师说可以点分治。但是我最初的想法其实是换根处理，但怎么想发现都行不通，因为要同时维护DFS序和权值。于是就没想了。后来10.5和xyh进行长达30s的讨论导游的工作那题，说了我这个想法，xyh觉得有道理，对要求解的问题具体化，于是我才想出了分块

CodeforcesRound987(Div.2)总结A常见的套路，将一个序列变为不下降序列所需要改变的值的最小数量，考虑最大能保留多少个，显然是求最长上升子序列，而这题给出的\(a\)序列保证不上升，所以只需要考虑相同长度的一段。#include<iostream>#include<cstdio>#include<cstring>#

P6628[省选联考2020B卷]丁香之路题解首先考虑题目中路径权值的含义：\(i,j\)两点之间的最短路就是\(|i-j|\)直接连边。题目要求从\(s\)遍历到每个点，到终点每个\(x\)的最短时间。于是我们不妨枚举每个\(x\)，考虑在\(O(n)\)至\(O(n\logn)\)的时间复杂度里解决问题

[Ynoi2018]未来日记老早之前就想写了，人生中第一道大分块，调了一上午+下午一个小时，对拍了不知道多少万组，终于过了。\[\Huge{本题不卡常本题不卡常本题不卡常本题不卡常本题不卡常本题不卡常本题不卡常}\]\[\Huge{快来写快来写快来写快来写快来写快来写快来写快来写快来写快来写

一些近期的模拟赛，被暴打。9.18D超级无敌线段树题目。给出\(n\)个\(a_i,b_i\)，然后\(q\)组询问。每组询问给出\(l,r,x\)。然后令\(i=l\)，一直做到\(r\)。若\(x>a_i\)，则\(x\getsx+b_i\)。暴力送你\(10\\texttt{pts}\)，然后离线的话有\(50\\texttt{pts}\)。离

图论系列：前言：相关题单：戳我算法讲解：戳我CF1829ETheLakes给定一张\(n*m\)的矩阵，询问正整数四联通块权值和的最大值。并查集维护即可，记录一下集合内的点的权值和。代码：constintM=1005;intT,n,m,ans;inta[M][M],fa[M*M],siz[M*M];intfx[5]={0,1,-1,0,0};intfy[5]

题意求对于所有的\(i\)满足\(|P_i-i|\neqk\)，的排列数量，对\(924844033\)取模。\(2\len\le2\times10^3,1\lek\len-1\)。Sol考虑转成\(n\timesn\)的网格图，那么就是所有\((i,i+k)\)以及\((i,i-k)\)的格子涂黑不能用。题意转化为在网格图里

图论系列：前言：相关题单：戳我算法讲解：戳我代码可能过多啊，到时候页面别卡死了，所以就把代码最前面的缺省源删了（反正就是几个头文件/defineintlonglong，自己加一下即可）。并查集记得初始化，最小生成树记得排序。P3367【模板】并查集板子题，给定\(n\)个元素，有2种操作，一种合并，

多校A层冲刺NOIP2024模拟赛20昨天晚上打ABC了，所以今天才发。T1星际联邦直接上菠萝（Borůvka）算法就行了，当然还可以用线段树优化prim算法，但是没打过只是口胡：就是维护当前的连通块，但一个点$i$加入连通块时，后面那些点就可以有$a_j-a_i$的贡献，前面的点可以有$a_i-

图论系列：前言：咲いた野の花よああどうか教えておくれ人は何故傷つけあって争うのでしょう相关题单：题单1题单2题单3题单4一.并查集1.基础定义与操作（1）定义并查集是一种用于管理元素所属集合的数据结构，实现为一个森林，其中每棵树表示一个集合，树中的节点表示对应集合中的

注意可能出现dpx+1在模意义下为0的情况，此时需要额外维护0的个数而不能求逆元记f[x]表示x子树内包含x的连通子图的个数，g[x]表示全树包含x的连通子图的个数，由于子树的限制，所有fx互斥【子树互斥模型】求出f[x]后换根DP求出g[x]。答案即为u-LCA(u,v)上f的和+g[LCA(u,v)]+v-LCA(u,v

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

题意给出\(n\)个集合\(S_1\cdotsS_n\)，\(S_i=\{a_i\}\)，每次给出\(x,y\)，将第\(x\)和第\(y\)个元素所在的集合的最大值\(\div2\)，合并两个集合，然后输出新集合的最大值。sol每次求出两个集合，记录两个集合的最大值并删除，将两个集合与两个最大值除以\(2\)后合并即可。

题意给定一颗树，每个点有权值\(1\)和\(-1\)，称一条路径是好的当且仅当路径上所有点的权值和为\(0\)。求连续编号区间\([l,r]\)使得两个点都在\([l,r]\)的好路径比两个点都不在\([l,r]\)的好路径数严格多的方案数。\(n\le10^5\)。Sol两个端点都在区间内不好做，

题意原题链接维护一个数据结构，要求支持合并集合或删除集合最小值并输出。sol双倍经验，同[luoguP3377]左偏树/可并堆代码#include<iostream>#include<algorithm>#include<cstring>usingnamespacestd;constintN=1000005;structNode{intl,r;int

对于操作:将一段元素合并为同类。在合并\([l,r]\)这一段数的时候，其实有很多数本来就在一个并查集里。我们只需要合并若干个还没有合并的并查集，而不需要从\(l\)到\(r\)一个一个合并。因为只要合并了这几个并查集，效果等价于把\([l,r]\)直接合并了。实现方法：每次记录一个

新的阶乘考虑从这个式子下手，怎么更优秀的求得答案。\[\begin{aligned}f(x)&=x_1\times(x-1)^2\times(x-2)^3...2^{x-1}\times1^x\\&=\prod_{k=0}^{x-1}(x-k)^{k+1}\\&=x!\times\prod_{k=0}^{x-2}(x-1-k)^{k+1}\\&=x!\timesf(x-1)\\&=\prod_{k=1}

背景4.14打abc的时候一眼e题是换根模板，但是我不会，于是就来补档了。什么是树形dp/换根dp一种在树上的dp，一般用dfs进行状态转移。树形dp一般用儿子来更新父亲的答案。换根dp一般在第二次dfs时用父亲的答案转移到儿子去。引入经典树形dp例题：没有上司的舞

flandre做得挺久的，大约做了\(\rm1h+\)。首先，选出来的序列一定是升序的，因为交换升序序列中的任意两个都不可能让「感觉效果」更高。然后来看选那些数组成这个序列。接下来是我赛时的想法：如果全为正数，那么自然正数全部都得选。需要考虑的是负数的情况。首先，选择一个负数不仅

前置知识：Splay和文艺平衡树介绍LinkCutTree，简称LCT，时间复杂度分析细节原splay函数Rotate()中，注意son[z][]的赋值要有限制语句isroot(y)，因为z可能是“认父亲不认儿子”的splay根节点的父亲（Splay()中的限制管不到，因为Splay()只考虑父亲，但Rotate()要考虑爷爷）voidRotate(int