传送门 这道题其实就是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上面，同时...

传送门 你们搞的这道题啊，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...

传送门 先考虑一下暴力怎么打，对于每个时间，我们开一个vectorvectorvector，对于每一个任务，我们在[Si,Ei][S_i,E_i][Si​,Ei​]的vectorvectorvector里面都pushbackpushbackpushback一遍PiP_iPi​即可。 但是这样的暴力是愚蠢的暴力，考虑优化，我们在SiS_iSi​和Ei+1E_i+1Ei​+1的位置分别打上加入和...

传送门 一开始看到这道题，非常懵逼，不知道怎么做。 然后发现子弹是按照顺序发射的，于是转化一下题目条件，木板[Li,Ri][L_i,R_i][Li​,Ri​]会在接触到第SiS_iSi​个子弹时破掉，于是就转换成求[Li,Ri][L_i,R_i][Li​,Ri​]第SiS_iSi​大的子弹编号是多少。 这就是主席树模板嘛！ p.s.如果你懒（像我一样），不想把操作离线下来搞，就可以搞一下线段...

传送门 一眼看上去：这不就是最短路的模板吗？ 两眼：边权太大了，怎么开的下？ 考虑还是用Dijkstra\rm DijkstraDijkstra解决，每个点开一棵线段树，存储二进制的状态 我们要实现的功能: 1.给二进制数加上2k2^k2k，这可以看成把kkk位后所有连续的111变成0，再把所有连续111后的那一个000变成111 2.比较两个二进制数的大小，先比较高位，再比较低位。 但是用...

题目 传送门 一个长度为nnn的序列aaa，设其排过序之后为bbb，其中位数定义为b[n/2]b[n/2]b[n/2]，其中a,ba,ba,b从000开始标号,除法取下整。 给你一个长度为nnn的序列sss。 回答QQQ个这样的询问：sss的左端点在[a,b][a,b][a,b]之间,右端点在[c,d][c,d][c,d]之间的子序列中，最大的中位数。 其中a<b<c<d...