hdu2795（线段树单点更新）

题目链接：hdu2795

/*线段树单点更新
题目大意：有一块板子，长宽分别为W，H，然后有n块1*w海报
让你把这n快海报贴在这块板子上，尽量往板子的上方贴,同一行尽量往板子的左边贴。
对于第i块海报如果能够贴下则输出能贴在第几行，否则输出-1。

思路：利用线段树求区间的最大值;
maxx表示区间内能贴的海报的最大宽度
建树的时候要注意，heigh的范围特别大
当heigh>=m(m是海报的数量)，要用m来建树
*/
#include
  
   
#include
   
     using namespace std; #define N 200005 int n,flag,heigh,wide,num; struct node { int left,right; int maxx; }s[N<<2]; void build(int left, int right, int n) { s[n].left = left; s[n].right = right; s[n].maxx = wide; if(left == right) return ; int mid = (left + right) >> 1; build(left, mid, n<<1); build(mid+1, right, n<<1|1); } void update(int id, int n) { if(s[n].left == id && s[n].right == id) { s[n].maxx -= num; return ; } int mid = (s[n].left + s[n].right) >> 1; if(id <= mid) update(id, n<<1); else if(id > mid) update(id, n<<1|1); s[n].maxx = max(s[n<<1].maxx, s[n<<1|1].maxx); } int query(int left, int right, int n) { if(s[n].maxx < num) return -1; if(s[n].left == s[n].right) return left; int mid = (s[n].left + s[n].right) >> 1; if(s[n<<1].maxx >= num)//先向左子树中查询 return query(left, mid, n<<1); else return query(mid+1, right, n<<1|1); } int main() { int i,m; while(~scanf("%d%d%d",&heigh,&wide,&m)) { m>=heigh   build(1,heigh,1):build(1,m,1);//建树时要注意 while(m--) { scanf("%d",&num); int ans = query(1,heigh,1); if(ans == -1) printf("-1\n"); else { printf("%d\n",ans); update(ans,1); } } } return 0; }