hdu 2795区間の最も値の位置を探します

問題がよくわかる
updateとqueryがマージされた2つのセグメントツリーが参照されているだけを書きました.そして分かれて最初に書いた
木の配列を書こうと思っていたのですが、区間最値の更新位置がどうなるか、いきなりゆっくりしてしまいます.牛が教えてくれることを願っています.
 

#include <cstdio>
#include <algorithm>
using namespace std;
 
#define lson l , m , rt << 1
#define rson m + 1 , r , rt << 1 | 1
const int maxn = 222222;
int h , w , n;
int MAX[maxn<<2];
void PushUP(int rt) {
	MAX[rt] = max(MAX[rt<<1] , MAX[rt<<1|1]);
}
void build(int l,int r,int rt) {
	MAX[rt] = w;
	if (l == r) return ;
	int m = (l + r) >> 1;
	build(lson);
	build(rson);
}

void update(int x,int l,int r,int rt) {
	if (l == r) {
		MAX[rt] -= x;
		return ;
	}
	int m = (l + r) >> 1;
	(MAX[rt<<1] >= x) ? update(x , lson) : update(x , rson);
	PushUP(rt);
}

int query(int x,int l,int r,int rt) {
	if (l == r) {
	//	MAX[rt] -= x;
		return l;//RETURN L
	}
	int m = (l + r) >> 1;
	// （ ） X  （ ）   
	int ret = (MAX[rt<<1] >= x) ? query(x , lson) : query(x , rson);
	//PushUP(rt);
	return ret;
}
int main() {
	while (~scanf("%d%d%d",&h,&w,&n)) 
	{
		if (h > n) h = n;
		build(1 , h , 1);
		// ， W 
		while (n --) 
		{
			int x;
			scanf("%d",&x);
			if (MAX[1] < x) puts("-1");
			else 
			{
				
				printf("%d
",query(x , 1 , h , 1));
				// updat query  
				update(x,1,h,1);
			}
		}
	}
	return 0;
}

合併の参考のネット上の

#include <cstdio>
#include <algorithm>
using namespace std;
 
#define lson l , m , rt << 1
#define rson m + 1 , r , rt << 1 | 1
const int maxn = 222222;
int h , w , n;
int MAX[maxn<<2];
void PushUP(int rt) {
	MAX[rt] = max(MAX[rt<<1] , MAX[rt<<1|1]);
}
void build(int l,int r,int rt) {
	MAX[rt] = w;
	if (l == r) return ;
	int m = (l + r) >> 1;
	build(lson);
	build(rson);
}
int query(int x,int l,int r,int rt) {
	if (l == r) {
		// w  
		MAX[rt] -= x;
		// ， L  
		return l;
	}
	int m = (l + r) >> 1;
	//query update ，  
	int ret = (MAX[rt<<1] >= x) ? query(x , lson) : query(x , rson);
	PushUP(rt);
	return ret;
}
int main() {
	while (~scanf("%d%d%d",&h,&w,&n)) {
		if (h > n) h = n;
		build(1 , h , 1);
		while (n --) {
			int x;
			scanf("%d",&x);
			if (MAX[1] < x) puts("-1");
			else printf("%d
",query(x , 1 , h , 1));
		}
	}
	return 0;
}