Count on a tree 题意:求路径 u到v上的 第k小的权重. 题解:先DFS建数, 然后对于每个节点往上跑出一颗主席树, 然后每次更新. 查询的时候, u, v, k, 找到 z = lca(u,v) , p = anc[z][0], 然后对于这条路上左边子节点的个数就可以被表示为u,v的树- z,p的树上的值. 然后主要是LCA不怎么用写搓了, 找了好久的bug. 汗. 代码: #include<bits/stdc++.h> using namespace std; #defi
1. 题目 2. 解答 字典序排数可以看做是第一层节点分别为 1-9 的十叉树,然后我们在树上找到第 K 小的数字即可.因此,我们需要分别统计以 1-9 为根节点的每个树的节点个数.如果 K 小于当前树的节点个数,那么第 K 小的数字即在当前树中,我们进入子树继续查找:如果 K 大于当前树的节点个数,那么我们需要查找后面树中第 (K - 当前树节点) 小的数字. 其中,比较关键的步骤就是统计树中的节点个数,我们按照逐层统计的方法来进行,详见下图. 首先我们初始化 cur = 1 然后我们让 le
Buy Tickets Time Limit: 4000MS Memory Limit: 65536K Total Submissions: 19012 Accepted: 9442 Description Railway tickets were difficult to buy around the Lunar New Year in China, so we must get up early and join a long queue… The Lunar New Year wa
http://www.lydsy.com/JudgeOnline/problem.php?id=3065 题意:带插入.修改的区间k小值在线查询.(原序列n<=35000, 询问<=175000) #include <bits/stdc++.h> using namespace std; const int nTr=1000005, nSg=15000005, alphaA=4, alphaB=5; int STop; struct Seg *Snull; struct Seg {