POJ 3067 - Japan

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

概要

N 個の東海岸の街と M 個の西海岸の街の間に K 本の真っ直ぐな superhighway をつくる． それぞれの街は北から 1, 2 ... と番号が割り当てられている． そのときに，superhighway が交差している箇所が何箇所あるかを答える．

一箇所で交差している superhighway は高々2本と考えてよい．

制約

解法

superhighway が結ぶ街の番号の大小関係が逆転している数を数えればいい．

これをナイーブに数えると O( K^2 ) かかる． K についての制約が無いので N*M = 10^6 くらいまできてもおかしくないので，これだと TLE する．

そこで Binary Indexed Tree を使うことでこれを O(K log K) で数えた．

 1 #include <cstdio>
 2 #include <vector>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 template <class T>
 7 struct BinaryIndexedTree
 8 {
 9   T tree;
10   const int size;
11   BinaryIndexedTree(const T& t, int s) : tree(t), size(s) {}
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   void add(int i, int v)
23   {
24     while (i <= size) {
25       tree[i] += v;
26       i += (i & -i);
27     }
28   }
29 };
30 
31 int main()
32 {
33   int T;
34   scanf("%d", &T);
35   for (int Ti = 1; Ti <= T; Ti++) {
36     int N, M, K;
37     scanf("%d %d %d", &N, &M, &K);
38     vector<pair<int,int> > v(K);
39     for (int i = 0; i < K; i++) {
40       scanf("%d %d", &v[i].first, &v[i].second);
41     }
42 
43     sort(v.begin(), v.end());
44     static int mem[1001];
45     fill_n(mem, M+1, 0);
46     BinaryIndexedTree<int*> bit(mem, M);
47     long long ans = 0LL;
48     for (vector<pair<int,int> >::const_iterator it(v.begin()); it != v.end(); ++it) {
49       ans += static_cast<long long>(bit.read(M - it->second + 1));
50       bit.add(M - it->second + 2, 1);
51     }
52     printf("Test case %d: %lld\n", Ti, ans);
53   }
54   return 0;
55 }
poj/3067.cc