在刷hh神牛的线段树专辑，

弄得头晕脑胀，

2795 线段树更新用的是自底向上更新。

表示前面一直想不通10^9的高怎么处理，后来看到只有20W查询，于是就取两者的最小值，因为每个输入高度可以视为1，你高度再多，一张输入就只能占一个高度，用到的也就只有1了。

class node {
public:
	int value, l, r, h;
};

class BillBoard {
public:
	void build(int s, int e, int idx);
	void query(int x, int idx);
	void update(int pos, int x);
	void update(int pos, int ls, int rs);
	void hexie();

	int w, n, m;
private:
	int	res, pos, tot;
	node st[800010];
}test;

void BillBoard::build(int s, int e, int idx) {
	st[idx].l = s;
	st[idx].r = e;
	st[idx].value = 0;
	if ( s == e ) {
		st[idx].h = ++tot;
		return;
	}
	int mid = (s+e)>>1;
	build(s, mid, LEFT(idx));
	build(mid+1, e, RIGHT(idx));
}

void BillBoard::query(int x, int idx) {
	if ( st[idx].value+x > w ) {
		res = -1;
		return;
	}
	if ( st[idx].l == st[idx].r ) {
		res = st[idx].h;
		pos = idx;
		return;
	}
	if ( st[LEFT(idx)].value+x <= w ) query(x, LEFT(idx));
	if ( res == -1 ) query(x, RIGHT(idx));
}

void BillBoard::update(int pos, int x) {
	st[pos].value += x;
	int bro;
	if ( pos&1 ) bro = pos-1;
	else		 bro = pos+1;
	if ( pos == 1 ) return;
	update(pos>>1, pos, bro);
}

void BillBoard::update(int pos, int ls, int rs) {
	st[pos].value = min(st[ls].value, st[rs].value);
	int bro;
	if ( pos&1 ) bro = pos-1;
	else		 bro = pos+1;
	if ( pos == 1 ) return;
	update(pos>>1, pos, bro);
}

void BillBoard::hexie() {
	n = n < m ? n : m;
	build(1, n, 1);
	tot = 0;
	int x;
	while ( m-- ) {
		scanf("%d", &x);
		res = -1;
		query(x, 1);
		printf("%d\n", res);
		if ( res != -1 ) {
			update(pos, x);
		}
	}
}

int main() {
	while ( ~scanf("%d%d%d", &test.n, &test.w, &test.m) ) {
		test.hexie();
	}
	return 0;
}

hdoj 3303北大oj上也有这题，转载下线段树思路。

一道在线RMQ的应用，题目大意是：有个正整数集合S，初始为空，接下来有一连串的操作：
B X : 表示把整数X(1 <= X <= 500000)放到集合S中。
A Y : 问现在在集合S中的所有整数，模Y结果最小的整数是哪一个，如果集合S中有多个满足条件的整数，输出最后放到S中的那个，如果没有这样的整数，输出-1。

解法比较不常见，要分清况讨论，当Y比较小的时候，直接算：对每一个S中的元素取模，找最小值。当Y比较大的时候，用线段树：因为集合S中的元素都大于1，小于500000，可以把这些数分成这样的区间：
(1, 2, ..., Y-1) (Y, Y + 1, Y + 2, ..., 2Y - 1) (2Y, 2Y + 1, 2Y + 2, ..., 3Y - 1)......
这样每个区间的最小值就是这个区间中模Y最小的那个数，然后再把这些区间的最小值作为候选结果，用最直接的方法：依次对Y取模，找结果。就行了。

做的时候一般想不到分情况讨论，直接暴力poj超时，hdoj过了（杯具），直接线段树的话也会超时，因为思路是把500000按题目输入的除数来分区间，取每个区间的最小值对比，如此这般详见代码。

class SegTree {
public:
	int l, r, value, time;
};

class node{
public:
	void build(int s, int e, int idx);
	void query(int s, int e, int idx, int data);
	void update(int data, int idx, int time);
	void hexie();
private:
	SegTree st[4000005];
	int		res, time;
	int		a[1000500];
}test;

int n;

void node::build(int s, int e, int idx) {
	st[idx].l = s;
	st[idx].r = e;
	st[idx].value = -1;
	if ( s == e ) return;
	int mid = (s+e)>>1;
	build(s, mid, LEFT(idx));
	build(mid+1, e, RIGHT(idx));
}

void node::update(int data, int idx, int time) {
	if ( st[idx].l == st[idx].r ) {
		st[idx].value = data;
		st[idx].time = time;
		return;
	}
	if ( st[idx].value == -1 ) {
		st[idx].value = data;
		st[idx].time = time;
		st[LEFT(idx)].value = st[RIGHT(idx)].value = -1;
	} else if ( data < st[idx].value ) {
		st[idx].value = data;
		st[idx].time = time;
	}
	int mid = (st[idx].l + st[idx].r) >> 1;
	if ( data <= mid ) update(data, LEFT(idx), time);
	else update(data, RIGHT(idx), time);
}

void node::query(int s, int e, int idx, int data) {
	if ( st[idx].value == -1 ) return;
	if ( st[idx].l == s && st[idx].r == e ) {
		int temp = st[idx].value%data;
//		printf("%d:%d\n", data, temp);
		if ( res == -1 || res > temp || ( res == temp && time < st[idx].time ) ) {
			res = temp;
			time = st[idx].time;
		}
		return;
	}
	int mid = (st[idx].l + st[idx].r) >> 1;
	if ( e <= mid ) query(s, e, LEFT(idx), data);
	else if ( s > mid ) query(s, e, RIGHT(idx), data);
	else {
		query(s, mid, LEFT(idx), data);
		query(mid+1, e, RIGHT(idx), data);
	}
}

void node::hexie() {
	char	c[5];
	int		i, j, k, tnum;
	st[1].value = -1;
	tnum = 0;
	FF (i, n) {
		scanf("%s%d", c, &k);
		if ( c[0] == 'B' ) {
			a[tnum++] = k;
			update(k, 1, tnum);
		} else if ( k < 5001 ) { //除数小的时候直接暴力
			res = 1000000;
			time = -1;
			FFD(j, tnum) {
				int temp = a[j] % k;
				if ( temp < res ) {
					res = temp;
					time = j+1;
				} 
				if ( res == 0 ) break;
			}
			printf("%d\n", time);
		} else { //这里开始分区间
			res = -1;
			time = -1;
			int a = k;
			int b = k+k-1;
			//特殊情况没有0，因为线段树构造是从1开始的
			query(1, k-1, 1, k);
			while ( a < 500000 ) {
				if ( b > 500000 ) b = 500000;
				query(a, b, 1, k);
				a += k;
				b += k;
			}
			printf("%d\n", time);
		}
	}
}

int main() {
//	freopen("in.txt","r",stdin);
	int T = 0;
	test.build(1, 500000, 1);
	while ( ~scanf("%d%*c", &n) && n ) {
		if ( T++ ) putchar('\n');
		printf("Case %d:\n", T);
		test.hexie();
	}
	return 0;
}