学步园

这个说是线段树入门....我其实还是开始的时候没有摸到头脑的.....

开始的想法是用普通方法做的,但是,自己忽略了20W*20W  400亿肯定会超时的....

用其线段树就舒服多了.

线段树不说可以省内存,但是他的有点就是可以优化询问....我把上一次的询问直接给你更新上去,你下次再问,我直接就给你个爽点的答案,这多爽!

贴出线段树的代码:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>

struct Node{
	int a;
	int b;
	int max;
}tree[888888];
int height,row,N;

int min(int a,int b)
{
	return a>=b?b:a;
}

int max(int a,int b)
{
	return a>=b?a:b;
}

void pushup(int i)
{
	tree[i].max=max(tree[i<<1].max,tree[i<<1|1].max);
}

void Buildtree(int i,int a,int b)
{
	tree[i].a=a;
	tree[i].b=b;
	tree[i].max=row;
	if(a==b)
	{
		return;
	}
	int mid=(a+b)>>1;
	Buildtree(i<<1,a,mid);
	Buildtree(i<<1|1,mid+1,b);
}

int query(int q,int i)
{
	if(tree[i].a==tree[i].b)
	{
		tree[i].max-=q;
		return tree[i].a;
	}
	int mid=(tree[i].a+tree[i].b)>>1;
	int ans=tree[i<<1].max>=q?query(q,i<<1):query(q,i<<1|1);
	pushup(i);
	return ans;
}


int main()
{
	while(scanf("%d%d%d",&height,&row,&N)!=EOF)
	{
		int n=min(height,N);
		Buildtree(1,1,n);
		for(int i=1;i<=N;i++)
		{
			int q;
			scanf("%d",&q);
			if(q>tree[1].max)
				printf("-1\n");
			else
				printf("%d\n",query(q,1));
		}
	}
	return 0;
}