# BZOJ 1089: [SCOI2003]严格n元树（dp+python）

## Description

如果一棵树的所有非叶节点都恰好有n个儿子，那么我们称它为严格n元树。如果该树中最底层的节点深度为d
（根的深度为0），那么我们称它为一棵深度为d的严格n元树。例如，深度为２的严格２元树有三个，如下图：

## Input

仅包含两个整数n, d( 0   <   n   <   =   32,   0  < =   d  < = 16)

## Output

仅包含一个数，即深度为d的n元树的数目。

【样例输入1】
2 2
【样例输入2】
2 3

【样例输入3】
3 5

## Sample Output

【样例输出1】
3
【样例输出2】
21

【样例输出2】
58871587162270592645034001

因为OJ上py都是按照字符串来读入数据的，所以我们需要用相应的字符串函数把数据切分出来。比如读入了整数n。我们就需要:

strip()是把字符串的左右空格去掉，split是按照空格或者tab来切分。

# BZOJ 1067: [SCOI2007]降雨量（ST表）

## Description

我们常常会说这样的话：“X年是自Y年以来降雨量最多的”。它的含义是X年的降雨量不超过Y年，且对于任意
Y＜Z＜X，Z年的降雨量严格小于X年。例如2002，2003，2004和2005年的降雨量分别为4920，5901，2832和3890，

## Input

输入仅一行包含一个正整数n，为已知的数据。以下n行每行两个整数yi和ri，为年份和降雨量，按照年份从小

## Output

对于每一个询问，输出true，false或者maybe。

6
2002 4920
2003 5901
2004 2832
2005 3890
2007 5609
2008 3024
5
2002 2005
2003 2005
2002 2007
2003 2007
2005 2008

false
true
false
maybe
false

## HINT

100%的数据满足：1<=n<=50000, 1<=m<=10000, -10^9<=yi<=10^9, 1<=ri<=10^9

# SPOJ DRUIDEOI – Fata7y Ya Warda!（破环成链+单调栈）

Druid (AKA Amr Alaa El-Deen) and little EOIers have finished their training and they are playing “Fatta7y ya warda!”. It’s a kids game when everyone holds hands with two other kids forming a circle, and they keep saying “Fatta7y ya warda!” (Flourish, flower!) (moving away from each other, while still holding hands, to form a huge circle), then “2affely ya warda!” (Die, flower!) (moving back as close to each other as possible, while still holding hands, to form a tiny circle, i.e. a point). That’s it!

Anyway the point is…

While Eagle (AKA Mohamed Ahmed) was watching them playing he was wondering, who’s the first person taller than Druid on his left? Similarly, who’s the first person taller than Druid on his right? Help Eagle find the answer for each person not just Druid.

### Input

The input starts with an integer T (1 ≤ T ≤ 20), the number of test cases.

Each test case contains two lines. The first line contains a single integer N (1 ≤ N ≤ 105), the number of persons playing the game. The second line contains N integers hi (1 ≤ hi ≤ 109) the height of the i-th person. They are numbered 1 to N starting from Druid.

### Output

For each test case print N lines, in the i-th line print 2 numbers, the index of the first person taller than the i-th person on his left, and the index of the first person taller than the i-th person on his right. If no one is taller than the i-th person print -1 -1.