数集 $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$ 的倍数，则判聪聪赢，否则可可赢。聪聪非常爱思考问题，在每次游戏后都会仔细研究这棵树，希望知道对于这张图自己的获胜概率是多少。现请你帮忙求出这个值以验证聪聪的答案是否正确。

Give a tree with n vertices,each edge has a length(positive integer less than 1001).
Define dist(u,v)=The min distance between node u and v.
Give an integer k,for every pair (u,v) of vertices is called valid if and only if dist(u,v) not exceed k.
Write a program that will count how many pairs which are valid for a given tree.
题意：给一棵边带权树，问两点之间的距离小于等于K的点对有多少个。

给定一个长度为 N 的序列，每个序列的元素是一个整数。要支持以下三种操作：

1. 将 [L,R] 这个区间内的所有数加上 V。
2. 将 [L,R] 这个区间翻转，比如 1 2 3 4 变成 4 3 2 1。
3. 求 [L,R] 这个区间中的最大值。 最开始所有元素都是 0。

工资的频繁调整很让员工反感，尤其是集体扣除工资的时候，一旦某位员工发现自己的工资已经低于了合同规定的工资下界，他就会立刻气愤地离开公司，并且再也不会回来了。每位员工的工资下界都是统一规定的。每当一个人离开公司，我就要从电脑中把他的工资档案删去，同样，每当公司招聘了一位新员工，我就得为他新建一个工资档案。老板经常到我这边来询问工资情况，现在工资第 $k$ 多的员工拿多少工资。

Splay Tree（伸展树）是一种自平衡二叉排序树，可以在均摊 $O({\log} n)$ 的时间内完成基于 Splay（伸展）操作的修改与查询。

本题中，我们将用符号 $\lfloor c \rfloor$ 表示对 $c$ 向下取整，例如： $\lfloor 3.0 \rfloor = \lfloor 3.1 \rfloor = \lfloor 3.9 \rfloor = 3$。
蛐蛐国最近蚯蚓成灾了！隔壁跳蚤国的跳蚤也拿蚯蚓们没办法，蛐蛐国王只好去请神刀手来帮他们消灭蚯蚓。
蛐蛐国里现在共有 $n$ 只蚯蚓（ $n$ 为正整数）。每只蚯蚓拥有长度，我们设第 $i$ 只蚯蚓的长度为 $a_i$（ $i = 1, 2, \ldots , n$），并保证所有的长度都是非负整数（即：可能存在长度为 $0$ 的蚯蚓）。
每一秒，神刀手会在所有的蚯蚓中，准确地找到最长的那一只（如有多个则任选一个）将其切成两半。神刀手切开蚯蚓的位置由常数 $p$（是满足 $0 < p < 1$ 的有理数）决定，设这只蚯蚓长度为 $x$，神刀手会将其切成两只长度分别为 $\lfloor px \rfloor$ 和 $x - \lfloor px \rfloor$ 的蚯蚓。特殊地，如果这两个数的其中一个等于 $0$，则这个长度为 $0$ 的蚯蚓也会被保留。此外，除了刚刚产生的两只新蚯蚓，其余蚯蚓的长度都会增加 $q$（是一个非负整常数）。
蛐蛐国王知道这样不是长久之计，因为蚯蚓不仅会越来越多，还会越来越长。蛐蛐国王决定求助于一位有着洪荒之力的神秘人物，但是救兵还需要 $m$ 秒才能到来 $\cdots \cdots$ （ $m$ 为非负整数）
蛐蛐国王希望知道这 $m$ 秒内的战况。具体来说，他希望知道：
$m$ 秒内，每一秒被切断的蚯蚓被切断前的长度（有 $m$ 个数）；
$m$ 秒后，所有蚯蚓的长度（有 $n + m$ 个数）。
蛐蛐国王当然知道怎么做啦！但是他想考考你 $\cdots \cdots $

题目描述

在一个忍者的帮派里，一些忍者们被选中派遣给顾客，然后依据自己的工作获取报偿。
在这个帮派里，有一名忍者被称之为 Master。除了 Master 以外，每名忍者都有且仅有一个上级。为保密，同时增强忍者们的领导力，所有与他们工作相关的指令总是由上级发送给他的直接下属，而不允许通过其他的方式发送。

志愿者选拔

题目描述

西博会马上就要开幕了，电子科技大学组织了一次志愿者选拔活动。
参加志愿者选拔的同学们排队接受面试官们的面试。参加面试的同学们按照先来先面试并且先结束的原则接受面试官们的考查。
面试中每个人的英语口语能力是主要考查对象之一。
作为主面试官的John想知道当前正在接受面试的同学队伍中口语能力值最高的是多少。于是他请你帮忙编写一个程序来计算。

简单题

题目背景

CQOI2006 T1

题目描述

有一个 n 个元素的数组，每个元素初始均为 0 。有 m 条指令，要么让其中一段连续序列数字反转——0 变 1，1 变 0（操作1），要么询问某个元素的值（操作2）。例如当 n=20 时，10 条指令如下：

系列操作Ⅱ

题目描述

给出数列 $a_1, a_2,\cdots,a_n(0 \leq a_i \leq 10 ^ 9)$，有关序列的两种操作。

1. $a_l, a_{ l + 1 }, \cdots, a_r(1 \leq l \leq r \leq n)$ 加上 $x(-10 ^ 3 \leq x \leq 10 ^ 3)$
2. 求 $a_i(1 \leq i \leq n)$

输入格式

第一行包含两个数 $n(1 \leq n \leq 10 ^ 5)$ 和 $m(1 \leq m \leq 10 ^ 5)$，表示序列的长度和操作次数。

接下来的一行有 $n$ 个数，以空格隔开，表示 $a_1, a_2, \cdots, a_n$。

接下来的 $m$ 行，每行为有以下两种格式之一：

0 1 r x ，表示 $a_l, a_{l+1},\cdots,a_r$ 加上 $x$。

1 i ，求 $a_i$。

输出格式

对于每次询问，输出单独一行表示答案。