POJ 3928 - Ping pong

http://poj.org/problem?id=3928

概要

\(N\) 人のプレイヤーが一列に並んでおり、各プレイヤーには一意のランク \(a_i\) が割り当てられている。

卓球のゲームを行うには、2人のプレイヤーと1人の審判が必要である。 このとき、審判は2人のプレイヤーの間にいる人であり、かつ審判のランクは両方のプレイヤーのランクより高かったり、逆に両方のプレイヤーより低かったりしてはならない。

このとき、何通りの試合の組み合わせが存在するかを答える。 いずれかのプレイヤー、または審判が異なる人であれば異なる試合である。

制約

解法

\(i\) 番目の人が審判になる試合を考えると、組み合わせの数は

の和となる。

これは BinaryIndexedTree を用いて \(O(\log a_i)\) で数えることができ、全体で計算量は \(O(N \log a_i)\) となって間に合う。

 1 #include <cstdio>
 2 #include <algorithm>
 3 using namespace std;
 4 
 5 template <class T>/*{{{*/
 6 struct BinaryIndexedTree
 7 {
 8   T tree;
 9   const int size;
10   BinaryIndexedTree(const T& t, int s) : tree(t), size(s) {}
11   // i 番目までの要素の累積和
12   int read(int i) const
13   {
14     int sum = 0;
15     while (i > 0) {
16       sum += tree[i];
17       i -= i & -i;
18     }
19     return sum;
20   }
21 
22   // i 番目の要素
23   int read_single(int i) const
24   {
25     int sum = tree[i];
26     if (i > 0) {
27       const int z = i - (i & -i);
28       --i;
29       while (i != z) {
30         sum -= tree[i];
31         i -= (i & -i);
32       }
33     }
34     return sum;
35   }
36 
37   void add(int i, int v)
38   {
39     while (i <= size) {
40       tree[i] += v;
41       i += (i & -i);
42     }
43   }
44 };/*}}}*/
45 
46 int main()
47 {
48   int T;
49   scanf("%d", &T);
50   while (T-- > 0) {
51     int N;
52     scanf("%d", &N);
53     static int a[20000];
54     for (int i = 0; i < N; i++) {
55       scanf("%d", &a[i]);
56     }
57     static const int M = 100000;
58     static int mem[M+1];
59     fill_n(mem, M+1, 0);
60     BinaryIndexedTree<int*> bit(mem, M);
61     static int xs[20000];
62     for (int i = 0; i < N; i++) {
63       xs[i] = bit.read(a[i]);
64       bit.add(a[i], 1);
65     }
66     fill_n(mem, M+1, 0);
67     long long ans = 0;
68     for (int i = N-1; i >= 0; i--) {
69       int n = bit.read(a[i]);
70       ans += static_cast<long long>(xs[i] * ((N-i-1)-n));
71       ans += static_cast<long long>((i-xs[i]) * n);
72       bit.add(a[i], 1);
73     }
74     printf("%lld\n", ans);
75   }
76   return 0;
77 }
poj/3928.cc