题目背景

ZBY 是一只青蛙！

题目描述

如果一只青蛙在 u (u>1) 号荷叶，他会进行一步等概率的跳跃，从 u 号荷叶跳到 1…u 号荷叶。

现在青蛙在 N 号荷叶，求出他跳到 1 号荷叶的期望步数。

诈尸了…这题比较 容易口胡 有意思，所以…

题目描述

我的母亲柯蒂丽亚，是一个舞者。身披罗纱，一身异国装扮的她，来自灰狼的村子。

曾经在灰狼村子担任女侍的她，被认定在某晚犯下可怕的罪行之后，被赶出了村子。

一切的元凶，都要回到母亲犯下重罪的那一晚。

好久没更新博客了呢…
入坑OI半年多了，又要回校要开始暑假的集训了
初中就这样结束了呀

Description

幼儿园里有N个小朋友，lxhgww老师现在想要给这些小朋友们分配糖果，要求每个小朋友都要分到糖果。但是小朋友们也有嫉妒心，总是会提出一些要求，比如小明不希望小红分到的糖果比他的多，于是在分配糖果的时候，lxhgww需要满足小朋友们的K个要求。幼儿园的糖果总是有限的，lxhgww想知道他至少需要准备多少个糖果，才能使得每个小朋友都能够分到糖果，并且满足小朋友们所有的要求。

Input

输入的第一行是两个整数N，K。

接下来K行，表示这些点需要满足的关系，每行3个数字，X，A，B。

如果X=1， 表示第A个小朋友分到的糖果必须和第B个小朋友分到的糖果一样多；

题目描述

如图：有 n 个重物，每个重物系在一条足够长的绳子上。每条绳子自上而下穿过桌面上的洞，然后系在一起。图中 X 处就是公共的绳结。假设绳子是完全弹性的（不会造成能量损失），桌子足够高（因而重物不会垂到地上），且忽略所有的摩擦。

问绳结 X 最终平衡于何处。

注意：桌面上的洞都比绳结 X 小得多，所以即使某个重物特别重，绳结 X 也不可能穿过桌面上的洞掉下来，最多是卡在某个洞口处。

对树状数组不了解的同学戳这里 —> 【模板】树状数组

题目背景

裸体就意味着身体。

*tips:作为一道严肃题目的背景，这句话显然是非常重要的（我总不能说吸引读者注意，激发读者阅读兴趣吧咳咳…）

感觉是个好大的坑wa…我就简略地写写好了…其实树状数组在大部分时候仅作为线段树的替代品（执行的基本操作相似，且代码简单易懂，时空复杂度均低于线段树），那那那为什么需要线段树呢？树状数组的适用范围小啊（很小很小啊）执行基本修改查询操作已经很不错了还苛求什么呢…

概念与基本性质

树状数组(Binary Indexed Tree(B.I.T), Fenwick Tree)是一个查询和修改复杂度都为log(n)的数据结构。主要用于查询任意两位之间的所有元素之和，但是每次只能修改一个元素的值；经过简单修改可以在log(n)的复杂度下进行范围修改，但是这时只能查询其中一个元素的值(如果加入多个辅助数组则可以实现区间修改与区间查询)。

概念与基本性质

左偏树(Leftist Tree)是一种可并堆的实现，是具有左偏性质的堆有序二叉树

• 可并堆(Mergeable Heap)是一种抽象数据类型，它除了支持优先队列的三个基本操作(Insert, Minimum,Delete-Min)，还支持一个额外的操作——合并操作。

• 左偏性质是为了使我们可以以更小的代价在优先队列的其它两个基本操作（插入节点、删除最小节点）进行后维持堆性质。

左偏树是一棵二叉树，它的节点除了和二叉树的节点一样具有左右子树指针(left, right)外，还有两个属性，键值(key)和距离(dist)
节点的键值小于或等于它的左右子节点的键值（小根）
节点的左子节点的距离不小于右子节点的距离（左偏性质）
节点的距离等于它的右子节点的距离加1

算法介绍

莫队算法，简单说就是基于分块进行暴力

莫队算法，是由前国家队队长莫涛在役时创造的，为数不多几种在役选手在比赛或平时训练中创造并广为流传使用的算法之一。

此算法在OI界具有极高的人气，据说能解决一切区间处理问题，当然我这种蒟蒻却只能板子题做做，让我们通过下面的题目简单了解一下莫队算法。

概念与基本性质

Treap = Tree + Heap，即是一棵同时满足二叉搜索树和堆性质的二叉树
Treap 有一个随机附加域满足堆的性质，其结构相当于以随机数据插入的二叉搜索树
其基本操作的期望时间复杂度为 O(log n)

相对于其他的平衡二叉搜索树，Treap的特点是实现简单，且能基本实现随机平衡的结构。