NIRVANA

Problem

楼房重建

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

Description

$\mathrm{小A}$的楼房外有一大片施工工地，工地上有$N$栋待建的楼房。每天，这片工地上的房子拆了又建、建了又拆。他经常无聊地看着窗外发呆，数自己能够看到多少栋房子。
为了简化问题，我们考虑这些事件发生在一个二维平面上。$\mathrm{小A}$在平面上$(0,0)$点的位置，第$i$栋楼房可以用一条连接$(i,0)$和$(i,H_i)$的线段表示，其中$H_i$为第$i$栋楼房的高度。如果这栋楼房上任何一个高度大于$0$的点与$(0,0)$的连线没有与之前的线段相交，那么这栋楼房就被认为是可见的。
施工队的建造总共进行了$M$天。初始时，所有楼房都还没有开始建造，它们的高度均为$0$。在第$i$天，建筑队将会将横坐标为$X_i$的房屋的高度变为$Y_i$(高度可以比原来大——修建，也可以比原来小——拆除，甚至可以保持不变——建筑队这天什么事也没做)。请你帮$\mathrm{小A}$数数每天在建筑队完工之后，他能看到多少栋楼房？

Input

第一行两个正整数$N,M$。
接下来$M$行，每行两个正整数$X_i,Y_i$。

Output

$M$行，第$i$行一个整数表示第$i$天过后$\mathrm{小A}$能看到的楼房有多少栋。

Problem

【NOI2004】郁闷的出纳员

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

Description

$\mathrm{OIER}$公司是一家大型专业化软件公司，有着数以万计的员工。作为一名出纳员，我的任务之一便是统计每位员工的工资。
这本来是一份不错的工作，但是令人郁闷的是，我们的老板反复无常，经常调整员工的工资。如果他心情好，就可能把每位员工的工资加上一个相同的量。反之，如果心情不好，就可能把他们的工资扣除一个相同的量。我真不知道除了调工资他还做什么其它事情。
工资的频繁调整很让员工反感，尤其是集体扣除工资的时候，一旦某位员工发现自己的工资已经低于了合同规定的工资下界，他就会立刻气愤地离开公司，并且再也不会回来了。每位员工的工资下界都是统一规定的。每当一个人离开公司，我就要从电脑中把他的工资档案删去，同样，每当公司招聘了一位新员工，我就得为他新建一个工资档案。
老板经常到我这边来询问工资情况，他并不问具体某位员工的工资情况，而是问现在工资第$k$多的员工拿多少工资。每当这时，我就不得不对数万个员工进行一次漫长的排序，然后告诉他答案。
好了，现在你已经对我的工作了解不少了。正如你猜的那样，我想请你编一个工资统计程序。怎么样，不是很困难吧？

Input

第一行有两个非负整数$n$和$min$。$n$表示下面有多少条命令，$min$表示工资下界。
接下来的$n$行，每行表示一条命令。命令可以是以下四种之一：

$\mathrm{I}$命令、$\mathrm{A}$命令、$\mathrm{S}$命令中的$k$是一个非负整数，$\mathrm{F}$命令中的$k$是一个正整数。
在初始时，可以认为公司里一个员工也没有。
$\mathrm{I}$命令的条数不超过$10^5$
$\mathrm{A}$命令和$\mathrm{S}$命令的总条数不超过$100$
$\mathrm{F}$命令的条数不超过$10^5$
每次工资调整的调整量不超过$1000$
新员工的工资不超过$10^5$

Output

输出行数为$\mathrm{F}$命令的条数加一。
对于每条$\mathrm{F}$命令，你的程序要输出一行，仅包含一个整数，为当前工资第$k$多的员工所拿的工资数，
如果$k$大于目前员工的数目，则输出$-1$。
输出文件的最后一行包含一个整数，为离开公司的员工的总数。

Problem

【BJWC2017】神秘物质

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

Description

$\mathrm{21ZZ}$年，冬。
小诚退休以后，不知为何重新燃起了对物理学的兴趣。他从研究所借了些实验仪器，整天研究各种微观粒子。
这一天，小诚刚从研究所得到了一块奇异的陨石样本，便迫不及待地开始观测。在精密仪器的视野下，构成陨石的每个原子都无比清晰。
小诚发现，这些原子排成若干列，每一列的结构具有高度相似性。于是，他决定对单独一列原子进行测量和测试。
被选中的这列共有$N$个顺序排列的原子。最初，第$i$个原子具有能量$E_i$。随着时间推移和人为测试，这列原子在观测上会产生两种变化：

• $merge\;x\;e$：当前第$x$个原子和第$x+1$个原子合并，得到能量为$e$的新原子；
• $insert\;x\;e$：在当前第$x$个原子和第$x+1$个原子之间插入一个能量为$e$的新原子。

对于一列原子，小诚关心的是相邻一段中能量最大和能量最小的两个原子的能量差值，称为区间极差。因此，除了观测变化外，小诚还要经常统计这列原子的两类数据：

• $max\;x\;y$：当前第$x$到第$y$个原子之间的任意子区间中区间极差的最大值；
• $min\;x\;y$：当前第$x$到第$y$个原子之间的任意子区间中区间极差的最小值。

其中，子区间指的是长度至少是$2$的子区间。
小诚坚信这项研究可以获得诺贝尔物理学奖。为了让小诚早日了结心愿，你能否帮助他实现上述的观测和测量呢？

Input

第一行，两个整数$N,M$，分别表示最初的原子数目和事件总数。
第二行，$N$个整数$E_1,E_2,\cdots,E_N$，由空格隔开，依次表示每个原子的能量。
接下来$M$行， 每行为一个字符串和两个整数， 描述一次事件，格式见题目描述。

Output

输出若干行， 按顺序依次表示每次$max$和$min$类事件的测量结果。

Problem

【HEOI2013】Segment

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

Description

要求在平面直角坐标系下维护两个操作：

1. 在平面上加入一条线段。记第$i$条被插入的线段的标号为$i$。
2. 给定一个数$k$，询问与直线$x=k$相交的线段中，交点最靠上的线段的编号。

Input

第一行一个整数$n$，表示共$n$个操作。
接下来$n$行，每行第一个数为$0$或$1$。
若该数为$0$，则后面跟着一个正整数$k$，表示询问与直线$x=((k+lastans–1)\%39989+1)$相交的线段中交点（包括在端点相交的情形）最靠上的线段的编号，其中$\%$表示取余。若某条线段为直线的一部分，则视作直线与线段交于该线段$y$坐标最大处。若有多条线段符合要求，输出编号最小的线段的编号。
若该数为$1$，则后面跟着四个正整数$x_0,y_0,x_1,y_1$，表示插入一条两个端点为$((x_0+lastans-1)\%39989+1$,$(y_0+lastans-1)\%10^9+1)$和$((x_1+lastans-1)\%39989+1$,$(y_1+lastans-1)$的线段。
其中$lastans$为上一次询问的答案。初始时$lastans=0$。

Output

对于每个$0$操作，输出一行，包含一个正整数，表示交点最靠上的线段的编号。
若不存在与直线相交的线段，答案为$0$。

Problem

最大团

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

Description

给出平面上$N$个点的坐标，和一个半径为$R$的圆心在原点的圆。
对于两个点，它们之间有连边，当且仅当它们的连线与圆不相交。
求此图的最大团。

Input

第一行两个整数$N$和$R$, 表示点数和圆的半径。
接下来$N$行，每行两个整数$x_i$和$y_i$，表示第$i$个点的坐标
保证每个点都严格在园外，且两两直线不与圆相切。

Output

输出一个整数：最大团的大小。

Problem

【HNOI2008】Cards

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

Description

小春现在很清闲，面对书桌上的$N$张牌，他决定给每张染色。
目前小春只有$3$种颜色：红色，蓝色，绿色。他询问$\mathrm{Sun}$有多少种染色方案，$\mathrm{Sun}$很快就给出了答案。
进一步，小春要求染出$Sr$张红色，$Sb$张蓝色，$Sg$张绿色。他又询问有多少种方案，$\mathrm{Sun}$想了一下，又给出了正确答案。
最后小春发明了$M$种不同的洗牌法，他又问$\mathrm{Sun}$有多少种不同的染色方案。两种染色方法相同当且仅当其中一种可以通过任意的洗牌法（即可以使用多种洗牌法，而每种方法可以使用多次）洗成另一种。
$\mathrm{Sun}$发现这个问题有点难度，决定交给你。
答案可能很大，只要求出答案除以$P$的余数（$P$为质数）。

Input

第一行输入$5$个整数：$Sr,Sb,Sg,m,p$。$n=Sr+Sb+Sg$。
接下来$m$行，每行描述一种洗牌法，每行有$n$个用空格隔开的整数$X_1X_2\cdots X_n$，恰为$1$到$n$的一个排列，表示使用这种洗牌法，第$i$位变为原来的$X_i$位的牌。
数据保证任意多次洗牌都可用$m$种洗牌法中的一种代替，且对每种洗牌法，都存在一种洗牌法使得能回到原状态。

Output

不同染法除以$P$的余数。

Problem

概率好题

$\mathrm{Time\;Limit:\;4\;Sec}$
$\mathrm{Memory\;Limit:\;131072\;KB}$

Description

甲乙进行比赛，他们各有$k_1,k_2$个集合$[L_i,R_i]$，每次随机从他们拥有的每个集合中都取出一个数。
$S_1=\sum甲取出的数$，$S_2$同理。若$S_1>S_2$甲胜；若$S_1=S_2$平局；否则乙胜。
分别求出甲胜、平局、乙胜的概率。
（显然这个概率是有理数，记为$\frac{p}{q}$，则输出答案为$\frac{p}{q}\bmod{10^9+7}$（逆元）
注意：多组数据

Input

一个数，数据组数$(T\le5)$
对于每组数据 输入顺序为

1
2

k1 L1 R1 ... Lk1 Rk1
k2 L1 R1 ... Lk2 Rk2

$(k_1,k_2\le8,1\le L\le R\le10^7)$

Output

甲胜、平局、乙胜的概率。

Problem

Synchronized Subsequence

$\mathrm{Time\;limit:\;2\;Sec}$
$\mathrm{Memory\;limit:\;1024\;MB}$

Statement

You are given a string $S$ of length $2N$, containing $N$ occurrences of a and $N$ occurrences of b.
You will choose some of the characters in $S$. Here, for each $i=1,2,\cdots,N$, it is not allowed to choose exactly one of the following two: the $i^{th}$ occurrence of a and the $i^{th}$ occurrence of b. (That is, you can only choose both or neither.) Then, you will concatenate the chosen characters (without changing the order).
Find the lexicographically largest string that can be obtained in this way.

Constraints

$1\le N\le3000$
$S$ is a string of length $2N$ containing $N$ occurrences of a and $N$ occurrences of b.

Input

Input is given from Standard Input in the following format:
$N\\S$

Output

Print the lexicographically largest string that satisfies the condition.

Problem

【POI2007】对称轴osi

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

Description

$\mathrm{FGD}$小朋友——一个闻名遐迩的年轻数学家——有一个小MM，$\mathrm{yours}$。$\mathrm{FGD}$小朋友非常喜欢他的MM，所以他很乐意帮助他的MM做数学作业。但是，就像所有科学的容器一样，FGD的大脑拒绝不停地重复思考同样的问题。不幸的是，$\mathrm{yours}$是一个十分用功的学生，所以她不停地让$\mathrm{FGD}$帮助她检查她的作业。
一个阳光明媚的周末，$\mathrm{yours}$的数学老师布置了非常多的寻找多边形的对称轴的题，足够她做相当长的一段时间了。在此之前$\mathrm{FGD}$已经决定去海边度过这个难得的假期，不过他还是觉得应该帮助他的MM对付可爱的数学作业。很快地，他找到了解决方案，最好写一个程序来帮助$\mathrm{yours}$检查她的数学作业。
因为$\mathrm{FGD}$并非一个计算机科学家，所以他找到了他的好朋友你，请你帮助他完成这个任务。
请写一个程序：读入多边形的描述计算出每个多边形的对称轴数将计算的结果输出。

Input

输入的第一行包含一个正整数$T\;(1\le T\le10)$，为多边形的边数。
接下来，为$T$个多边形的描述。
每个描述的第一行为一个正整数$n\;(3\le n\le10^5)$，表示了多边形的点数。
后面$n$行每行两个整数$x$和$y\;(-10^8\le x, y\le10^8)$，依次表示多边形的顶点坐标。
多边形不一定是凸的，但是不自交。任何两条边都只有最多一个公共点，即它们的公共端点。此外，没有两条连续的边平行。

Output

你的程序应该输出正好$T$行，第k行包含了一个整数$n_k$——表示第$k$个多边形有多少个对称轴。

Problem

【TJOI2018】Party

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

Description

小豆参加了$\mathrm{NOI}$的游园会，会场上每完成一个项目就会获得一个奖章，奖章只会是N,O,I的字样。在会场上他收集到了$K$个奖章组成的串。
兑奖规则是奖章串和兑奖串的最长公共子序列长度为小豆最后奖励的等级。
现在已知兑奖串长度为$N$，并且在兑奖串上不会出现连续三个奖章为NOI，即奖章中不会出现子串NOI。
现在小豆想知道各个奖励等级会对应多少个不同的合法兑奖串。

Input

第一行两个数，$N,K$分别代表兑奖串的长度，小豆收集的奖章串的长度。
第二行一共$K$个字符，表示小豆得到奖章串。

Output

一共$K+1$行，第$i$行表示小豆最后奖励等级为$i-1$的不同的合法兑奖串的个数，可能这个数会很大，结果对$10^9+7$取模。