HDU 4217

클릭 하여 제목 링크 열기
문제 형 은 바로 데이터 구조 다.한 배열 에 주 고 또 k 번 작업 합 니 다. 매번 작업 할 때마다 하나의 키 를 지정 하고 배열 에서 작은 키 의 수 를 삭제 합 니 다. k 번 작업 후에 삭 제 된 모든 숫자의 합 을 요구 합 니 다.　
간단 한 사고방식 은 이 숫자 가 삭제 되 지 않 았 음 을 1 로 표시 하고 0 은 삭제 되 었 음 을 나타 낸다. 키 의 작은 숫자 를 찾 으 려 면 표기 그룹의 첫 번 째 접두사 와 키 의 아래 표 시 를 찾 아야 한다. 또한 표기 하 는 그룹의 접두사 와 줄 지 않 는 수열 을 찾 아야 하기 때문에 2 점 으로 가속 할 수 있다.여기 서 주의해 야 할 것 은 삭 제 된 수 는 두 번 째 또는 여러 번 찾 을 수 없습니다. 즉, 각 수 는 최대 한 번 찾 을 수 있 습 니 다. 이 수 는 삭 제 된 것 이 고 이 수 는 아래 표 의 접두사 와 ki 가 있 으 면 더 작은 아래 표 가 존재 하기 때문에 접두사 와 도 ki 가 있 습 니 다. 우리 가 찾 아야 할 것 은 접두사 와 ki 의 아래 표 가 처음 나타 나 는 것 입 니 다.I64 를 더 사용 해 야 합 니 다.
코드 첨부:

 1 /*************************************************************************

 2     > File Name: 4217.cpp

 3     > Author: Stomach_ache

 4     > Mail: [email protected]

 5     > Created Time: 2014 04 26      21 51 19 

 6     > Propose: HDU 4217  

 7  ************************************************************************/

 8 //BIT + BinarySearch　   　O(k * logn * logn)

 9 //    ，    ,  １         ，０         

10 #include <cmath>

11 #include <string>

12 #include <vector>

13 #include <cstdio>

14 #include <fstream>

15 #include <cstring>

16 #include <iostream>

17 #include <algorithm>

18 using namespace std;

19 

20 #define X first

21 #define Y second

22 #define MAX_N (262144 + 5)

23 typedef long long LL;

24 typedef pair<int, int> pii;

25 int n, k;

26 int c[MAX_N];

27 

28 int

29 lowbit(int x) {

30         return x & (-x);

31 }

32 

33 LL

34 get_sum(int x) {

35         LL s = 0;

36         while (x > 0) {

37                 s += c[x];

38                 x -= lowbit(x);

39         }

40 

41         return s;

42 }

43 

44 void 

45 update(int x, int v) {

46         while (x <= n) {

47                 c[x] += v;

48                 x += lowbit(x);

49         }

50 

51         return ;

52 }

53 

54 int

55 main(void) {

56         int T, cnt = 1;

57         scanf("%d", &T);

58         while (T--) {

59                 scanf("%d %d", &n, &k);

60                 memset(c, 0, sizeof(c));

61                 for (int i = 1; i <= n; i++) {

62                         update(i, 1);

63                 }

64                 LL ans = 0;

65                 for (int i = 0; i < k; i++) {

66                         int ki;

67                         scanf("%d", &ki);

68                         //         ki    ，    ki   

69                         //       ，                ki    

70                         int L = ki, R = n, tmp = L;

71                         while (L <= R) {

72                                 int mid = L + (R - L) / 2;

73                                 int s = get_sum(mid);

74                                 if (s < ki) {

75                                         L = mid + 1;

76                                 } else {

77                                         if (s == ki) {

78                                                 tmp = mid;

79                                         }

80                                         R = mid;

81                                 }

82                                 if (tmp == L && tmp == R) {

83                                         break;

84                                 }

85                         }

86                         ans += tmp;

87                         update(tmp, -1);

88                 }

89                 printf("Case %d: %I64d
", cnt++, ans);

90         }

91 

92         return 0;

93 }