hdu 2795 线段树（纵向）

注意h的范围和n的范围,纵向建立线段树

题意:h*w的木板,放进一些1*L的物品,求每次放空间能容纳且最上边的位子
思路:每次找到最大值的位子,然后减去L
线段树功能:query:区间求最大值的位子(直接把update的操作在query里做了)
3 5 5
2
4
3
3
3

1
2
1
3
-1

2015-05-15

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<algorithm>
 4 #include<cstring>
 5 #include<cmath>
 6 #include<queue>
 7 #include<map>
 8 using namespace std;
 9 #define MOD 1000000007
10 const int INF=0x3f3f3f3f;
11 const double eps=1e-5;
12 #define cl(a) memset(a,0,sizeof(a))
13 #define ts printf("*****
");
14 #define lson l,mid,rt<<1
15 #define rson mid+1,r,rt<<1|1
16 #define root 1,n,1
17 #define mid ((l+r)>>1)
18 const int MAXN=200050;
19 int n,m,t;
20 int num[MAXN],w,h;
21 struct Node
22 {
23     int l,r;
24     int sum;
25 }node[MAXN<<2];
26 void build(int l,int r,int rt)
27 {
28     node[rt].l=l;
29     node[rt].r=r;
30     node[rt].sum=w;
31     if(l==r)    return;
32     build(lson);
33     build(rson);
34 }
35 int query(int val,int rt)
36 {
37     if(node[rt].l==node[rt].r)
38     {
39         node[rt].sum-=val;
40         return node[rt].l;
41     }
42     int ret=0;
43     if(node[rt<<1].sum>=val)  ret=query(val,rt<<1);
44     else    ret=query(val,rt<<1|1);
45     node[rt].sum=max(node[rt<<1|1].sum,node[rt<<1].sum);
46     return ret;
47 }
48 int main()
49 {
50     int i,j,k,tt;
51     #ifndef ONLINE_JUDGE
52     freopen("1.in","r",stdin);
53     #endif
54     while(~scanf("%d%d%d",&h,&w,&n))
55     {
56         if(h>n) h=n;
57         int a;
58         build(1,h,1);
59         for(i=1;i<=n;i++)
60         {
61             scanf("%d",&a);
62             if(node[1].sum<a)   printf("-1
");
63             else printf("%d
",query(a,1));
64         }
65     }
66 }

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<algorithm>
 4 #include<cstring>
 5 #include<cmath>
 6 #include<queue>
 7 #define lson l,m,rt<<1
 8 #define rson m+1,r,rt<<1|1
 9 using namespace std;
10 const int maxn=222225;
11 int sum[maxn<<2];
12 int n,m,t,h,w;
13 void pushup(int rt)
14 {
15     sum[rt]=max(sum[rt<<1],sum[rt<<1|1]);
16 }
17 void build(int l,int r,int rt)
18 {
19     sum[rt]=w;
20     if(l==r)    return;
21     int m=(l+r)>>1;
22     build(lson);
23     build(rson);
24 }
25 int query(int add,int l,int r,int rt)
26 {
27     if(l==r)
28     {
29         sum[rt]-=add;
30         return l;
31     }
32     int m=(l+r)>>1;
33     int ret;
34     if(sum[rt<<1]>=add)
35     {
36         ret=query(add,lson);
37     }
38     else ret=query(add,rson);
39     pushup(rt);
40     return ret;
41 }
42 int main()
43 {
44     int i,j,k;
45     //freopen("1.in","r",stdin);
46     while(scanf("%d%d%d",&h,&w,&n)!=EOF)
47     {
48         if(h>n) h=n;
49         build(1,h,1);
50         for(i=1;i<=n;i++)
51         {
52             scanf("%d",&k);
53             if(sum[1]<k)    printf("-1
");
54             else printf("%d
",query(k,1,h,1));
55         }
56     }
57     return 0;
58 }