标签 - 线段树合并

? 解题记录 ? ? LOJ ? ? 线段树合并 ? ? 动态规划 ?    2018-12-05 19:28:45    487    0    0
题目链接:https://loj.ac/problem/2537 考虑到题目是一颗二叉树,有一个简单的O(N^2)的DP做法。f(i,j)表示i号点取值为数集中第j大数的概率,每一次我们从子树合并上来。j被取到有两种情况:j更大并且当前选择的是最大值 j更小并且当前选择的是最小值分情况讨论,发现要转移需要一个选到比j小的值的概率和(比j大的可以直接用1减比j小的)。那么我们维护两个前缀和(对两边的元素分别计算),即可完成一次合并。 如何优化这个算法呢?假设两边子树可以产生的j值集合分别为A,B。考虑A值域上这样连续的一段数:满足不存在B[i]使得A[l]<=B[i]<=A
【题目描述】给定一棵n个点的有根树,编号依次为1到n,其中1号点是根节点。每个节点都被染上了某一种颜色,其中第i个节点的颜色为c[i]。如果c[i]=c[j],那么我们认为点i和点j拥有相同的颜色。定义depth[i]为i节点与根节点的距离,为了方便起见,你可以认为树上相邻的两个点之间的距离为1。站在这棵色彩斑斓的树前面,你将面临m个问题。 每个问题包含两个整数x和d,表示询问x子树里且depth不超过depth[x]+d的所有点中出现了多少种本质不同的颜色。请写一个程序,快速回答这些询问。 【输入】第一行包含一个正整数T(1<=T<=500),表示测试数据的组数。 每组数据中,第
Bomboslav set up a branding agency and now helps companies to create new logos and advertising slogans. In term of this problems, slogan of the company should be a non-empty substring of its name. For example, if the company name is "hornsandhoofs", then substrings "sand" and "hor" could b
? 解题记录 ? ? 洛谷 ? ? 线段树 ? ? 线段树合并 ?    2018-05-15 07:59:50    458    0    0
题目描述Byteasar the gardener is growing a rare tree called Rotatus Informatikus. It has some interesting features: The tree consists of straight branches, bifurcations and leaves. The trunk stemming from the ground is also a branch. Each branch ends with either a bifurcation or a leaf on its top end. E
? 解题记录 ? ? 洛谷 ? ? 线段树 ? ? 线段树合并 ?    2018-01-21 15:01:11    374    0    0
题目描述永无乡包含 n 座岛,编号从 1 到 n,每座岛都有自己的独一无二的重要度,按照重要度可 以将这 n 座岛排名,名次用 1 到 n 来表示。某些岛之间由巨大的桥连接,通过桥可以从一个岛 到达另一个岛。如果从岛 a 出发经过若干座(含 0 座)桥可以到达岛 b,则称岛 a 和岛 b 是连 通的。 现在有两种操作: B x y 表示在岛 x 与岛 y 之间修建一座新桥。 Q x k 表示询问当前与岛 x连通的所有岛中第 k 重要的是哪座岛,即所有与岛 x 连通的岛中重要度排名第 k 小的岛是哪 座,请你输出那个岛的编号。 输入输出格式输入格式:   输入文件第一行是用空格隔开的两