UVa 1428

Ping pong

from Chapter 3. Data Structures :: Maintaining Interval Data :: Examples

Description

有 N （3 ≤ N ≤ 20000）个乒乓球球员住在一条东西向的街上（可以把这个街认为是一条直线），每个球员都有唯一的排名。

为了提高他们的排名，他们经常互相挑战。如果两名球员想要进行一场比赛，他们必须选择另一名球员当比赛的裁判，并且比赛在裁判的房子里举办。由于某些原因，选手不可以选择排名比他们两个都低或者都高的球员作裁判。并且因为选手必须走路到裁判的房子参加比赛，所以选手希望他们走路的路径之和，不超过他们房屋的距离。（每位选手都很懒）

球员们都住在不同的房子中，没有两座房子在同一个地方。如果有两场比赛的裁判或任意一名球员不相同，我们就认为这是不同的两场比赛。现在问题来了：在这条乒乓球街上，可以举办多少种不同的比赛？

Input

输入的第一行是一个整数 T （1 ≤ T ≤ 20），表示有几组测试数据。紧接着有 T 行数据，每行表示一组测试数据。

每组测试数据包含 N + 1个整数。第一个整数是 N ，表示球员数。之后有N个不同的整数 a₁ , a₂ , ... , a_N ，按住处从西到东的顺序表示每个球员的排名（1 ≤ a_i ≤ 100000, i = 1... N ）。

Output

对于所有的测试数据，每行输出一个整数，表示可以举办的不同比赛的场数。

Solution

原题相当于给出一组序列 a₁ , a₂ , ... , a_n ，可以找出有多少组 i , j , k 符合 i ≤ j ≤ k ，且 a_i ≤ a_j ≤ a_k 或 a_i ≥ a_j ≥ a_k 成立。

我们可以枚举上述不等式中间的 a_j ，设 a₁ 到 a_j-1 中有 x_j 个比 a_j 小，则有 ( j - 1 - x_j ) 个比 a_j 大；同理，设 a_j+1 到 a_N 中有 y_j 个比 a_j 小，则有 ( N - j - y_j ) 个比 a_j 大。所以当 a_i ≤ a_j ≤ a_k 时， i 和 k 一共有 x_j · ( N - j - y_j ) 种组合，而当 a_i ≥ a_j ≥ a_k 时， i 和 k 一共有种 ( j - 1 - x_j ) · y_j 组合，最后的答案就是 [ x_j ( N - j - y_j ) + ( j - 1 - x_j ) y_j ] 。

剩下的工作就是求出 x_i 和 y_i 了。 x_i 可以这样计算：从左往右扫描 a_i ，用 c[v] 表示 a₁ , a₂ , ... , a_i-1 中， 值等于 v 的 a_i 是否出现（用 c[v] = 0 表示未出现， c[v] = 1 表示已出现），则 x_i = sum( a₁ , a₂ , ... , a_i-1 )。一开始 c[v] 初始化为0，在计算出 x_i 之后，将 c[v] ( v = a_i ) 标记为1，然后继续扫描 a_i+1 。为什么这么做呢？因为在这之中的 “求和” 和 “标记” 的操作正好是二叉索引树的经典用法。最后我们可以再从右往左扫描 a_i ，用同样的方法求出 y_i 就可以了。

这个算法的时间复杂度为 O(n·log(max{a_i})) 。