解題區/解題區 - UVa

UVa 12890 - Easy Peasy

contents

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

Problem

給一串整數序列，請問有多少連續的區間，區間不包含重複的數字。

Sample Input

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

Sample Output

1
2
5
12

Solution

窮舉每一個點當作區間左端點，向左延伸的最遠的右端點必然非遞減。

掃描線計算右端點。效率 O(n log n)。

掛上輸入優化、HASH 會來得更快。

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
#include <stdio.h>
#include <map>
#include <algorithm>
using namespace std;
int main() {
    int testcase, n, x;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        map<int, int> R;
        int low = 0;
        long long ret = 0;
        for (int i = 1; i <= n; i++) {
            scanf("%d", &x);
            int &y = R[x];
            if (y > low)	low = y;
            y = i;
            ret += i - low;
//			printf("[%d %d]\n", low + 1, i);
        }
        printf("%lld\n", ret);
    }
    return 0;
}
/*
9
3
1 2 1
5
1 2 3 1 2
4
1 2 2 1
*/