hdu4217 Data Structure?

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.

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

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

这题是简单的插空问题，只要维护每条线段还剩多少空就行，坑点是要用__int64，wa了两次。。

#include<iostream>

#include<stdio.h>

#include<string.h>

#include<math.h>

#include<vector>

#include<map>

#include<queue>

#include<stack>

#include<string>

#include<algorithm>

using namespace std;

__int64 sum;

struct node{

	int l,r,num;

}b[8*300000];

void build(int l,int r,int i)

{

	int mid;

	b[i].l=l;b[i].r=r;b[i].num=r-l+1;

	if(l==r)return;

	mid=(l+r)/2;

	build(l,mid,i*2);

	build(mid+1,r,i*2+1);

}

void question(int index,int i)

{

	int mid;

	if(b[i].l==b[i].r){

		sum+=b[i].l;

		b[i].num=0;return;

	}

	if(b[i*2].num>=index)question(index,i*2);

	else question(index-b[i*2].num,i*2+1);

	b[i].num=b[i*2].num+b[i*2+1].num;

}

int main()

{

	int n,m,i,j,T,num1=0,c;

	scanf("%d",&T);

	while(T--)

	{

		num1++;

		//printf("\n",num1);

		scanf("%d%d",&n,&m);

		build(1,n,1);

		sum=0;

		for(i=1;i<=m;i++){

			scanf("%d",&c);

			question(c,1);

		}

		printf("Case %d: %I64d\n",num1,sum);

	}

	return 0;

}

巴特西

hdu4217 Data Structure?

最新文章

热门文章