题意：一块宽w高h的板，有n张纸条，线条高度为1，第i张纸条的宽度为wi，将这n张纸条按顺序从上到下，从左到右贴在那块板上，输出各纸条贴在了第几行，无法贴的输出-1。 (1 <= h,w <= 10^9; 1 <= n <= 200,000)
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2795
——>>线段树过，将块的高度作为线段树区间，维护各结点对应的最大容纳量就好。开始建树时我直接来了个build(1, 1, h)，结果是RE，我想数组没开小，又不用指针，怎么会是RE？于是换了建树方法，直接把4*maxn个结点全部赋为w，结果还是RE，我想会不会是太大了，于是来个二分测试，submit了几十次，测出了给前400021个结点赋w时，返回的都是WA，给400022以上个结点赋w时，返回的都是RE，my god!这怎么过？再看一下别人的代码，发现有个if(h > n) h = n;东东，顿悟了！h <= 10^9，如果测试数据中来个h = 10^9，查询线段树query(1, 1, h)是一定RE的！！！如果板的高度h大于纸条的张数n，即使n张纸条全部贴下，最多就占n行，即使此时h = 10^9，如果板的高度h小于等于纸条的张数n，线段树区间的右端只能是h。所以不能直接用h或者n来做线段树的右端，应选h，但当if(h > n) h = n。
#include <cstdio>
#include <algorithm>using namespace std;const int maxn = 200000 + 10;
int maxv[maxn<<2], w, wi;int query(int o, int L, int R) //查询&更新
{if(maxv[o] < wi) return -1; //不满足if(L == R && maxv[o] >= wi) //叶子结点满足时，更新返回{maxv[o] -= wi;return L;}int M = L + (R - L) / 2, ans;if(maxv[2*o] >= wi) ans = query(2*o, L, M); //先左后右else ans = query(2*o+1, M+1, R);maxv[o] = max(maxv[2*o], maxv[2*o+1]); //更新return ans;
}
void build(int o, int L, int R) //建树
{if(L == R){maxv[o] = w;return;}int M = L + (R - L) / 2;build(2*o, L, M);build(2*o+1, M+1, R);maxv[o] = w;
}
int main()
{int h, n, i;while(~scanf("%d%d%d", &h, &w, &n)){if(h > n) h = n; //这句千万别少！！！直接用h来建树RE，直接用n建树WAbuild(1, 1, h);for(i = 1; i <= n; i++){scanf("%d", &wi);printf("%d\n", query(1, 1, h));}}return 0;
}