传送门 强烈谴责出题者，题面都花了好几分钟读。 题意： 给你Ai\\{ A_i\\}Ai​，让你从集合S={x∣x=∑k=ijA[k],j−i+1∈[L,R]}S=\{x|x= \sum _{k=i} ^{j} A[k] , j-i+1 \in[L,R] \}S={x∣x=∑k=ij​A[k],j−i+1∈[L,R]}选出kkk个数，使他们的和尽可能大。 首先考虑一件事，如何表示[i,j]...

传送门 首先考虑暴力的做法，不要把注意力放在字串上面，考虑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...

传送门 如果是一条链，我们将这条链从111节点提起来，显然我们不能选择同时选择左半部分或者右半部分的两个点放在一组，于是我们有如下思路：左半部分的点和右半部分的点两两配对，剩下的点（包括111）自成一组。 考虑如何使结果最小，肯定是左半部分最大值和右半部分最大值配对，第二大值互相配对，第三大值互相配对…… 正确性怎么证明，考虑我们把x1,y1x_1,y_1x1​,y1​和x2,y2x_2,y...

传送门 考虑离线+差分。 将∑l≤i≤rdep[LCA(i,z)]\sum _{l \le i \le r} dep[LCA(i,z)]∑l≤i≤r​dep[LCA(i,z)]转化成∑1≤i≤rdep[LCA(i,z)]−∑1≤i≤l−1dep[LCA(i,z)]\sum _{1 \le i \le r} dep[LCA(i,z)]-\sum _{1 \le i \le l-1} dep[L...

传送门 你们搞的这道题啊，exciting。 首先，看到标题我们就知道用什么算法实现，于是我们使用主席树。 容易发现，a,ba,ba,b和ccc都在同一条到根节点的链上面，而且ccc是这条链最下面的节点，但是a,ba,ba,b关系未知。 于是分类讨论： 1.b∈anc(a)1.b \in anc(a)1.b∈anc(a)，发现c∈subtree(a),dis(a,b)≤kc \in subt...

传送门 考虑预处理出szszsz数组，表示子树的大小，处理出来val[u]val[u]val[u]数组，表示uuu的子树里面的所有奶牛到uuu集合的不方便度。 于是dpdpdp就十分简单，初始化dp[1]=val[1]dp[1]=val[1]dp[1]=val[1]，然后考虑集合地点从uuu变到vvv，vvv子树里面的所有奶牛都会少走www路程，而剩下奶牛都会都走www路程。 1234567...