有 $n$ 个集合，初始都为空，要求支持：

1. 向第 $[l, r]$ 个集合中加入 $x$。
2. 求第 $i$ 个集合的元素个数。

给一棵树，随机选取两个点，求两点间路径距离为质数的概率。

给出一个数列 $a_i$，有 $q$ 个询问 $(l, r, k)$，每次询问区间 $[l, r]$ 中的数从小到大排序且去重后第 $k$ 大的数，强制在线。

有 $N$ 座山排成一排，每座山都有一个 $1 \sim N$ 的唯一编号。第 $i$ 座山的编号为 $P_i$，高度为 $H_i$。
大厨从第一座山出发，目标是到达第 $N$ 座山。他可以从第 $i$ 座山跳到第 $j$ 座山上（$i < j, P_i < P_j$），并花费 $(H_i - H_j) ^ 2$ 的能量，当大厨处于第 $i$ 座山时，他还会花费 $A_i$ 的能量（$A_i$ 可以为负）。

求最小能量花费。

给出一个 $n$ 个节点的树，和一个长为 $n$ 的排列 $p$，要求支持：

1. 求 $\sum\limits_{i = l} ^ r \mathrm{dis}(p_i, x)$
2. $\mathrm{swap}(p_i, p_{i + 1})$

强制在线。

有 $n$ 个商店，每个商店中各有一个特殊物品，特殊物品会一直供应；按照时间顺序（令时间为 $\mathrm{day}$）有 $m$ 个下列事件：

1. 第 $s$ 个商店在当日新进一种价值为 $v$ 的商品，$\mathrm{day}++$；
2. 询问第 $L$ 到第 $R$ 的商店购买 $d$ 天内的商品价值 $\mathrm{xor} \ x$ 的最大值。

对于时刻 $1 \sim n$，要求支持：

1. 加入一个数 $a$；
2. 删除一个已加入的数 $a$。

求每个时刻所有数的最大异或和。

要求支持 $2$ 种操作：

1. 向字典中加入一个串 $s$，其权值为 $v$（若重复算作多个串）。
2. 询问一个串 $t$，其中在字典中出现过的单词的权值和（相同单词应被多次计算）。

强制在线。

维护一片森林，要求支持加边，询问重心，询问所有树重心编号的异或和。

维护一个森林，每个点有一个函数 $f$，要求支持连接两个点，断开两个点，修改某个点的函数，询问路径上函数 $f(x)$ 的和。

给 $n$ 个人，每人有 $5$ 科成绩，给出 $q$ 个成绩查询，输出 $5$ 科都比要查询的这 $5$ 科低的数目。

有 $n$ 种物品，个数无限，价值为 $w$，价格为 $p$，要求支持单点修改，询问 $k$ 元能买的最大价值，要求优先购买能买的物品中价值最大的，相同价值选择价格小的。

给出一个序列，每次操作将 $[l, r]$ 染上一种颜色 $i$，问最后有多少种颜色。

给出一个序列，每个位置有同一个颜色，每个颜色有一个价值，要求支持单点修改，查询区间 $[l, r]$ 的权值和，相同颜色只算一次。

现有一个长度为 $n$ 的序列 ${x_1, x_2, \cdots, x_n}$，要求支持两种操作：

1. 0 l r 表示将 $i \in [l, r], x_i \leftarrow x_i^2 \bmod p$
2. 1 l r 询问 $\sum\limits_{i = l} ^ r x_i$

给定一棵以 $1$ 为根的有根树，初始所有节点颜色为 $1$，每次将距离节点 $a$ 不超过 $l$ 的 $a$ 的子节点染成 $c$，或询问点 $a$ 的颜色。

题意很清晰，直接给链接。

链接

BZOJ 3337

给出一个 $n$ 的排列，进行 $m$ 次操作，每次操作是将一个区间升序或降序排序。
请你输出 $m$ 次操作后第 $p$ 个位置的值。

给定一个 $N$ 个点 $M$ 条边的有向图。统计无序对 $(X, Y)$ 的个数，其中 $(X, Y)$ 满足存在一条从 $1$ 到 $X$ 的路径，和一条 $1$ 到 $Y$ 的路径，且两路径除 $1$ 外无公共点。

一棵 $n$ 个点，边带权的树，$m$ 次询问，每次给出 $k$ 个关键点，求割掉最小代价的边使 $1$ 号点不能到达任何关键点。

给定一棵有 $n$ 个节点的无根树和 $m$ 个操作，操作有 $2$ 类：

1. 将节点 $a$ 到节点 $b$ 路径上所有点都染成颜色 $c$
2. 询问节点 $a$ 到节点 $b$ 路径上的颜色段数量

给出一个 $1 \sim n$ 的排列，$p_0, p_2, \cdots, p_{n - 1}$，每次从中选相邻两数删去，加入 $q$ 的前面，求最小字典序的 $q$。

维护一棵树，子树修改，询问 $k$ 条链并的权值和。

链接

BZOJ 3589

给定一颗由 $n$ 个节点 $n - 1$ 条边构成的树，在所有路径长度不超过 $R$ 且不低于 $L$ 的路径中，对于任意一条路径，将其每条边权值从大到小排序，取第 $\lfloor \frac {len} {2} \rfloor + 1$ 个权值，求使此权值最大时，从哪个节点出发，到哪个节点结束。

给你一棵 $n$ 个点的无根树。

树上的每条边具有颜色。一共有 $m$ 种颜色，编号为 $1$ 到 $m$。第 $i$ 种颜色的权值为 $c_i$。

对于一条树上的简单路径，路径上经过的所有边按顺序组成一个颜色序列，序列可以划

分成若干个相同颜色段。定义路径权值为颜色序列上每个同颜色段的颜色权值之和。

请你计算，经过边数在 $l$ 到 $r$ 之间的所有简单路径中，路径权值的最大值。

永无乡包含 n 座岛，编号从 1 到 n，每座岛都有自己的独一无二的重要度，按照重要度可 以将这 n 座岛排名，名次用 1 到 n 来表示。某些岛之间由巨大的桥连接，通过桥可以从一个岛 到达另一个岛。如果从岛 a 出发经过若干座（含 0 座）桥可以到达岛 b，则称岛 a 和岛 b 是连 通的。现在有两种操作：B x y 表示在岛 x 与岛 y 之间修建一座新桥。Q x k 表示询问当前与岛 x连通的所有岛中第 k 重要的是哪座岛，即所有与岛 x 连通的岛中重要度排名第 k 小的岛是哪 座，请你输出那个岛的编号。

算术天才 ⑨ 非常喜欢和等差数列玩耍。

有一天，他给了你一个长度为 $n$ 的序列，其中第 $i$ 个数为 $a[i]$。

他想考考你，每次他会给出询问 $l, r, k$，问区间 $[l, r]$ 内的数从小到大排序后能否形成公差为 $k$ 的等差数列。
当然，他还会不断修改其中的某一项。

为了不被他鄙视，你必须要快速并正确地回答完所有问题。

注意：只有一个数的数列也是等差数列。

共有 $m$ 部电影，编号为 $1 \sim m$，第 $i$ 部电影的好看值为 $w[i]$。

在 $n$ 天之中（从 $1 \sim n$ 编号）每天会放映一部电影，第 $i$ 天放映的是第 $f[i]$ 部。

你可以选择 $l,r(1 \leq l \leq r \leq n)$，并观看第 $l,l+1,\cdots,r$ 天内所有的电影。如果同一部电影你观看多于一次，你会感到无聊，于是无法获得这部电影的好看值。所以你希望最大化观看且仅观看过一次的电影的好看值的总和。

一个长度为 $ n $ 的大数，用 $ S_1S_2S_3 \ldots S_n $表示，其中 $ S_i $ 表示数的第 $ i $ 位，$ S_1 $ 是数的最高位，告诉你一些限制条件，每个条件表示为四个数 $( l_1, r_1, l_2, r_2 )$，即两个长度相同的区间，表示子串 $ S_{l_1}S_{l_1 + 1}S_{l_1 + 2} \ldots S_{r_1} $ 与 $ S_{l_2}S_{l_2 + 1}S_{l_2 + 2} \ldots S_{r_2} $ 完全相同。

比如 $ n = 6 $ 时，某限制条件 $ (l_1 = 1, r_1 = 3, l_2 = 4, r_2 = 6) $，那么 $ 123123 $,$ 351351 $ 均满足条件，但是 $ 12012 $,$ 131141 $ 不满足条件，前者数的长度不为 $ 6 $，后者第二位与第五位不同。问满足以上所有条件的数有多少个。

奈特公司是一个巨大的情报公司，它有着庞大的情报网络。情报网络中共有 $n$ 名情报员。每名情报员可能有若干名（可能没有）下线，除 $1$ 名大头目外其余 $n - 1$ 名情报员有且仅有 $1$ 名上线。奈特公司纪律森严，每名情报员只能与自己的上,下线联系，同时，情报网络中任意两名情报员一定能够通过情报网络传递情报。

1. 搜集情报：指派 $T$ 号情报员搜集情报
2. 传递情报：将一条情报从 $X$ 号情报员传递给 $Y$ 号情报员

情报员最初处于潜伏阶段，他们是相对安全的，我们认为此时所有情报员的危险值为0；-旦某个情报员开始搜集情报，他的危险值就会持续增加，每天增加1点危险值（开始搜集情报的当天危险值仍为0，第2天危险值为1，第3天危险值为2，以此类推）。传递情报并不会使情报员的危险值增加。为了保证传递情报的过程相对安全，每条情报都有一个风险控制值C。余特公司认为，参与传递这条情报的所有情报员中，危险值大于C的情报员将对该条情报构成威胁。现在，奈特公司希望知道，对于每个传递情报任务，参与传递的情报员有多少个，其中对该条情报构成威胁的情报员有多少个。

给定Ｎ个点以及每个点的权值，要你处理接下来的Ｍ个操作。操作有４种。操作从０到３编号。点从１到Ｎ编号。
０：后接两个整数（ｘ，ｙ），代表询问从ｘ到ｙ的路径上的点的权值的ｘｏｒ和。保证ｘ到ｙ是联通的。

１：后接两个整数（ｘ，ｙ），代表连接ｘ到ｙ，若ｘ到Ｙ已经联通则无需连接。

２：后接两个整数（ｘ，ｙ），代表删除边（ｘ，ｙ），不保证边（ｘ，ｙ）存在。

３：后接两个整数（ｘ，ｙ），代表将点Ｘ上的权值变成Ｙ。

某天，Lostmonkey发明了一种超级弹力装置，为了在他的绵羊朋友面前显摆，他邀请小绵羊一起玩个游戏。游戏一开始，Lostmonkey在地上沿着一条直线摆上 $n$ 个装置，每个装置设定初始弹力系数 $k_i$，当绵羊达到第i个装置时，它会往后弹 $k_i$ 步，达到第 $i + k_i$ 个装置，若不存在第 $i + k_i$ 个装置，则绵羊被弹飞。绵羊想知道当它从第 $i$ 个装置起步时，被弹几次后会被弹飞。为了使得游戏更有趣，Lostmonkey可以修改某个弹力装置的弹力系数，任何时候弹力系数均为正整数。

一棵n个点的树，每个点的初始权值为1。对于这棵树有q个操作，每个操作为以下四种操作之一：

+ $u$ $v$ $c$：将u到v的路径上的点的权值都加上自然数c；

- $u_1$ $v_1$ $u_2$ $v_2$：将树中原有的边 $(u_1,v_1)$ 删除，加入一条新边 $(u_2,v_2)$，保证操作完之后仍然是一棵树；

* $u$ $v$ $c$：将 $u$ 到 $v$ 的路径上的点的权值都乘上自然数 $c$；

/ $u$ $v$：询问 $u$ 到 $v$ 的路径上的点的权值和，求出答案对于 $51061$ 的余数。

辉辉热衷于洞穴勘测。某天，他按照地图来到了一片被标记为JSZX的洞穴群地区。经过初步勘测，辉辉发现这片区域由n个洞穴（分别编号为1到n）以及若干通道组成，并且每条通道连接了恰好两个洞穴。假如两个洞穴可以通过一条或者多条通道按一定顺序连接起来，那么这两个洞穴就是连通的，按顺序连接在一起的这些通道则被称之为这两个洞穴之间的一条路径。洞穴都十分坚固无法破坏，然而通道不太稳定，时常因为外界影响而发生改变，比如，根据有关仪器的监测结果，123号洞穴和127号洞穴之间有时会出现一条通道，有时这条通道又会因为某种稀奇古怪的原因被毁。辉辉有一台监测仪器可以实时将通道的每一次改变状况在辉辉手边的终端机上显示：如果监测到洞穴u和洞穴v之间出现了一条通道，终端机上会显示一条指令 Connect u v 如果监测到洞穴u和洞穴v之间的通道被毁，终端机上会显示一条指令 Destroy u v 经过长期的艰苦卓绝的手工推算，辉辉发现一个奇怪的现象：无论通道怎么改变，任意时刻任意两个洞穴之间至多只有一条路径。因而，辉辉坚信这是由于某种本质规律的支配导致的。因而，辉辉更加夜以继日地坚守在终端机之前，试图通过通道的改变情况来研究这条本质规律。然而，终于有一天，辉辉在堆积成山的演算纸中崩溃了……他把终端机往地面一砸（终端机也足够坚固无法破坏），转而求助于你，说道：“你老兄把这程序写写吧”。辉辉希望能随时通过终端机发出指令 Query u v，向监测仪询问此时洞穴u和洞穴v是否连通。现在你要为他编写程序回答每一次询问。已知在第一条指令显示之前，JSZX洞穴群中没有任何通道存在。

兔子们在玩 $k$ 个串的游戏。首先，它们拿出了一个长度为 $n$ 的数字序列，选出其中的一
个连续子串，然后统计其子串中所有数字之和（注意这里重复出现的数字只被统计一次）。

兔子们想知道，在这个数字序列所有连续的子串中，按照以上方式统计其所有数字之和，第
$k$ 大的和是多少。

Your friend, Jackson is invited to a TV show called SuperMemo in which the participant is told to play a memorizing game. At first, the host tells the participant a sequence of numbers, {A1, A2, … An}. Then the host performs a series of operations and queries on the sequence which consists:

这天，SJY显得无聊。在家自己玩。在一个棋盘上，有N个黑色棋子。他每次要么放到棋盘上一个黑色棋子，要么放上一个白色棋子，如果是白色棋子，他会找出距离这个白色棋子最近的黑色棋子。此处的距离是 曼哈顿距离 即(|x1-x2|+|y1-y2|) 。现在给出N<=500000个初始棋子。和M<=500000个操作。对于每个白色棋子，输出距离这个白色棋子最近的黑色棋子的距离。同一个格子可能有多个棋子。

对于序列A，它的逆序对数定义为满足 $i < j$，且 $A_i > A_j$ 的数对 $(i, j)$ 的个数。给 $1$ 到 $n$ 的一个排列，按照某种顺序依次删除m个元素，你的任务是在每次删除一个元素之前统计整个序列的逆序对数。

维护一个 $W * W$ 的矩阵，初始值均为S.每次操作可以增加某格子的权值,或询问某子矩阵的总权值.修改操作数 $M <= 160000$,询问数 $Q <= 10000,W <= 2000000$.

有n朵花，每朵花有三个属性：花形(s),颜色(c),气味(m)，又三个整数表示。现要对每朵花评级，一朵花的级别是它拥有的美丽能超过的花的数量。定义一朵花A比另一朵花B要美丽，当且仅当Sa>=Sb,Ca>=Cb,Ma>=Mb。显然，两朵花可能有同样的属性。需要统计出评出每个等级的花的数量。

排名系统通常要应付三种请求：上传一条新的得分记录、查询某个玩家的当前排名以及返回某个区段内的排名记录。当某个玩家上传自己最新的得分记录时，他原有的得分记录会被删除。为了减轻服务器负担，在返回某个区段内的排名记录时，最多返回$10$ 条记录。

给定一个含有 n 个数的序列 a[1],a[2],a[3], … ,a[n]，程序必须回答这样的询问：对于给定的 i,j,k，在 a[i],a[i+1],a[i+2], … ,a[j] 中第 k 小的数是多少 (1≤k≤j-i+1)，并且，你可以改变一些a[i]的值，改变后，程序还能针对改变后的a继续回答上面的问题。你需要编一个这样的程序，从输入文件中读入序列 a，然后读入一系列的指令，包括询问指令和修改指令。对于每一个询问指令，你必须输出正确的回答。 第一行有两个正整数 n(1≤n≤10000)，m(1≤m≤10000)。分别表示序列的长度和指令的个数。第二行有 n 个数，表示 a[1],a[2]……a[n]，这些数都小于 10^9。接下来的 m 行描述每条指令，每行的格式是下面两种格式中的一种。 Q i j k 或者 C i t Q i j k （i,j,k是数字，1≤i≤j≤n, 1≤k≤j-i+1） 表示询问指令，询问 a[i]，a[i+1]……a[j] 中第 k 小的数。C i t (1≤i≤n，0≤t≤10^9) 表示把 a[i] 改变成为 t。

兵库县位于日本列岛的中央位置，北临日本海，南面濑户内海直通太平洋，中央部位是森林和山地，与拥有关西机场的大阪府比邻而居，是关西地区面积最大的县，是集经济和文化于一体的一大地区，是日本西部门户，海陆空交通设施发达。濑户内海沿岸气候温暖，多晴天，有日本少见的贸易良港神户港所在的神户市和曾是豪族城邑“城下町”的姬路市等大城市，还有以疗养地而闻名的六甲山地等。
兵库县官方也大力发展旅游，为了方便，他们在县内的N个旅游景点上建立了n-1条观光道，构成了一棵图论中的树。同时他们推出了M条观光线路，每条线路由两个节点x和y指定，经过的旅游景点就是树上x到y的唯一路径上的点。保证一条路径只出现一次。
你和你的朋友打算前往兵库县旅游，但旅行社还没有告知你们最终选择的观光线路是哪一条（假设是线路A）。这时候你得到了一个消息：在兵库北有一群丧心病狂的香菜蜜，他们已经选定了一条观光线路（假设是线路B），对这条路线上的所有景点都释放了【精神污染】。这个计划还有可能影响其他的线路，比如有四个景点1-2-3-4，而【精神污染】的路径是1-4，那么1-3,2-4,1-2等路径也被视为被完全污染了。
现在你想知道的是，假设随便选择两条不同的路径A和B，存在一条路径使得如果这条路径被污染，另一条路径也被污染的概率。换句话说，一条路径被另一条路径包含的概率。

数集 $S$ 的 $ForbiddenSum$ 定义为无法用 $S$ 的某个子集（可以为空）的和表示的最小的非负整数。
例如，$S={1,1,3,7}$，则它的子集和中包含0(S’= \varnothing)，1(S’={1})，2(S’={1,1})，3(S’={3})，4(S’={1,3})，5(S’ = {1, 1, 3})，但是它无法得到 $6$。因此 $S$ 的 $ForbiddenSum$ 为 $6$。
给定一个序列 $A$，你的任务是回答该数列的一些子区间所形成的数集的$ForbiddenSum$ 是多少。

一个可重复数字集合 $S$ 的神秘数定义为最小的不能被 $S$ 的子集的和表示的正整数。
求由 $a[l]$，$a[l+1]$，… ，$a[r]$ 所构成的可重复数字集合的神秘数。

在 Bytemountains 有 N 座山峰，每座山峰有他的高度 h_i 。有些山峰之间有双向道路相连，共 M 条路径，每条路径有一个困难值，这个值越大表示越难走，现在有 Q 组询问，每组询问询问从点 v 开始只经过困难值小于等于 x 的路径所能到达的山峰中第 k 高的山峰，如果无解输出 -1。

You are working for Macrohard company in data structures department. After failing your previous task about key insertion you were asked to write a new data structure that would be able to return quickly k-th order statistics in the array segment.
That is, given an array $a[1…n]$ of different integer numbers, your program must answer a series of questions $Q(i, j, k)$ in the form: “What would be the k-th number in $a[i…j]$ segment, if this segment was sorted?”
For example, consider the array $a = (1, 5, 2, 6, 3, 7, 4)$. Let the question be $Q(2, 5, 3)$. The segment $a[2…5]$ is $(5, 2, 6, 3)$. If we sort this segment, we get $(2, 3, 5, 6)$, the third number is $5$, and therefore the answer to the question is $5$.
题意：就是求区间第 $k$ 大。

傲娇少女幽香正在玩一个非常有趣的战略类游戏，本来这个游戏的地图其实还不算太大，幽香还能管得过来，但是不知道为什么现在的网游厂商把游戏的地图越做越大，以至于幽香一眼根本看不过来，更别说和别人打仗了。
在打仗之前，幽香现在面临一个非常基本的管理问题需要解决。
整个地图是一个树结构，一共有 $n$ 块空地，这些空地被 $n-1$ 条带权边连接起来，使得每两个点之间有一条唯一的路径将它们连接起来。在游戏中，幽香可能在空地上增加或者减少一些军队。同时，幽香可以在一个空地上放置一个补给站。
如果补给站在点 $u$ 上，并且空地 $v$ 上有 $d_v$ 个单位的军队，那么幽香每天就要花费：$d_v \times dist(u,v)$ 的金钱来补给这些军队。由于幽香需要补给所有的军队，因此幽香总共就要花费为 $\sum_{v=1}^{n}d_v \cdot dist(u, v)$ 的代价。其中 $dist(u,v)$ 表示 $u$ 和 $v$ 在树上的距离（唯一路径的权和）。
因为游戏的规定，幽香只能选择一个空地作为补给站。在游戏的过程中，幽香可能会在某些空地上制造一些军队，也可能会减少某些空地上的军队，进行了这样的操作以后，出于经济上的考虑，幽香往往可以移动她的补给站从而省一些钱。但是由于这个游戏的地图是在太大了，幽香无法轻易的进行最优的安排，你能帮帮她吗？ 你可以假定一开始所有空地上都没有军队。

捉迷藏 $Jiajia$ 和 $Wind$ 是一对恩爱的夫妻，并且他们有很多孩子。某天，$Jiajia$、$Wind$ 和孩子们决定在家里玩捉迷藏游戏。他们的家很大且构造很奇特，由 $N$ 个屋子和 $N-1$ 条双向走廊组成，这 $N-1$ 条走廊的分布使得任意两个屋子都互相可达。游戏是这样进行的，孩子们负责躲藏，$Jiajia$ 负责找，而 $Wind$ 负责操纵这 $N$ 个屋子的灯。在起初的时候，所有的灯都没有被打开。每一次，孩子们只会躲藏在没有开灯的房间中，但是为了增加刺激性，孩子们会要求打开某个房间的电灯或者关闭某个房间的电灯。为了评估某一次游戏的复杂性，$Jiajia$ 希望知道可能的最远的两个孩子的距离（即最远的两个关灯房间的距离）。 我们将以如下形式定义每一种操作： $C(hange)$ $i$ 改变第 $i$ 个房间的照明状态，若原来打开，则关闭；若原来关闭，则打开。 $G(ame)$ 开始一次游戏，查询最远的两个关灯房间的距离。

聪聪和可可是兄弟俩，他们俩经常为了一些琐事打起来，例如家中只剩下最后一根冰棍而两人都想吃,两个人都想玩儿电脑（可是他们家只有一台电脑）……遇到这种问题，一般情况下石头剪刀布就好了，可是他们已经玩儿腻了这种低智商的游戏。他们的爸爸快被他们的争吵烦死了，所以他发明了一个新游戏：由爸爸在纸上画 $n$ 个“点”，并用$n-1$条“边”把这 $n$ 个“点”恰好连通（其实这就是一棵树）。并且每条“边”上都有一个数。接下来由聪聪和可可分别随即选一个点（当然他们选点时是看不到这棵树的），如果两个点之间所有边上数的和加起来恰好是 $3$ 的倍数，则判聪聪赢，否则可可赢。聪聪非常爱思考问题，在每次游戏后都会仔细研究这棵树，希望知道对于这张图自己的获胜概率是多少。现请你帮忙求出这个值以验证聪聪的答案是否正确。