BZOJ 3113: Toy
外面有一圈 N 个结点，中心有一个结点与 N 个结点都相连，总共就是 条边，删除 N 条边，使 N+1 个点连通，旋转相同视为等价，问有多少种情况。
题解、Writeup、游记和碎碎念
2016 年 11 月
外面有一圈 N 个结点，中心有一个结点与 N 个结点都相连，总共就是 条边，删除 N 条边，使 N+1 个点连通，旋转相同视为等价，问有多少种情况。
给一个长为 n 的序列 a，每个数在 0 到 v - 1 之间，有 m 次操作。
操作 1：每次询问一个区间中是否可以选出两个下标的集合 X，Y，满足：
1.X 和 Y 没有交集 2.设集合 X 中有一个元素是 i，则其对集合 X 的贡献是 a[i] + 1，要求集合 X 的元素的总贡献和集合 Y 的元素的总贡献
相等如果可以选出这两个集合，输出 Yuno 否则输出 Yuki
操作 2：修改一个区间 l,r 之间的数，使得所有 l <= i <= r，a[i] = a[i] * a[i] * a[i] % v ，即区间立方
您需要写一种数据结构（可参考题目标题），来维护一个有序数列，其中需要提供以下操作： 1.查询 k 在区间内的排名 2.查询区间内排名为 k 的值 3.修改某一位值上的数值 4.查询 k 在区间内的前驱(前驱定义为小于 x，且最大的数) 5.查询 k 在区间内的后继(后继定义为大于 x，且最小的数)
“寄没有地址的信，这样的情绪有种距离，你放着谁的歌曲，是怎样的心心静，能不能说给我听。” 失忆的 Eden 总想努力地回忆起过去，然而总是只能清晰地记得那种思念的感觉，却不能回忆起她的音容笑貌。 记忆中，她总是喜欢给 Eden 出谜题：在 valentine’s day 的夜晚，两人在闹市中闲逛时，望着礼品店里精巧玲珑的各式玩偶，她突发奇想，问了 Eden 这样的一个问题：有 n 个玩偶，每个玩偶有对应的价值、价钱，每个玩偶都可以被买有限次，在携带的价钱 m 固定的情况下，如何选择买哪些玩偶以及每个玩偶买多少个，才能使得选择的玩偶总价钱不超过 m，且价值和最大。众所周知的，这是一个很经典的多重背包问题，Eden 很快解决了，不过她似乎因为自己的问题被飞快解决感到了一丝不高兴，于是她希望把问题加难：多次 询问，每次询问都将给出新的总价钱，并且会去掉某个玩偶（即这个玩偶不能被选择），再问此时的多重背包的答案（即前一段所叙述的问题）。 这下 Eden 犯难了，不过 Eden 不希望自己被难住，你能帮帮他么？
1946 年 3 月 5 日，英国前首相温斯顿·丘吉尔在美国富尔顿发表“铁幕演说”，正式拉开了冷战序幕。
美国和苏联同为世界上的“超级大国”，为了争夺世界霸权，两国及其盟国展开了数十年的斗争。在这段时期，虽然分歧和冲突严重，但双方都尽力避免世界范围的大规模战争（第三次世界大战）爆发，其对抗通常通过局部代理战争、科技和军备竞赛、太空竞争、外交竞争等“冷”方式进行，即“相互遏制，不动武力”，因此称之为“冷战”。
Reddington 是美国的海军上将。由于战争局势十分紧张，因此他需要时刻关注着苏联的各个活动，避免使自己的国家陷入困境。苏联在全球拥有 N 个军工厂，但由于规划不当，一开始这些军工厂之间是不存在铁路的，为了使武器制造更快，苏联决定修建若干条道路使得某些军工厂联通。
Reddington 得到了苏联的修建日程表，并且他需要时刻关注着某两个军工厂是否联通，以及最早在修建哪条道路时会联通。具体而言，现在总共有 M 个操作，操作分为两类：
• 0 u v，这次操作苏联会修建一条连接 u 号军工厂及 v 号军工厂的铁路，注意铁路都是双向的;
• 1 u v， Reddington 需要知道 u 号军工厂及 v 号军工厂最早在加入第几条条铁路后会联通，假如到这次操作都没有联通，则输出 0;
作为美国最强科学家， Reddington 需要你帮忙设计一个程序，能满足他的要求。
XLk 觉得《上帝造题的七分钟》不太过瘾，于是有了第二部。 "第一分钟，X 说，要有数列，于是便给定了一个正整数数列。 第二分钟，L 说，要能修改，于是便有了对一段数中每个数都开平方(下取整)的操作。 第三分钟，k 说，要能查询，于是便有了求一段数的和的操作。 第四分钟，彩虹喵说，要是 noip 难度，于是便有了数据范围。 第五分钟，诗人说，要有韵律，于是便有了时间限制和内存限制。 第六分钟，和雪说，要省点事，于是便有了保证运算过程中及最终结果均不超过 64 位有符号整数类型的表示范围的限制。 第七分钟，这道题终于造完了，然而，造题的神牛们再也不想写这道题的程序了。" ——《上帝造题的七分钟·第二部》 所以这个神圣的任务就交给你了。