学步园

线段树模板题

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define N 263000
struct tree
{
	int left,right,count;
}p[N*3];
void build(int l,int r,int num)
{
	int mid=(l+r)/2;
	p[num].left=l;
	p[num].right=r;
	if(l==r)
	{
		p[num].count=1;return;
	}
	build(l,mid,num*2);
	build(mid+1,r,num*2+1);
	p[num].count=p[num*2].count+p[num*2+1].count;
}
int find(int i,int num)
{
	int sum;
	if(p[i].left==p[i].right)
	{
		p[i].count=0;return p[i].left;
	}
	if(num<=p[2*i].count)
		sum=find(i*2,num);
	else sum=find(i*2+1,num-p[i*2].count);
	p[i].count=p[i*2].count+p[i*2+1].count;
	return sum;
}
int main()
{
	int i,n,k,t,a,op=1;
	__int64 sum;
	scanf("%d",&t);
	while(t--)
	{
		sum=0;
		scanf("%d%d",&n,&a);
		build(1,n,1);
		while(a--)
		{
			scanf("%d",&k);
			sum+=find(1,k);
		}
		printf("Case %d: ",op++);
		printf("%I64d\n",sum);
	}
	return 0;
}