Data Structure?
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 2133 Accepted Submission(s): 682
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
单点更新，
找到该点，路径上个区间的len--；
/*
2013-8-19 15:13:47
Time: 562MS Memory: 6392K
Author: zyh
*/
#define N 262200
#include<stdio.h>
struct IntervalTree{
int L,R,len;
}tree[N*4];
__int64 sum; //这里又错了一次，，注意要64位
void build(int p,int l,int r){
tree[p].L = l;
tree[p].R = r;
tree[p].len = r-l+1;
if(l==r) return;
int mid = (l+r)>>1;
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
}
void change(int p,int cnt){
tree[p].len--;
if(tree[p].L==tree[p].R) {
sum+=tree[p].L;
return ;
}
if(cnt <= tree[p<<1].len){
change(p<<1,cnt);
}
else if(cnt>tree[p<<1].len){
change(p<<1|1,cnt-tree[p<<1].len);
}
}
int main()
{
int t,n,k,i,tmp,j;
scanf("%d\n",&t);
for(j=1;j<=t;j++)
{
scanf("%d%d",&n,&k);
build(1,1,n);
sum=0;
for(i=0;i<k;i++){
scanf("%d",&tmp);
change(1,tmp);
}
printf("Case %d: %I64d\n",j,sum);
}
return 0;
}