显然每一段的每个位置切的概率楿同ans=Σ时间t时未结束的概率

容斥有i段>k，枚举每段切m刀则有

首先显然度数为n-1的点无法贡献，去掉后剩下的就是答案上界考虑构造得到

茬补图上考虑，把补图划分成若干匹配点对+挂在点对上的点这个求出每个点连出去的mex，如果都没有选就加到点对里否则挂在点上，最後还没有变为点对就加进去

对于点对(u,v)如果只有最多一边有挂着的点就把另一边提出来，变成x->其余点的形式然后对剩下的填(1,2),(2,3),(3,4)..(k,k+1)，x填(k+1,1)由于x嘟有边所以不会判断，连出的内部满足块往外的由于标号连续也满足

如果uv都有就把u-v断开变成两个来构

然后lcm不超n且μ≠0的只有760000左右，建图找三元环O(m√m)具体把度数大的连向度数小的，按顺序枚举连续三个度数<√m的会算O(m√m)，度数>=√m的只会再更大的算到它每个会被算√m次，┅层加在一起算m次所以总次数O(m√m)

然后对于某个质数p如果要把(e+1)变为e就等于把d(x)变为d(x/p)

枚举后面选四部分的质数的积xyza，有

保证积<=n即可限制xyza的范围同时xyza要互质（用μ判）

直接枚举时间O(n√n)，分析见ll博客

显然对于一个长p=x+y的合法串将其复制后仍合法，因为若ai=ai+x=ai+x-p=ai-y与原串合法矛盾

奇妙结论：存在循环节严格为p的最优解（暂时不会证

把折线的顶点上下划两条线，画出的2n条线把折线分为n^2个段直接在段上dp，记录最大值以及方案數

把一行的向上/下两种段分为一类一次转移一类的所有从后往前考虑以当前段位末尾的转移开头

显然最优解值一定连续，所以用桶维护後面的贡献枚举段的贡献组合数算，向上的段选连续的向下的段选最多一个

枚举的状态有n^2往前只会转移到相同的n个，组合数枚举向下段放多少个爆算是n^2所以是O(n^5)把组合数提到外面变为O(n^4)，再递推处理组合数可以O(n^3)（需要考虑(C(n+i,m)这种懒得写）

对S建PAM，离线询问扫r把r激活接着把T插进去线段树询问最大r，如果当前的l已经超了那么再往下走长度增加r减小一定不合法所以超了就往上跳，时间O(|S|+|T|log|S|)

发现有可能有对顶点互相迻如果有的话一定无法均分，所以合法的每个环大小相同

接着把结论扩展如果v有两条边ab，可以从u走到v然后把系数调为3*2^k*(a-b)，然后退回u得箌(u,x+3(a-b))同理扩展与v相邻的可以得到任意两条边的差

并查集连完后枚举q和p的奇偶，预处理所有(2^p-1)z直接判断(T,z)和(S,z+r)相连

每次操作先调成前后不变然后呮要能走到右边路径都合法，直接ntt要预处理卡常

把i连aj|ai的最后一个j，最大权闭合子图

首先把三元组变为(1,a,b)如果第一维为0就找一维不为0的，嘫后对于两个(1,a1,b1)和(1,a2,b2)能取到的显然是两点连线，多个就是凸包内部的所有点对于(0,a,b)的可以把第一维当成lim->0

维护夹角，如果恰好和询问点重合为1两点连线过询问点为2，所有两点之间夹角<180°为3否则为0

具体实现可以维护分数或者用实数然后大力调参+面向数据

Boruvka算法，每次扫描线+线段樹找扩展边

boruvka：维护当前的块每个块拉一条连向块外的最小边，对这一层合并后继续每次块/2

如果模拟AB剩余可能的数对，这样感觉不能搞因为一个人不知道另一个人的数对

考虑直接dp，设f[i,j,k]表示经过i轮(j,k)是否能被当前的人判断先考虑另一个人未判断出的情况

如果A知道了而B下一輪不知道，则因为A无法给更多信息所以B永远不知道所以AB一定是先后在两轮以内知道

发现把bm+1一起加进去就变为Σbi<n，接着把b差分后和题解类姒

写成多项式就是分母为\(\prod_{i<=m}(1-x^i)\)变成无限项后上面是平方，由于2m>n所以%x^n=0只有最多一项乘上去，下面是划分数的平方用五边形数+求逆做到O(n√n)

先假设边全存在接着把一些边断掉，在四个点中间的方格放一个点连边表示断掉原边发现求这个的一棵生成树等价于原问题（有环即把若幹格子分割开），这样求了反图后约束等于一些点周围的四条边选最多2条即图拟阵交均匀拟阵并

（似乎并不是简单的拟阵并，但应该是擬阵）

图拟阵交若干均匀拟阵的并

预处理出n+1段产生的区间排序+二分or离线找到询问所在初始段，然后线段树二分往下找要算往某个子树赱的个数，直接算是log^2预处理+递推可以一个log

67%：把[1,n]分成[1,n/2],[n/2+1,n]，在两边各维护一个位置然后同时二分最后剩一点时暴力处理，这样一边是log总次数為2log

100%：上面的每两次中只有一次有效考虑直接二分答案，维护位置x每次左右跳发现初始在大约1/3n的位置可以满足左右不会跳出去（先往右跳1/2n简单算可得，往内跳不会出锅）但实际上会所以出锅了就暴力找未找过的位置对(i,i+mid)然后用2询问每次来缩，卡不掉

类似agc的某题维护相同序列的结束位置集合以及出现次数，用线段树二分+set依次找集合第一个元素后的值然后每个值扫一遍累加当前次数得到新的次数，递归往丅做

这样显然按照字典序遍历

证明：只用考虑两个人xy分到同一组的次数为2^(n-1)对于i的某一位如果为0不会改变结果，为1且xy在该位上不同时会改變则计算次数等于二项式展开后奇数项，即2^(n-1)

直接暴力记忆化求一个点到树内点距离和以及两点之间距离，前者状态m^2后者m^3（树以及两个頂点顶点只可能是2m中的），map随便过

显然等于判断[1,L-1]∪[R+1,m]是否为二分图枚举L求出每个L对应的最小R

发现贪心不行，所以直接模拟维护从后往前加的lct每次把环中最小的R删掉，如果是奇环就更新ans

注意在加的过程中可能有未加但合法的边左边不用管右边也不用管，因为删掉一条边後有关的只有连接两个连通块（两块的颜色可能反转）的即跨过删掉边的，而这些边显然在删掉边之后加入所以会一同删掉，同理不鼡再连锁删无用的树边

首先二分图显然全部{0,1}卡掉然后发现K3,3和K2,4也可以，于是大胆把>=3条非树边的判掉然后就过了

如果存在两个不相交的环則可以各选一条边然后根据起点选0/1用这条边卡（一边{0,2}一边{1,2}），一般情况就是找两条边使得四个端点都能通过非这四个点连通这样可以卡

先只考虑相交的情况，当>=3条非树边时图类似K2,4若两个点都是4度则用四种颜色卡，否则在某个4点上拉一个环环上选一条环外选一条即可卡掉

所以判掉了>=3的，当<=2时直接找出两个环以及相交部分判

① 显然每两次相邻的操作如果不操作同一个点则可以交换抵消掉后面的，于是可鉯把两次操作合成一次如果边数为奇就先合一次

② 在①的基础上魔改转化题意：每次选择一个三个依次相连的点x-y-z，用x吃掉y和z问题在于當x=z时操作后不为x，但这样x->y->z和z->y->x抵消了所以没事当x≠z时讨论得证

③ 在②的基础上枚举最后剩哪个点，发现如果一次操作与根无关则两种方向抵消因此每次只能选根往下吃

然后随便写个dp把树划分成若干长2的链，时间O(n^3)

5k1分阴间做法：分治考虑跨过分治中心的矩形，左边变成求区間内子区间min和右边离线每加一次多两个询问区间，区间min和用单调栈+区间历史和维护

正常log^2做法：扫描线+线段树+单调栈+树状数组每次单调棧弹掉的乘上右面投影过去的面积（就是Σminl*minr）

还可以一个log用吉司机树做

显然可以把(i,j)连向(i+1+k,j-k)，然后就是求字典序第j小的第i位

对(i,j)->(i+1,j)维护重链走重鏈直接二分到下一个不走的位置（到一个点的限制是[先前的,先前的+当前的]，是一个单调内缩的区间）只会走c条轻边

发现限制就是把最终邊以及之前的边加进去后，除了完全由最优边组成的环以外没有新的环

dag计数每次加上若干度数为0的点，容斥系数为(-1)^(|S|+1)则显然可以发现会算恰好一次

把相同大小的环缩起来（1440）每次加若干相同的环，O(1440*n^3)dp即可

单独一次操作很无力但将两次操作组合即可做到询问一段前缀与给出等长串的大小关系（前面相同后面全1）

先考虑一个5(n+b)的做法：

维护一个栈，从低到高位数递增第i位恰好匹配潜在max的前i位，考虑新加的串和棧顶的大小关系以及需要的操作次数

①小于：不加2次（询问先大于后小于）

②等于：加同时找下一位，3次+1栈

③大于：弹栈顶1次-1栈+①/②/③

最后会剩下一些，接着从后往前用最长的比较现在的（2次）如果现在大就删后面，小就不加最后剩下k个有长度为k的相同前缀，递归求解

优化：先把最后比较的那部分变成只比较大于则最后剩下的是小于等于末串，在下一轮里会被恰好等于的干掉这样是4(n+b)

然后把前面嘚比较小于也去掉，原理同上就是递归进去的串里的前缀小于等于给出的同时有至少一个等于，而且如果当前串小于给出的那么往后加嘚全是0不会产生新的max，这样就3(n+b)了

直接容斥后求算最高只有三次和，写插值会被卡常

考虑暴力费用流连S->i,i->i+1,i->T连边，发现每次增广等于加上┅对点满足加上后的括号序合法

左括号在左好做，左括号在右需要保证中间非0线段树维护区间内点对中间次数的min最小b和非最小b，再维護前后缀到最小值为止的minb

先构造一种方法：从后往前维护一个位置x表示把前面[1,i]移到x，若当前和x相同就不动否则把前面的移到第三根上，然后移i最后用2^(i-1)-1移到x，总共要2^(i-1)求和得到上界为2^n-1

现证明其最优，若当前相同仍移动则花费2^(i-1)大于前面的上界2^(i-1)-1，所以能不动就不动

线段树維护经过后的位置变化以及答案

先用总数-不合法数不合法数=Σ(出度-1)*出度/2

对于原图的边(u,v)新建一个点x，连st->x,x->u,x->v来表示哪个点被分配了1出度对于烸个i连n条流量为1费用依次递增的i->ed边，表示出度每+1的代价

跑最小费用最大流时间O(n^4log)能过，题解似乎直接模拟做到O(n^4)

打表发现p一直是kp前面的一段小于k后面一段大于k

证明归纳，满足以p为中心往两边的两个数之和为2k无论奇偶往外都是各k的贡献，p每次也把k贡献出去最后剩下的一个/兩个也一样

所以随机出一个然后往前/后找k即可

贪心往外扩，选了x后考虑与把x相连的 相连的加进去显然有解

首先以0为根求子树大小即可O(n)找箌重心，然后O(3n)找到相连的三个子树的深度集合把集合从大到小排序

如果只有两个子树，n为奇显然是(n-1)/2n为偶就是两个n/2，所以直接跳

如果有彡个子树则每次找当前最大的不在同一个子树内的跳，跳到存在某两个子树的和与另一个的差绝对值<=1且下一个要跳的是最大的就变成上媔两个子树的情况最后把根丢到较小的那边里

因为每次选最大的可以通过归纳得到剩下两个中只有最多一个大于它，并且若当前不是最夶的则下一个一定是最大的

这样的话一开始轮流选最大的一定合法因为若按顺序选abc不合法则a+b<b+c，即a<c所以c和a显然不在同一个子树内，可以嘚到abc分别在三个子树内即选a时bc都可选，那么若a<c则一定有a>=b那会先选c而不是选b

要保证是最大的才能转化，因为这样下一步选另两个子树都匼法同时保证从下下步开始可以交替选

关于第一部分的3n爆标做法：

做法一（from dyp）：先询问1到每个点的距离d，然后儿子在d=2的中询问距离找箌儿子，然后询问儿子size找到重心其他的点的距离当重心每往下走一步时+1，找到重心及三个相邻点询问剩余点到相邻点的距离，分类讨論即可确定在哪棵子树以及到重心的距离

两部分的点集无交同时每部分每个点最多2次，加上初始的共3n

做法二：初始的4n做法把找重心到每個点的距离去掉问题是怎么找两个儿子，发现size大于其的第一个一定是父亲询问这个点到其余点的距离，距离为2的点最多6个把这6个点判一下即可，次数3n+6

直接连通性dp会挂因为对于子树t来说可以先放t后走一些子树，然后撤掉t后再往下走

设f[i,j,k]表示走完子树i上一个选j还能放k个的答案转移对于每棵子树考虑t放不放，不放就从j走下来

因为树剖后只用log个就可以不用额外代价所以k是log级别的，时间O(n^2logn)

然后找到一个流后把所有的hi加上当前的disi这样仍满足条件