Problem

曼哈顿最小生成树

Description

平面坐标系内，给定个顶点。对于顶点，与之间的距离定义为。你的任务是求出这个顶点的最小生成树。

Input

第一行一个正整数，表示定点个数。
接下来行每行两个正整数，描述一个顶点。

Output

只有一行，为最小生成树的边的距离和。

Problem

【SCOI2007】组队

Description

每年都有球员选秀环节。通常用速度和身高两项数据来衡量一个篮球运动员的基本素质。假如一支球队里速度最慢的球员速度为，身高最矮的球员高度为，那么这支球队的所有队员都应该满足：。其中和为给定的经验值。这个式子很容易理解，如果一个球队的球员速度和身高差距太大，会造成配合的不协调。 请问作为球队管理层的你，在名选秀球员中，最多能有多少名符合条件的候选球员。

Input

第一行四个数。
下接行每行两个数描述一个球员的和。

Output

最多候选球员数目。

Problem

最假女选手

Description

在刚刚结束的水题嘉年华的压轴节目放水大赛中，如愿以偿的得到了最假女选手的奖项。但是作为主办人的为了证明确实在放水，决定出一道基础题考察的姿势水平。给定一个长度为序列，编号从到。要求支持下面几种操作：

1. 给一个区间加上一个数
2. 把一个区间里小于的数变成
3. 把一个区间里大于的数变成
4. 求区间的和
5. 求区间的最大值
6. 求区间的最小值

Input

第一行一个整数表示序列长度
第二行个整数表示初始序列
第三行一个整数表示操作个数
接下来行，每行三或四个整数，第一个整数表示操作类型，接下来或表述操作数

Output

对于每个类型的操作，输出一行一个整数表示答案

Problem

【SCOI2008】斜堆

Description

斜堆是一种常用的数据结构。它也是二叉树，且满足与二叉堆相同的堆性质：每个非根结点的值都比它父亲大。因此在整棵斜堆中，根的值最小。但斜堆不必是平衡的，每个结点的左右儿子的大小关系也没有任何规定。在本题中，斜堆中各个元素的值均不相同。
在斜堆中插入新元素的过程是递归进行的：

• 当为空或者小于的根结点时X变为新的树根，而原来的树根（如果有的话）变为的左儿子。
• 当大于的根结点时，根结点的两棵子树交换，而（递归）插入到交换后的左子树中。

给出一棵斜堆，包含值为的结点各一次。求一个结点序列，使得该斜堆可以通过在空树中依次插入这些结点得到。
如果答案不惟一，输出字典序最小的解。输入保证有解。

Input

第一行包含一个整数。
第二行包含个整数，表示是的左儿子，表示是的右儿子。
显然总是根，所以输入中不含。

Output

仅一行，包含整数，即字典序最小的插入序列。

Problem

YY的GCD

Description

神犇虐完数论后给出了一题：
给定，求且为质数的有多少对
这种必然不会了，于是向你来请教。
多组输入。

Input

第一行一个整数表述数据组数。
接下来行，每行两个正整数，表示。

Output

行，每行一个整数表示第组数据的结果。

Problem

【HNOI2008】神奇的国度

Description

国是一个热衷三角形的国度，连人的交往也只喜欢三角原则。他们认为三角关系：即相互认识，相互认识，相互认识，是简洁高效的。
为了巩固三角关系，国禁止四边关系，五边关系等等的存在。所谓边关系，是指个人之间仅存在对认识关系：，而没有其它认识关系。比如四边关系指四个人 ，，，相互认识，而，不认识。
全民比赛时，为了防止做弊，规定任意一对相互认识的人不得在一队。国王想知道，最少可以分多少支队。

Input

第一行两个整数。表示有个人，对认识关系。
接下来行每行输入一对朋友。

Output

输出一个整数，最少可以分多少队。

Problem

【HAOI2007】覆盖问题

Description

某人在山上种了棵小树苗。冬天来了，温度急速下降，小树苗脆弱得不堪一击，于是树主人想用一些塑料薄膜把这些小树遮盖起来，经过一番长久的思考，他决定用个的正方形塑料薄膜将小树遮起来。我们不妨将山建立一个平面直角坐标系，设第棵小树的坐标为，个的正方形的边要求平行与坐标轴，一个点如果在正方形的边界上，也算作被覆盖。当然，我们希望塑料薄膜面积越小越好，即求L最小值。

Input

第一行有一个正整数，表示有多少棵树。
接下来有行，第行有个整数，表示第棵树的坐标，保证不会有个树的坐标相同。

Output

一行，输出最小的值。

Problem

小猴打架

Description

一开始森林里面有只互不相识的小猴子，它们经常打架，但打架的双方都必须不是好朋友。每次打完架后，打架的双方以及它们的好朋友就会互相认识，成为好朋友。经过次打架之后，整个森林的小猴都会成为好朋友。 现在的问题是，总共有多少种不同的打架过程。 比如当时，就有 六种不同的打架过程。

Input

一个整数，

Output

一行，方案数。

Problem

【JSOI2007】合金

Description

某公司加工一种由铁、铝、锡组成的合金。他们的工作很简单。首先进口一些铁铝锡合金原材料，不同种类的原材料中铁铝锡的比重不同。然后，将每种原材料取出一定量，经过融解、混合，得到新的合金。新的合金的铁铝锡比重为用户所需要的比重。 现在，用户给出了种他们需要的合金，以及每种合金中铁铝锡的比重。公司希望能够订购最少种类的原材料，并且使用这些原材料可以加工出用户需要的所有种类的合金。

Input

第一行两个整数和，分别表示原材料种数和用户需要的合金种数。第到行，每行三个实数，分别表示铁铝锡在一种原材料中所占的比重。第到行，每行三个实数，分别表示铁铝锡在一种用户需要的合金中所占的比重。

Output

一个整数，表示最少需要的原材料种数。若无解，则输出。

Problem

【ZJOI2007】Hide捉迷藏

Description

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

• ：改变第个房间的照明状态，若原来打开，则关闭；若原来关闭，则打开。
• ：开始一次游戏，查询最远的两个关灯房间的距离。

Input

第一行包含一个整数，表示房间的个数，房间将被编号为的整数。接下来行每行两个整数，表示房间与房间之间有一条走廊相连。接下来一行包含一个整数，表示操作次数。接着行，每行一个操作，如上文所示。

Output

对于每一个操作，输出一个非负整数，表示最远的两个关灯房间的距离。
若只有一个房间是关着灯的，输出；若所有房间的灯都开着，输出。