解題區►解題區 - UVa

UVa 12663 - High bridge, low bridge

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

給水位消長的情況，請問有有多少塊地經過溼乾的次數大於等於 K。

Sample Input

1
2
3
4
5
6
7
8
9
2 2 2
2 5
6 2
8 3
5 3 2
2 3 4 5 6
5 3
4 2
5 2

Sample Output

1
2
Case 1: 1
Case 2: 3

Solution

先對地面高度作一次排序，來確保每一次消長會將一個區間的所有元素都 +1。

用 binary index tree 維護區間調整，單點查詢。

  1. 假設對於 [l, r] 都加上 v，則對於前綴對 A[l] += v, A[r+1] -= v 這樣保證前綴和不影響其結果。
  2. 單點查詢 B[l] 元素的結果 = sum(A[1, l])
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <vector>
using namespace std;
int A[131072], tree[131072];
void modify(int x, int N, int val) {
    while (x <= N) {
        tree[x] += val;
        x += x&(-x);
    }
}
int query(int x) {
    int ret = 0;
    while (x) {
        ret += tree[x];
        x -= x&(-x);
    }
    return ret;
}
int main() {
    int cases = 0;
    int N, M, K, l = 0, r;
    while (scanf("%d %d %d", &N, &M, &K) == 3) {
        for (int i = 1; i <= N; i++)
            scanf("%d", &A[i]);
        sort(A+1, A+1+N);
        memset(tree, 0, sizeof(tree));
        int p = 1;
        for (int i = 0; i < M; i++) {
            scanf("%d %d", &r, &l);
            p = upper_bound(A+1, A+1+N, p) - A;
            r = upper_bound(A+1, A+1+N, r) - A;
            if (p <= r) {
                modify(p, N, 1);
                modify(r, N, -1);
            }
            p = l;
        }
        
        int ret = 0;
        for (int i = 1; i <= N; i++) {
            int cnt = query(i);
            ret += cnt >= K;
        }
        printf("Case %d: %d\n", ++cases, ret);
    }
    return 0;
}
/*
 */