題目鏈接：[點擊打開鏈接](http://acm.hdu.edu.cn/showproblem.php?pid=2795) 題意： 原始序列全為w， 找到最左邊的>=a的位置， 將該位置的值減去a，答案為該位置， 如果找不到符合要求的位置， 輸出-1。 該題利用線段樹遞歸特點來求其最左邊的大于等于a的位置。 線段樹遞歸的特點是從祖先結點開始自頂向下遞歸，訪問各個元素的順序一定是從左到右， 并且在遞歸之后可以順便維護區間結點的值。 利用這個特點， 我們可以直接查詢到>=a的最左邊的位置。該元素變成v - a， ?然后順便維護改變了的值。 所以該題就成了維護區間最大值的線段樹題目。 細節參見代碼： ~~~ #include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #include<string> #include<vector> #include<stack> #include<bitset> #include<cstdlib> #include<cmath> #include<set> #include<list> #include<deque> #include<map> #include<queue> #define Max(a,b) ((a)>(b)?(a):(b)) #define Min(a,b) ((a)<(b)?(a):(b)) using namespace std; typedef long long ll; const double PI = acos(-1.0); const double eps = 1e-6; const int INF = 1000000000; const int maxn = 200010; int T,n,w,h,a,m,maxv[maxn*4]; void push_up(int o) { maxv[o] = max(maxv[o<<1], maxv[o<<1|1]); } void build(int l, int r, int o) { int m = (l + r) >> 1; maxv[o] = w; if(l == r) return ; build(l, m, o<<1); build(m+1, r, o<<1|1); push_up(o); } int query(int v, int l, int r, int o) { int m = (l + r) >> 1, ans = 0; if(l == r) { maxv[o] -= v; return l; } if(maxv[o<<1] >= v) ans = query(v, l, m, o<<1); else ans = query(v, m+1, r, o<<1|1); push_up(o); return ans; } int main() { while(~scanf("%d%d%d",&h,&w,&n)) { if(h > n) h = n; build(1, h, 1); for(int i=0;i<n;i++) { scanf("%d",&a); if(maxv[1] < a) printf("-1\n"); else printf("%d\n",query(a, 1, h, 1)); } } return 0; } ~~~