Billboard

通过这题,我知道了要活用线段树的思想,而不是拘泥于形式, 就比如这题 显然更新和查询放在一起很简单 但如果分开写 那么我觉得难度会大大增加

【题目链接】Billboard

【题目类型】区间求最大值的位置update的操作在query里做了

&题意：

h*w的木板,放进一些1*L的物品,求每次放空间能容纳且最上边的位子

&题解：

思路:每次找到最大值的位子,然后减去L

线段树功能:query

区间求最大值的位置(直接把update的操作在query里做了)

【时间复杂度】\(O(nlogn)\)

&代码：

#include <bits/stdc++.h>

using namespace std;

const int maxn = 200000 + 9 ;

int h,w,n;

int seg[maxn<<2];

inline void PushUp(int rt)

{

	seg[rt]=max(seg[rt<<1],seg[rt<<1|1]);

}

void Build(int b,int e,int rt)

{

	if (b==e){

		seg[rt]=w;

		return;

	}

	int m=b+e>>1;

	Build(b,m,rt<<1);

	Build(m+1,e,rt<<1|1);

	PushUp(rt);

}

//把更新和查询放在了一起

int Query(int xx,int b,int e,int rt)

{

	if (b==e){

		seg[rt]-=xx;

		return b;

	}

	int m=b+e>>1;

	int re=0;

	//这里保证了先从小的序号开始找

	if (seg[rt<<1]>=xx)

		re=Query(xx,b,m,rt<<1);

	else

		re=Query(xx,m+1,e,rt<<1|1);

	PushUp(rt);

	return re;

}

void Solve()

{

	while(~scanf("%d%d%d",&h,&w,&n)){

		h=min(h,n);

		Build(1,h,1);

		for(int i=0;i<n;i++){

			int t;

			scanf("%d",&t);

			if (seg[1]<t) puts("-1");

			else {

				printf("%d\n",Query(t,1,h,1));

			}

		}

	}

}

int main()

{

	Solve();

	return 0;

}