本题注意的是虽然长和宽的范围很广,数组开不下,但是需要注意的是n的值却很只有20000个,对于H>N的情况区间只需要1——N,因为最多能有N个,但是对于N>H的情况,当然,区间就最大只能开1-N,因为板只有那么大,区间开的就是为它们两者之间最小的那一个。
#include<cstdio> #include<cstdlib> #include<cmath> #include<cstring> #define MAXN 200002 void build_tree(int l,int r,int id); void push_up_tree(int id); void update_tree(int value,int *x,int l,int r,int id); int m_max(int a,int b); int seg_tree[MAXN<<2]; int h,w,n; int main() { int temp,value,x; while(scanf("%d%d%d",&h,&w,&n)==3) { h=(h>=n?n:h); build_tree(1,h,1); while(n--) { scanf("%d",&value); if(value>seg_tree[1]) { printf("-1\n"); } else { update_tree(value,&x,1,h,1); printf("%d\n",x); } } } } void build_tree(int l,int r,int id) { if(l==r) { seg_tree[id]=w; return ; } int m=(l+r)>>1; build_tree(l,m,id<<1); build_tree(m+1,r,id<<1|1); push_up_tree(id); } void push_up_tree(int id) { seg_tree[id]=m_max(seg_tree[id<<1],seg_tree[id<<1|1]); } int m_max(int a,int b) { return a>=b?a:b; } void update_tree(int value,int *x,int l,int r,int id) { if(l==r) { *x=l; seg_tree[id]-=value; return ; } int m=(l+r)>>1; if(seg_tree[id<<1]>=value) update_tree(value,x,l,m,id<<1); else update_tree(value,x,m+1,r,id<<1|1); push_up_tree(id); }