Problem Description
Data structure is one of the basic skills for Computer Science students, which is a particular way of storing and organizing data in a computer so that it can be used efficiently. Today let me introduce a data-structure-like problem for you.
Original, there are N numbers, namely 1, 2, 3...N. Each round, iSea find out the Ki-th smallest number and take it away, your task is reporting him the total sum of the numbers he has taken away.
Original, there are N numbers, namely 1, 2, 3...N. Each round, iSea find out the Ki-th smallest number and take it away, your task is reporting him the total sum of the numbers he has taken away.
Input
The first line contains a single integer T, indicating the number of test cases.
Each test case includes two integers N, K, K indicates the round numbers. Then a line with K numbers following, indicating in i (1-based) round, iSea take away the Ki-th smallest away.
Technical Specification
1. 1 <= T <= 128
2. 1 <= K <= N <= 262 144
3. 1 <= Ki <= N - i + 1
Each test case includes two integers N, K, K indicates the round numbers. Then a line with K numbers following, indicating in i (1-based) round, iSea take away the Ki-th smallest away.
Technical Specification
1. 1 <= T <= 128
2. 1 <= K <= N <= 262 144
3. 1 <= Ki <= N - i + 1
Output
For each test case, output the case number first, then the sum.
Sample Input
2 3 2 1 1 10 3 3 9 1
Sample Output
Case 1: 3 Case 2: 14
题意：n个数1-n，k次操作，每次取出第ki小的数。问所有取出数字之和。
思路：树状数组。开始所有位置都是1，如果有数字被去掉就-1。然后在查找第ki小的数字的时候，利用树状数组去进行求和，看数字个数为k时是第几个。
代码：
#include <stdio.h>
#include <string.h>
#include <iostream>
using namespace std;
const int N = 277777;
int t, n, m, bit[N], num, i;
long long ans;
void add(int x, int v) {
while (x <= n) {
bit[x] += v;
x += (x&(-x));
}
}
int Sum(int k) {
int num = 0;
int x = 0;
for (int i = 18; i >= 0; i--) {
if (x + (1<<i) <= n && bit[x + (1<<i)] + num < k) {
x += (1<<i);
num += bit[x];
}
}
return x + 1;
}
void init() {
ans = 0;
memset(bit, 0, sizeof(bit));
scanf("%d%d", &n, &m);
for (i = 1; i <= n; i++)
add(i, 1);
for (i = 0; i < m; i++) {
scanf("%d", &num);
int s = Sum(num);
ans += s;
add(s, -1);
}
}
int main() {
int cas = 0;
scanf("%d", &t);
while (t--) {
init();
//printf("Case %d: %lld\n", ++cas, ans);
cout <<"Case "<<++cas<<": "<<ans<<endl;
}
return 0;
}