NIRVANA

Problem

Shallot

$\mathrm{Time\;Limit:\;30\;Sec}$
$\mathrm{Memory\;Limit:\;128\;MB}$

Description

小苗去市场上买了一捆小葱苗，她突然一时兴起，于是她在每颗小葱苗上写上一个数字，然后把小葱叫过来玩游戏。
每个时刻她会给小葱一颗小葱苗或者是从小葱手里拿走一颗小葱苗，并且让小葱从自己手中的小葱苗里选出一些小葱苗使得选出的小葱苗上的数字的异或和最大。
这种小问题对于小葱来说当然不在话下，但是他的身边没有电脑，于是他打电话给同为$\mathrm{OI}$选手的你，你能帮帮他吗？
你只需要输出最大的异或和即可，若小葱手中没有小葱苗则输出0。

Input

第一行一个正整数$n$表示总时间。
第二行$n$个整数$a_1,a_2,\cdots,a_n$，若$a_i$大于$0$代表给了小葱一颗数字为$a_i$的小葱苗，否则代表从小葱手中拿走一颗数字为$-a_i$的小葱苗。

Output

输出共$n$行，每行一个整数代表第$i$个时刻的最大异或和。

Problem

二叉树

$\mathrm{Time\;Limit:\;15\;Sec}$
$\mathrm{Memory\;Limit:\;256\;MB}$

Description

现在有一棵二叉树，所有非叶子节点都有两个孩子。
在每个叶子节点上有一个权值（有$n$个叶子节点，满足这些权值为$1\sim n$的一个排列）。可以任意交换每个非叶子节点的左右孩子。
要求进行一系列交换，使得最终所有叶子节点的权值按照中序遍历写出来，逆序对个数最少。

Input

第一行一个整数$n$。
下面每行一个数$x$，

• 如果$x=0$，表示这个节点非叶子节点，递归地向下读入其左孩子和右孩子的信息，
• 如果$x\ne0$，表示这个节点是叶子节点，权值为$x$。

Output

一行，最少逆序对个数。

Problem

向量

$\mathrm{Time\;Limit:\;20\;Sec}$
$\mathrm{Memory\;Limit:\;512\;MB}$

Description

你要维护一个向量集合，支持以下操作：

1. 插入一个向量$(x,y)$
2. 删除插入的第$i$个向量
3. 查询当前集合与$(x,y)$点积的最大值是多少，如果当前是空集输出0

Input

第一行输入一个整数$n$，表示操作个数
接下来$n$行，每行先是一个整数$t$表示类型，如果$t=1$，输入向量$(x,y)$；如果$t=2$，输入$id$表示删除第$id$个向量；否则输入$(x,y)$，查询与向量$(x,y)$点积最大值是多少
保证一个向量只会被删除一次，不会删没有插入过的向量

Output

对于每条$t=3$的询问，输出一个答案

Problem

算术天才⑨与等差数列

$\mathrm{Time\;Limit:\;10\;Sec}$
$\mathrm{Memory\;Limit:\;128\;MB}$

Description

算术天才⑨非常喜欢和等差数列玩耍。
有一天，他给了你一个长度为$n$的序列，其中第$i$个数为$a_i$。
他想考考你，每次他会给出询问$l,r,k$，问区间$[l,r]$内的数从小到大排序后能否形成公差为$k$的等差数列。
当然，他还会不断修改其中的某一项。
为了不被他鄙视，你必须要快速并正确地回答完所有问题。
注意：只有一个数的数列也是等差数列。

Input

第一行包含两个正整数$n,m\;(1\le n,m\le300000)$，分别表示序列的长度和操作的次数。
第二行包含$n$个整数，依次表示序列中的每个数$a_i\;(0\le a_i\le10^9)$。
接下来$m$行，每行一开始为一个数$op$，
若$op=1$，则接下来两个整数$x,y\;(1\le x\le n,0\le y\le10^9)$，表示把$a_x$修改为$y$。
若$op=2$，则接下来三个整数$l,r,k\;(1\le l\le r\le n,0\le k\le10^9)$，表示一个询问。
在本题中，$x,y,l,r,k$都是经过加密的，都需要异或你之前输出的Yes的个数来进行解密。

Output

输出若干行，对于每个询问，如果可以形成等差数列，那么输出Yes，否则输出No。

Problem

【Usaco2008 Jan】猜数游戏

$\mathrm{Time\;Limit:\;10\;Sec}$
$\mathrm{Memory\;Limit:\;162\;MB}$

Description

为了提高自己低得可怜的智商，奶牛们设计了一个新的猜数游戏，来锻炼她们的逻辑推理能力。
游戏开始前，一头指定的奶牛会在牛棚后面摆$N\;(1\le N\le 10^6)$堆干草，每堆有若干捆，并且没有哪两堆中的草一样多。
所有草堆排成一条直线，从左到右依次按$1\sim N$编号，每堆中草的捆数在$[1,10^9]$之间。
然后，游戏开始。
另一头参与游戏的奶牛会问那头摆干草的奶牛$Q\;(1\le Q\le 25000)$个问题，问题的格式如下：
编号为$Q_l\sim Q_h\;(1\le Q_l\le Q_h\le N)$的草堆中，最小的那堆里有多少捆草？
对于每个问题，摆干草的奶牛回答一个数字$A$，但或许是不想让提问的奶牛那么容易地得到答案，又或许是她自己可能记错每堆中干草的捆数，总之，她的回答不保证是正确的。
请你帮助提问的奶牛判断一下，摆干草的奶牛的回答是否有自相矛盾之处。

Input

• 第$1$行: $2$个用空格隔开的整数：$N$和$Q$
• 第$2\sim Q+1$行: 每行为$3$个用空格隔开的整数$Q_l,Q_h,A$，描述了一个问题以及它对应的回答

Output

如果摆干草的奶牛有可能完全正确地回答了这些问题，输出$0$；否则输出$1$个$1\sim Q$中的数，表示这个问题的答案与它之前的那些回答有冲突之处。
注意：如果有冲突出现输出一个数$m$，使得前$m-1$个命题不冲突。

Problem

【USACO2008 Open】奶牛的邻居

$\mathrm{Time\;Limit:\;5\;Sec}$
$\mathrm{Memory\;Limit:\;64\;MB}$

Description

了解奶牛们的人都知道，奶牛喜欢成群结队．观察约翰的$N\;(1\le N\le10^5)$只奶牛，你会发现她们已经结成了几个“群”．每只奶牛在吃草的时候有一个独一无二的位置坐标$x_i,y_i\;(x_i,y_i\in[1,10^9],x_i,y_i\in\Z)$．当满足下列两个条件之一，两只奶牛$i$和$j$是属于同一个群的：

1. 两只奶牛的曼哈顿距离不超过$C\;(1\le C\le10^9)$，即$|x_i-x_j|+|y_i-y_j|\le C$.
2. 两只奶牛有共同的邻居，即存在一只奶牛$k$，使$i$与$k，j$与$k$均同属一个群．

给出奶牛们的位置，请计算草原上有多少个牛群，以及最大的牛群里有多少奶牛。

Input

第$1$行输入$N$和$C$，之后$N$行每行输入一只奶牛的坐标。

Output

仅一行，先输出牛群数，再输出最大牛群里的牛数，用空格隔开。

Problem

【HEOI2014】大工程

$\mathrm{Time\;Limit:\;60\;Sec}$
$\mathrm{Memory\;Limit:\;512\;MB}$

Description

国家有一个大工程，要给一个非常大的交通网络里建一些新的通道。
我们这个国家位置非常特殊，可以看成是一个单位边权的树，城市位于顶点上。
在两个国家$a,b$之间建一条新通道需要的代价为树上$a,b$的最短路径。
现在国家有很多个计划，每个计划都是这样，我们选中了$k$个点，然后在它们两两之间新建$\binom{k}{2}$条新通道。
现在对于每个计划，我们想知道：

1. 这些新通道的代价和
2. 这些新通道中代价最小的是多少
3. 这些新通道中代价最大的是多少

Input

第一行$n$表示点数。
接下来$n-1$行，每行两个数$a,b$表示$a$和$b$之间有一条边。
点从$1$开始标号。接下来一行$q$表示计划数。
对每个计划有$2$行，第一行$k$表示这个计划选中了几个点。
第二行用空格隔开的$k$个互不相同的数表示选了哪$k$个点。

Output

输出$q$行，每行三个数分别表示代价和，最小代价，最大代价。

Problem

【ZJOI2007】棋盘制作

$\mathrm{Time\;Limit:\;20\;Sec}$
$\mathrm{Memory\;Limit:\;162\;MB}$

Description

国际象棋是世界上最古老的博弈游戏之一，和中国的围棋、象棋以及日本的将棋同享盛名。据说国际象棋起源于易经的思想，棋盘是一个$8\times8$大小的黑白相间的方阵，对应八八六十四卦，黑白对应阴阳。而我们的主人公$\mathrm{小Q}$，正是国际象棋的狂热爱好者。作为一个顶尖高手，他已不满足于普通的棋盘与规则，于是他跟他的好朋友$\mathrm{小W}$决定将棋盘扩大以适应他们的新规则。
$\mathrm{小Q}$找到了一张由$N\times M$个正方形的格子组成的矩形纸片，每个格子被涂有黑白两种颜色之一。$\mathrm{小Q}$想在这种纸中裁减一部分作为新棋盘，当然，他希望这个棋盘尽可能的大。不过$\mathrm{小Q}$还没有决定是找一个正方形的棋盘还是一个矩形的棋盘（当然，不管哪种，棋盘必须都黑白相间，即相邻的格子不同色），所以他希望可以找到最大的正方形棋盘面积和最大的矩形棋盘面积，从而决定哪个更好一些。于是$\mathrm{小Q}$找到了即将参加全国信息学竞赛的你，你能帮助他么？

Input

第一行包含两个整数$N$和$M$，分别表示矩形纸片的长和宽。
接下来的$N$行包含一个$N\times M$的$01$矩阵，表示这张矩形纸片的颜色（$0$表示白色，$1$表示黑色）。

Output

包含两行，每行包含一个整数。
第一行为可以找到的最大正方形棋盘的面积；
第二行为可以找到的最大矩形棋盘的面积。

Problem

【CERC2007】Robotic Sort

$\mathrm{Time\;Limit:\;5\;Sec}$
$\mathrm{Memory\;Limit:\;64\;MB}$

Description

Input

输入共两行，第一行为一个整数$N$，$N$表示物品的个数，$1\le N\le10^5$。
第二行为$N$个用空格隔开的正整数，表示$N$个物品最初排列的编号。

Output

输出共一行，$N$个用空格隔开的正整数$P_1,P_2,P_3\cdots P_n$，$P_i$表示第$i$次操作前第$i$小的物品所在的位置。
注意：如果第$i$次操作前，第$i$小的物品己经在正确的位置$P_i$上，我们将区间$[P_i,P_i]$反转(单个物品)。

Problem

【AHOI2009】Mincut最小割

$\mathrm{Time\;Limit:\;10\;Sec}$
$\mathrm{Memory\;Limit:\;162\;MB}$

Description

$\mathrm{A,B}$两个国家正在交战，其中$\mathrm{A}$国的物资运输网中有$N$个中转站，$M$条单向道路。
设其中第$i$ $(1\le i\le M)$条道路连接了$v_i,u_i$两个中转站，那么中转站$v_i$可以通过该道路到达$u_i$中转站，如果切断这条道路，需要代价$c_i$。
现在$\mathrm{B}$国想找出一个路径切断方案，使中转站$s$不能到达中转站$t$，并且切断路径的代价之和最小。
小可可一眼就看出，这是一个求最小割的问题。但爱思考的小可可并不局限于此。现在他对每条单向道路提出两个问题：
问题一：是否存在一个最小代价路径切断方案，其中该道路被切断？
问题二：是否对任何一个最小代价路径切断方案，都有该道路被切断？
请你回答这两个问题。

Input

第一行有$4$个正整数，依次为$N,M,s,t$。
第$2$行到第$(M+1)$行每行$3$个正整数$v,u,c$表示$v$中转站到$u$中转站之间有单向道路相连，单向道路的起点是$v$，终点是$u$，切断它的代价是$c$。
注意：两个中转站之间可能有多条道路直接相连。
同一行相邻两数之间可能有一个或多个空格。

Output

对每条单向边，按输入顺序，依次输出一行，包含两个非$0$即$1$的整数，分别表示对问题一和问题二的回答（其中输出$1$表示是，输出$0$表示否）。
同一行相邻两数之间用一个空格隔开，每行开头和末尾没有多余空格。