2015
05-23

# Data Structure?

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.

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

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

2
3 2
1 1
10 3
3 9 1

Case 1: 3
Case 2: 14

http://acm.hdu.edu.cn/showproblem.php?pid=4217

//线段树
#include <stdio.h>

#define MAX 262145

int tmp;

typedef struct _tree
{
int left;
int right;
int count;
}tree;

tree t[MAX*3];

void build_tree(int c, int left, int right)
{
int mid;
t[c].left = left;
t[c].right = right;
t[c].count = right - left + 1;
if(left == right)return ;
mid = (left + right)>>1;
build_tree(2*c, left, mid);
build_tree(2*c+1, mid+1, right);
}

void del(int c, int ki)
{
if(t[c].left == t[c].right){
tmp = t[c].right;
t[c].count --;
return;
}
if(ki <= t[2*c].count){	//if the left tree'count is less than ki then the ki-th min number must be at the left tree
del(2*c, ki);
}
else {	//else it is at the right tree
del(2*c+1, ki - t[2*c].count);
}
t[c].count --;
}

int main()
{
int t, n, k, cas, ki;
__int64 res;
scanf("%d", &t);
for(cas = 1; cas <= t; cas ++){
scanf("%d%d", &n, &k);
build_tree(1, 1, n);
res = 0;
while(k --){
scanf("%d", &ki);
del(1, ki);
res += tmp;
}
printf("Case %d: %I64d\n", cas, res);
}
return 0;
}