Input:
10 10
7 6 2 4 0 8 3 6 5 3 
3 4 1
1 6 2
4 9 5
4 9 4
9 10 1
3 6 3
3 3 1
8 9 1
5 8 3
5 7 2
Output:
2
2
6
5
3
4
2
5
6
3


Input:
20 20
17 16 2 4 10 8 13 6 15 13 13 12 8 0 5 3 13 18 2 8 
10 14 4
10 15 5
16 19 1
3 16 7
3 8 1
11 18 7
14 15 2
3 16 10
12 17 6
2 7 1
4 18 13
3 8 3
9 11 1
19 20 1
2 20 3
2 19 12
8 20 1
2 3 1
13 20 5
6 12 6
Output:
13
13
2
8
2
13
5
12
13
2
13
6
13
2
2
13
0
2
8
13

其实，你也可以写个朴素对拍，我就是这么做的。

PS:这是目前为止我在POJ上交过的最长的程序了，写了4KB，值得纪念。

• 你给的数据有问题吧？ (12) huyuncongh 2011-07-29 14:55:01
• Re:Treap三秒钟水过……提供2组数据…… (693) coolFires 2013-04-15 16:20:59
• Re:Treap三秒钟水过……提供2组数据…… (53) dieyidezui 2013-05-30 09:56:11