NIRVANA

Problem

【AHOI2008】Meet 紧急集合

Description

欢乐岛上有个非常好玩的游戏，叫做“紧急集合”。在岛上分散有$N$个等待点，有$N-1$条道路连接着它们，每条道路都连接某两个等待点，且通过这些道路可以走遍所有的等待点，通过道路从一点到另一点要花费一个游戏币。参加游戏的三人一组，开始的时候，所有人员均任意分散在各个等待点上（每个点同时允许多个人等待），每个人均带有足够多的游戏币（用于支付使用道路的花费）、地图（标明等待点之间道路连接的情况）以及对讲机（用于和同组的成员联系）。当集合号吹响后，每个成员之间迅速联系，了解到自己组所有成员所在的等待点后，迅速在$N$个等待点中确定一个集合点，组内所有成员将在该集合点集合，集合所用花费最少的组将是游戏的赢家。
小可可和他的朋友邀请你一起参加这个游戏，有你来选择集合点，聪明的你能够完成这个任务，帮助小可可赢得游戏吗？

Input

第一行两个正整数$N$和$M$（$N\le 5\times 10^5$，$M\le 5\times 10^5$），之间用一个空格隔开。分别表示等待点的个数（等待点也从$1$到$N$进行编号）和获奖所需完成的集合次数。
随后有$N-1$行，每行两个正整数$A$和$B$，之间用空格隔开，表示编号为$A$和编号为$B$的等待点之间有一条路。
接着还有$M$行，每行用三个正整数表示某次集合前小可可、小可可的朋友以及你所在的等待点的编号。

Output

一共有$M$行，每行两个数$P$和$C$，用一个空格隔开。其中第$i$行表示第$i$次集合点选择在编号为$P$的等待点，集合总共的花费是$C$个游戏币。

Problem

【POI2007】大都市meg

Description

经济全球化浪潮的影响下,习惯于漫步在清晨的乡间小路的邮递员$Blue Mary$也开始骑着摩托车传递邮件了。不过，她经常回忆起以前在乡间漫步的情景。昔日，乡下有依次编号为$1\sim n$的$n$个小村庄，某些村庄之间有一些双向的土路。从每个村庄都恰好有一条路径到达村庄$1$（即比特堡）。并且，对于每个村庄，它到比特堡的路径恰好只经过编号比它的编号小的村庄。另外，对于所有道路而言，它们都不在除村庄以外的其他地点相遇。在这个未开化的地方，从来没有过高架桥和地下铁道。随着时间的推移，越来越多的土路被改造成了公路。至今，$Blue Mary$还清晰地记得最后一条土路被改造为公路的情景。现在，这里已经没有土路了——所有的路都成为了公路，而昔日的村庄已经变成了一个大都市。 $Blue Mary$想起了在改造期间她送信的经历。她从比特堡出发，需要去某个村庄，并且在两次送信经历的间隔期间,有某些土路被改造成了公路.现在$Blue Mary$需要你的帮助：计算出每次送信她需要走过的土路数目。（对于公路，她可以骑摩托车；而对于土路，她就只好推车了。）

Input

第一行是一个数$n$ ($1\le n\le 250000$)
以下$n-1$行，每行两个整数$a,b$($1\le a < b\le n$)，表示原有一条路连接$a$和$b$
以下一行，包含一个整数$m$($1\le m\le 250000$)，表示$Blue Mary$曾经在改造期间送过$m$次信。
以下$n+m-1$行，每行有两种格式的若干信息，表示按时间先后发生过的$n+m-1$次事件:
若这行为 $A\ a\ b$ ($1\le a < b\le n$)，表示将$a$到$b$的土路修为公路。
若这行为 $W\ a$, 则表示$Blue Mary$曾经从比特堡送信到村庄$a$。

Output

有m行，每行包含一个整数，表示对应的某次送信时经过的土路数目。

Problem

小Z的袜子

Description

作为一个生活散漫的人，小$Z$每天早上都要耗费很久从一堆五颜六色的袜子中找出一双来穿。终于有一天，小$Z$再也无法忍受这恼人的找袜子过程，于是他决定听天由命……
具体来说，小$Z$把这$N$只袜子从$1$到$N$编号，然后从编号$L$到$R$(尽管小$Z$并不在意两只袜子是不是完整的一双，甚至不在意两只袜子是否一左一右，他却很在意袜子的颜色，毕竟穿两只不同色的袜子会很尴尬)。
你的任务便是告诉小$Z$，他有多大的概率抽到两只颜色相同的袜子。当然，小$Z$希望这个概率尽量高，所以他可能会询问多个$(L,R)$以方便自己选择。

Input

输入文件第一行包含两个正整数$N$和$M$。$N$为袜子的数量，$M$为小$Z$所提的询问的数量。接下来一行包含$N$个正整数$C_i$，其中$C_i$表示第$i$只袜子的颜色，相同的颜色用相同的数字表示。再接下来$M$行，每行两个正整数$L$，$R$表示一个询问。

Output

包含$M$行，对于每个询问在一行中输出分数$A/B$表示从该询问的区间$[L,R]$中随机抽出两只袜子颜色相同的概率。若该概率为$0$则输出$0/1$，否则输出的$A/B$必须为最简分数。

Problem

最长回文

Time Limit: $4000/2000 MS (Java/Others)$
Memory Limit: $32768/32768 K (Java/Others)$

Problem Description

给出一个只由小写英文字符$a,b,c\cdots y,z$组成的字符串$S$, 求$S$中最长回文串的长度.
回文就是正反读都是一样的字符串, 如$aba$, $abba$等

Input

输入有多组$case$,不超过$120$组,每组输入为一行小写英文字符$a,b,c\cdots y,z$组成的字符串$S$
两组$case$之间由空行隔开(该空行不用处理)
字符串长度$len\le 110000$

Output

每一行一个整数$x$,对应一组$case$,表示该组$case$的字符串中所包含的最长回文长度.

Problem

Dynamic len(set(a[L:R]))

Description

In python, we can use len(start(a[L:R])) to calculate the number of distinct values of elements $a[L],a[L + 1], \cdots,a[R-1]$.
Tere are some interactive examples that may help you understand how it is done. Remember that the indices of python lists start from $0$.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

>>>
a=[1,2,1,3,2,1,4]
>>> print a[1:6]
[2, 1, 3, 2, 1]
>>> print set(a[1:6])
set([1, 2, 3])
>>> print
len(set(a[1:6]))
3
>>> a[3]=2
>>> print
len(set(a[1:6]))
2
>>> print len(set(a[3:5]))
1

Your task is to simulate this process.

Input

There will be only one test case. The first line contains two integers $n$ and $m$ $(1\le n,m\le 50,000)$.
The next line contains the original list.
All the integers are between $1$ and $1,000,000$ (inclusive). The next m lines contain the statements
that you need to execute.
A line formatted as ‘$M$ $x$ $y$’ $(1\le y\le 1,000,000)$ means $a[x] = y$, and a line formatted as ‘$Q$ $x$
$y$’ means $print\ len(set(a[x : y]))$.
It is guaranteed that the statements will not cause $index$ $out$ $of$ $range$ error.

Output

Print the simulated result, one line for each query.

Problem

【SDOI2008】校门外的区间

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

Description

受校门外的树这道经典问题的启发，$A$君根据基本的离散数学的知识，抽象出$5$种运算维护集合$S$($S$初始为空)并最终输出$S$。现在，请你完成这道校门外的树之难度增强版——校门外的区间。
$5$种运算如下：

基本集合运算如下：

Input

输入共$M$行。
每行的格式为$X$ $T$，用一个空格隔开，$X$表示运算的种类，$T$为一个区间(区间用$(a,b), (a,b], [a,b), [a,b]$表示)。

Output

共一行，即集合$S$，每个区间后面带一个空格。若$S$为空则输出$empty$ $set$。

Problem

善意的投票

题目描述

幼儿园里有$n$个小朋友打算通过投票来决定睡不睡午觉。对他们来说，这个问题并不是很重要，于是他们决定发扬谦让精神。
虽然每个人都有自己的主见，但是为了照顾一下自己朋友的想法，他们也可以投和自己本来意愿相反的票。我们定义一次投票的冲突数为好朋友之间发生冲突的总数加上和所有和自己本来意愿发生冲突的人数。
我们的问题就是，每位小朋友应该怎样投票，才能使冲突数最小？

输入输出格式

输入格式
文件的第一行只有两个整数$n$，$m$，保证有$2\le n\le 300$，$1\le m\le n\times (n-1)/2$。
其中$n$代表总人数，$m$代表好朋友的对数。文件第二行有$n$个整数，第$i$个整数代表第$i$个小朋友的意愿，当它为$1$时表示同意睡觉，当它为$0$时表示反对睡觉。接下来文件还有$m$行，每行有两个整数$i$，$j$。表示$i$，$j$是一对好朋友，我们保证任何两对$i$，$j$不会重复。
输出格式
只需要输出一个整数，即可能的最小冲突数。

Problem

【JSOI2008】星球大战

题目描述

很久以前，在一个遥远的星系，一个黑暗的帝国靠着它的超级武器统治者整个星系。某一天，凭着一个偶然的机遇，一支反抗军摧毁了帝国的超级武器，并攻下了星系中
几乎所有的星球。这些星球通过特殊的以太隧道互相直接或间接地连接。但好景不长，很快帝国又重新造出了他的超级武器。凭借这超级武器的力量，帝国开始有计划地
摧毁反抗军占领的星球。由于星球的不断被摧毁，两个星球之间的通讯通道也开始不可靠起来。现在，反抗军首领交给你一个任务：给出原来两个星球之间的以太隧道连
通情况以及帝国打击的星球顺序，以尽量快的速度求出每一次打击之后反抗军占据的星球的连通快的个数。（如果两个星球可以通过现存的以太通道直接或间接地连通，
则这两个星球在同一个连通块中）。

输入输出格式

输入格式
输入文件第一行包含两个整数，$N (1\le N\le 2\times M)$ 和$M (1\le M\le 2\times 10^5)$，分别表示星球的数目和以太隧道的数目。星球用$0\sim N-1$的整数编号。
接下来的$M$行，每行包括两个整数$X, Y$，其中（$0\le X,Y<N$且$X\ne Y$），表示星球$X$和星球$Y$之间有以太隧道。注意所有的以太隧道都是双向的。
接下来一行是一个整数$K$，表示帝国计划打击的星球个数。
接下来的$K$行每行一个整数$X$，满足$0\le X<N$，表示帝国计划打击的星球编号。帝国总是按输入的顺序依次摧毁星球的。
输出格式
输出文件的第一行是开始时星球的连通块个数。
接下来的$K$行，每行一个整数，表示经过该次打击后现存星球的连通块个数。

Problem

切糕

Description

经历千辛万苦小$A$得到了一块切糕，切糕的形状是长方体，小$A$打算拦腰将切糕切成两半分给小$B$。出于美观考虑，小$A$希望切面能尽量光滑且和谐。于是她找到你，希望你能帮她找出最好的切割方案。
出于简便考虑，我们将切糕视作一个长$P$，宽$Q$，高$R$的长方体点阵。我们将位于第$z$层中第$x$行，第$y$列上的点称为$(x,y,z)$，它有一个非负的不和谐值$v(x,y,z)$。一个合法的切面满足以下两个条件：

1. 与每个纵轴有且仅有一个交点。即切面是一个函数$f(x,y)$，对于所有$1≤x≤P$，$1≤y≤Q$，我们需指定一个切割点$f(x,y)$，且 $1≤f(x,y)≤R$。
2. 切面需要一定的光滑性要求，即相邻纵轴上的切割点不能相距太远。对于所有 $1\le x,x'\le P$ 和 $1\le y,y'\le Q$，若 $|x-x'|+|y-y'|=1$，则 $|f(x,y)-f(x',y')|\le D$, 其中$D$是给定的一个非负整数。

能有许多切面满足上面的条件，小$A$希望找出总的切割点上的不和谐值最小的那个，即$\sum_{x=1}^{P}\sum_{y=1}^{Q} v(x,y,f(x,y))$最小。

Input

第一行是三个正整数$P,Q,R$，表示切糕的长$P$、 宽$Q$、高$R$。第二行有一个非负整数$D$，表示光滑性要求。接下来是$R$个$P$行$Q$列的矩阵，第$z$个矩阵的第$x$行第$y$列是$v(x,y,z) (1\le x\le P, 1\le y\le Q, 1\le z\le R)$。
$100\%$的数据满足$P,Q,R\le 40$，$0\le D\le R$，且给出的所有的不和谐值不超过$1000$。

Output

仅包含一个整数，表示在合法基础上最小的总不和谐值。

Problem

【HNOI2008】越狱

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

Description

监狱有连续编号为$1\sim N$的$N$个房间，每个房间关押一个犯人，有$M$种宗教，每个犯人可能信仰其中一种。如果相邻房间的犯人的宗教相同，就可能发生越狱，求有多少种状态可能发生越狱。

Input

输入两个整数$M$，$N$ 。

Output

能越狱的状态数，答案模$100003$ 。