2015
02-22

# How Many W

Given a sequence (S_1, S_2, …, S_N) (1 <= S_i <= 1,000,000,000, S_i != S_j), count the number of W, which can be regarded as a quintuple (a, b, c, d, e) satisfying a < b < c < d < e, S_b < S_c < S_a, S_d < S_c < S_e.

The beginning of the input is an integer T, which is the number of test cases. T cases are followed. The first line of each test case is an integer N (1 <= N <= 100,000), which denotes the length of the sequence. The second line is N integer S_1, S_2, …, S_N, which denote the sequence.

The beginning of the input is an integer T, which is the number of test cases. T cases are followed. The first line of each test case is an integer N (1 <= N <= 100,000), which denotes the length of the sequence. The second line is N integer S_1, S_2, …, S_N, which denote the sequence.

2
5
5 1 3 2 4
6
6 1 3 4 2 5

1
3

1. 约瑟夫也用说这么长……很成熟的一个问题了，分治的方法解起来o(n)就可以了，有兴趣可以看看具体数学的第一章，关于约瑟夫问题推导出了一系列的结论，很漂亮

2. 给你一组数据吧：29 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 1000。此时的数据量还是很小的，耗时却不短。这种方法确实可以，当然或许还有其他的优化方案，但是优化只能针对某些数据，不太可能在所有情况下都能在可接受的时间内求解出答案。