传送门 首先考虑暴力的做法，不要把注意力放在字串上面，考虑Sl1Sl1+1Sl1+2⋯Sr1==Sl2Sl2+1Sl2+2⋯Sr2S_{l_1}S_{l_1+1}S_{l_1+2} \cdots S_{r_1} == S_{l_2}S_{l_2+1}S_{l_2+2} \cdots S_{r_2}Sl1​​Sl1​+1​Sl1​+2​⋯Sr1​​==Sl2​​Sl2​+1​Sl2​+2​⋯S...

传送门 本题暴力： 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869#include <bits/stdc++.h>#define MAXN 200005using nam...

传送门 这道题其实就是P4185 [USACO18JAN]MooTube和P3224 [HNOI2012]永无乡的结合。 看到第kkk高，就要想到主席树，但是考虑到题目条件：只经过困难值小于等于x的路径，于是考虑离线操作，把询问和边按照边权从小到大排序，来了一个边权为xxx的询问，只要把$ \le x$的边全部连上，同时合并两个连通块所代表的主席树即可。 代码： 12345678910111...

查询第kkk大/小，首先想到主席树，每棵主席树记录当前节点到根节点的路径上面的所有值，每次查询u,vu,vu,v，我们使用第u,v,LCA(u,v),fa[LCA(u,v)]u,v,LCA(u,v),fa[LCA(u,v)]u,v,LCA(u,v),fa[LCA(u,v)]棵主席树，做一次差分即可。 主要是如何实现连边，最暴力的方式是把yyy所在的联通块的节点全部一个一个连到xxx上面，同时...

传送门 注意到一个性质，如果加入的边<u,v><u,v><u,v>已经在连通块里面，发现连通块任意两点都是联通的，于是加入边并不会对答案有任何影响，我们就不加入这一条边。 于是发现这张图在任意时刻都是一个森林，森林就比较好办，考虑记录加入边的时间tim[]tim[]tim[]，于是答案即是max⁡{tim[w],w∈route(u,v)}\max\{ ti...

传送门 并查集+二分答案，假设现在二分到midmidmid这个值，把距离小于midmidmid的奶牛全部连边，看看最后是不是只剩一个集合。 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465#inclu...

传送门 这题其实有两种做法： 1.1.1. 我一开始想到的是二分加并查集，考虑二分最近部落的距离，如果两点iii，jjj距离小于等于midmidmid那么连边，并查集维护，最后统计有多少集合。 考虑如何证明单调性：如果两点iii，jjj在mid1mid1mid1情况下能连边，那么在mid2mid2mid2情况下也能连边（mid2>mid1mid2>mid1mid2>mid1...