hdu 1754 I Hate It

今天听斌哥讲课，果然V5，讲的是竞赛用堆，从基本到扩展，自顶向下和自底向上，递归与非递归……基本是听懂了，刷了两题，把顶和底都敲了一遍，都A了。本来打算把课后练习刷完的，无奈还不习惯高强度训练，做了两题以后感觉脑力枯竭了，怎么也做不下去了，唉。

hdu 1754

 1 #include <stdio.h>
 2 #include <string.h>
 3 const int MAXD = 200005;
 4 int tree[4*MAXD];
 5 int D;
 6 int max(int a,int b)
 7 {
 8     return a>b ?a :b;
 9 }
10 void update(int n)
11 {
12     for(; n^1; n>>=1)
13         tree[n>>1] = max(tree[n],tree[n^1]);
14 }
15 void query(int cur,int s,int t,int x,int y,int &ans)
16 {
17     int mid = (s+t)>>1;
18     if(s>=x && t<=y)
19     {
20         ans = max(tree[cur],ans);
21         return ;
22     }
23     if(x <= mid) query(cur<<1,s,mid,x,y,ans);
24     if(y >= mid+1) query(cur<<1|1,mid+1,t,x,y,ans);
25 }
26 int main()
27 {
28     int m,n,i,ans,x,y;
29     char t;
30     while(~scanf("%d%d",&n,&m)){
31     memset(tree,0,sizeof(tree));
32     for(D = 1; D < n+2; D <<= 1);
33     for(i = 1; i <= n; i++)
34         scanf("%d",&tree[D+i]);
35     for(i = D-1; i; i--)
36         tree[i] = max(tree[i<<1],tree[i<<1^1]);
37     while(m--)
38     {
39         getchar();
40         scanf("%c%d%d",&t,&x,&y);
41         if(t=='Q')
42         {
43             ans = 0;
44             query(1,0,D-1,x,y,ans);
45             printf("%d\n",ans);
46         }
47         else
48         {
49             tree[D+x] = y;
50             update(D+x);
51         }
52     }
53     }
54     return 0;
55 }