HUD2795 線段樹（單點更新）

? ? ?題目中給出的h和w范圍均大，其實n的最大范圍才200000，所以我們建立的線段樹大小為min(h,n),線段樹的每一個節點包含一個變量c，記錄當前區間內還剩下的可以put on的最大長度。插入一個數時，如果該數大于該區間最大值，則返回-1，說明put on不了。否則將它插入到頁節點，并返回插入的下標，接著一定不要忘記更新父節點的c值。

#define _CRT_SECURE_NO_DEPRECATE
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN = 200001;
struct Tnode{int e, b;int c;
};
int h, w, n,ans;;
Tnode tree[4 * MAXN];
void Create(int v, int b, int e){tree[v].b = b;tree[v].e = e;tree[v].c = w;if (e > b){int mid = (b + e) >> 1;Create(2 * v + 1, b, mid);Create(2 * v + 2, mid + 1, e);}
}
void Insert(int v,int x){if (x > tree[v].c){ans = -1;return;}if (tree[v].b==tree[v].e){tree[v].c -= x;ans = tree[v].b;return;}if (x <= tree[2 * v + 1].c)Insert(2 * v + 1, x);elseInsert(2 * v + 2, x);tree[v].c = max(tree[2 * v + 1].c, tree[2 * v + 2].c);
}
int main(){int x;while (~scanf("%d%d%d", &h, &w, &n)){int len = min(h, n);Create(0, 1, len);for (int i = 0; i < n; i++){scanf("%d",&x);Insert(0, x);printf("%d\n", ans);}}return 0;
}

　　

?