专题训练之线段树

单点更新模板（以区间求和为例）

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 #define lson l,m,rt*2
 6 #define rson m+1,r,rt*2+1 
 7 #define root 1,n,1
 8 const int maxn=100000; //题目所给最大区间
 9 struct node{
10     int sum; //记录附加信息 
11 }arr[maxn*4]; //节点长度开最大区间的四倍
12 
13 void pushup(int rt)
14 {
15     arr[rt].sum=arr[rt*2].sum+arr[rt*2+1].sum;
16 }
17 
18 void build(int l,int r,int rt)
19 {
20     if ( l==r ) {
21         scanf("%d",&arr[rt].sum);
22         return;
23     }
24     int m=(l+r)/2;
25     build(lson);
26     build(rson);
27     pushup(rt);
28 }
29 
30 void update(int p,int add,int l,int r,int rt)
31 {
32     if ( l==r ) {
33         arr[rt].sum+=add;
34         return;
35     }
36     int m=(l+r)/2;
37     if ( p<=m ) update(p,add,lson);
38     else update(p,add,rson);
39     pushup(rt);
40 } 
41 
42 int query(int L,int R,int l,int r,int rt)
43 {
44     if ( L<=l && r<=R ) return arr[rt].sum;
45     int m=(l+r)/2;
46     int ret=0;
47     if ( L<=m ) ret+=query(L,R,lson);  //注意不是左右区间不是if和else的关系，而是并列的关系（拆分区间） 
48     if ( R>m ) ret+=query(L,R,rson);
49     return ret;
50 } 
51 
52 int main()
53 {
54     int n;
55     while ( scanf("%d",&n)!=EOF ) {
56         build(root);
57         //操作 
58     }
59     return 0;
60 }

单点更新

成段更新模板（以区间求和为例）

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 #define lson l,m,rt*2
 6 #define rson m+1,r,rt*2+1
 7 #define root 1,n,1
 8 typedef long long ll;
 9 const int maxn=100005;
10 struct node{
11     ll sum;
12 }arr[maxn*4]; 
13 ll add[maxn*4]; //延迟标记 
14 
15 void pushup(int rt)
16 {
17     arr[rt].sum=arr[rt*2].sum+arr[rt*2+1].sum;
18 }
19 
20 void pushdown(int rt,int m)
21 {
22     if ( add[rt] ) {
23         add[rt*2]+=add[rt];
24         add[rt*2+1]+=add[rt];
25         arr[rt*2].sum+=add[rt]*(m-m/2);
26         arr[rt*2+1].sum+=add[rt]*(m/2);
27         add[rt]=0;
28     }
29 }
30 
31 void build(int l,int r,int rt)
32 {
33     add[rt]=0;
34     if ( l==r ) {
35         scanf("%lld",&arr[rt].sum);
36         return;
37     }
38     int m=(l+r)/2;
39     build(lson);
40     build(rson);
41     pushup(rt);
42 }
43 
44 void update(int L,int R,int c,int l,int r,int rt)
45 {
46     if ( L<=l && r<=R ) {
47         add[rt]+=c;
48         arr[rt].sum+=(ll)c*(r-l+1);
49         return;
50     }
51     pushdown(rt,r-l+1);
52     int m=(l+r)/2;
53     if ( L<=m ) update(L,R,c,lson);
54     if ( m<R ) update(L,R,c,rson);
55     pushup(rt);
56 }
57 
58 ll query(int L,int R,int l,int r,int rt)
59 {
60     if ( L<=l && r<=R ) return arr[rt].sum;
61     pushdown(rt,r-l+1);
62     int m=(l+r)/2;
63     ll ret=0;
64     if ( L<=m ) ret+=query(L,R,lson);
65     if ( m<R ) ret+=query(L,R,rson);
66     return ret;
67 }

成段更新

练习题

区间最值和区间求和

1.（HDOJ1166）http://acm.hdu.edu.cn/showproblem.php?pid=1166

单点更新模板题

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 #define lson l,m,rt*2
 6 #define rson m+1,r,rt*2+1 
 7 #define root 1,n,1
 8 const int maxn=50005; //题目所给最大区间
 9 struct node{
10     int sum;
11 }arr[maxn*4]; //节点长度开最大区间的四倍
12 
13 void pushup(int rt)
14 {
15     arr[rt].sum=arr[rt*2].sum+arr[rt*2+1].sum;
16 }
17 
18 void build(int l,int r,int rt)
19 {
20     if ( l==r ) {
21         scanf("%d",&arr[rt].sum);
22         return;
23     }
24     int m=(l+r)/2;
25     build(lson);
26     build(rson);
27     pushup(rt);
28 }
29 
30 void update(int p,int add,int l,int r,int rt)
31 {
32     if ( l==r ) {
33         arr[rt].sum+=add;
34         return;
35     }
36     int m=(l+r)/2;
37     if ( p<=m ) update(p,add,lson);
38     else update(p,add,rson);
39     pushup(rt);
40 } 
41 
42 int query(int L,int R,int l,int r,int rt)
43 {
44     if ( L<=l && r<=R ) return arr[rt].sum;
45     int m=(l+r)/2;
46     int ret=0;
47     if ( L<=m ) ret+=query(L,R,lson);
48     if ( R>m ) ret+=query(L,R,rson);
49     return ret;
50 } 
51 
52 int main()
53 {
54     int n,T,i,j,k,ans,h,x,y;
55     char s[10];
56     scanf("%d",&T);
57     for ( h=1;h<=T;h++ ) {
58         scanf("%d",&n);
59         build(root);
60         printf("Case %d:
",h);
61         while ( scanf("%s",s) && s[0]!='E' ) {
62             scanf("%d%d",&x,&y);
63             if ( s[0]=='Q' ) {
64                 printf("%d
",query(x,y,root));
65             }
66             else if ( s[0]=='A' ) update(x,y,root);
67             else if ( s[0]=='S' ) update(x,-y,root);
68         }
69     }
70     return 0;
71 }

HDOJ1166

2.（POJ3468）http://poj.org/problem?id=3468

成段更新模板题

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 #define lson l,m,rt*2
 6 #define rson m+1,r,rt*2+1
 7 #define root 1,n,1
 8 typedef long long ll;
 9 const int maxn=100005;
10 struct node{
11     ll sum;
12 }arr[maxn*4]; 
13 ll add[maxn*4]; //延迟标记 
14 
15 void pushup(int rt)
16 {
17     arr[rt].sum=arr[rt*2].sum+arr[rt*2+1].sum;
18 }
19 
20 void pushdown(int rt,int m)
21 {
22     if ( add[rt] ) {
23         add[rt*2]+=add[rt];
24         add[rt*2+1]+=add[rt];
25         arr[rt*2].sum+=add[rt]*(m-m/2);
26         arr[rt*2+1].sum+=add[rt]*(m/2);
27         add[rt]=0;
28     }
29 }
30 
31 void build(int l,int r,int rt)
32 {
33     add[rt]=0;
34     if ( l==r ) {
35         scanf("%lld",&arr[rt].sum);
36         return;
37     }
38     int m=(l+r)/2;
39     build(lson);
40     build(rson);
41     pushup(rt);
42 }
43 
44 void update(int L,int R,int c,int l,int r,int rt)
45 {
46     if ( L<=l && r<=R ) {
47         add[rt]+=c;
48         arr[rt].sum+=(ll)c*(r-l+1);
49         return;
50     }
51     pushdown(rt,r-l+1);
52     int m=(l+r)/2;
53     if ( L<=m ) update(L,R,c,lson);
54     if ( m<R ) update(L,R,c,rson);
55     pushup(rt);
56 }
57 
58 ll query(int L,int R,int l,int r,int rt)
59 {
60     if ( L<=l && r<=R ) return arr[rt].sum;
61     pushdown(rt,r-l+1);
62     int m=(l+r)/2;
63     ll ret=0;
64     if ( L<=m ) ret+=query(L,R,lson);
65     if ( m<R ) ret+=query(L,R,rson);
66     return ret;
67 }
68 
69 int main()
70 {
71     int n,q,i,j,k,x,y,z;
72     ll ans;
73     char s[10];
74     while ( scanf("%d%d",&n,&q)!=EOF ) {
75         build(root);
76         while ( q-- ) {
77             scanf("%s",s);
78             if ( s[0]=='C' ) {
79                 scanf("%d%d%d",&x,&y,&z);
80                 update(x,y,z,root);
81             }
82             else {
83                 scanf("%d%d",&x,&y);
84                 printf("%lld
",query(x,y,root));
85             }
86         }
87     }
88     return 0;
89 }

POJ3468

3.(HDOJ1754)http://acm.hdu.edu.cn/showproblem.php?pid=1754

模板题，将求和改成求最大值即可

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 #define lson l,m,rt*2
 6 #define rson m+1,r,rt*2+1
 7 #define root 1,n,1
 8 const int maxn=200005;
 9 struct node{
10     int maxx;
11 }arr[maxn*4];
12 
13 void pushup(int rt)
14 {
15     arr[rt].maxx=max(arr[rt*2].maxx,arr[rt*2+1].maxx);
16 }
17 
18 void build(int l,int r,int rt)
19 {
20     if ( l==r ) {
21         scanf("%d",&arr[rt].maxx);
22         return;
23     }
24     int m=(l+r)/2;
25     build(lson);
26     build(rson);
27     pushup(rt);
28 }
29 
30 void update(int p,int add,int l,int r,int rt)
31 {
32     if ( l==r ) {
33         arr[rt].maxx=add;
34         return;
35     }
36     int m=(l+r)/2;
37     if ( p<=m ) update(p,add,lson);
38     else update(p,add,rson);
39     pushup(rt);
40 }
41 
42 int query(int L,int R,int l,int r,int rt)
43 {
44     if ( L<=l && r<=R ) return arr[rt].maxx;
45     int m=(l+r)/2;
46     int ret=0;
47     if ( L<=m ) ret=max(ret,query(L,R,lson));
48     if ( R>m ) ret=max(ret,query(L,R,rson));
49     return ret;
50 }
51 
52 int main()
53 {
54     int n,m,i,j,k,x,y,z;
55     char s[10];
56     while ( scanf("%d%d",&n,&m)!=EOF ) {
57         build(root);
58         while ( m-- ) {
59             scanf("%s%d%d",s,&x,&y);
60             if ( s[0]=='Q' ) printf("%d
",query(x,y,root));
61             else update(x,y,root);
62         }
63     }
64     return 0;
65 }

HDOJ1754

4.（HDOJ1394）http://acm.hdu.edu.cn/showproblem.php?pid=1394

题意：给定一段长度为n的序列，每次可以将第一个数字移动到最后一次，每移动一次求一次逆序数对，最后输出最小的逆序数对

分析：线段树求逆序数对的原理是：每次只输入一个数，然后利用线段树算出前面已经存入线段树中比它大的数的个数。本题求出原来序列的逆序数对后采用递推的方式求出后几项：对于一个num[i]从第一位移动到最后一位时，逆序数对会减少num[i]-1，会增加n-num[i]

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 #define lson l,m,rt*2
 6 #define rson m+1,r,rt*2+1
 7 #define root 1,n,1
 8 const int maxn=5005;
 9 int sum[maxn*4],num[maxn];
10 
11 void pushup(int rt)
12 {
13     sum[rt]=sum[rt*2]+sum[rt*2+1];    
14 } 
15 
16 void update(int p,int l,int r,int rt)
17 {
18     if ( l==r ) {
19         sum[rt]++;
20         return;
21     }
22     int m=(l+r)/2;
23     if ( p<=m ) update(p,lson);
24     else update(p,rson);
25     pushup(rt);
26 }
27 
28 int query(int L,int R,int l,int r,int rt)
29 {
30     if ( L<=l && r<=R ) return sum[rt];
31     int m=(l+r)/2;
32     int ret=0;
33     if ( L<=m ) ret+=query(L,R,lson);
34     if ( R>m ) ret+=query(L,R,rson);
35     return ret;
36 }
37 
38 int main()
39 {
40     int n,i,j,k,m,x,y,z,ans,now;
41     while ( scanf("%d",&n)!=EOF ) {
42         memset(sum,0,sizeof(sum));
43         ans=0;
44         for ( i=1;i<=n;i++ ) {
45             scanf("%d",&x);
46             num[i]=++x;
47         }
48         for ( i=1;i<=n;i++ ) {
49             x=query(1,num[i],root);
50             y=i-1-x;
51             ans+=y;
52             update(num[i],root);
53         }
54         now=ans;
55         for ( i=1;i<=n;i++ ) {
56             now=now-(num[i]-1)+(n-num[i]);
57             ans=min(ans,now);
58         }
59         printf("%d
",ans);
60     }
61     return 0;
62 }

HDOJ1394

5.(HDOJ2795)http://acm.hdu.edu.cn/showproblem.php?pid=2795

题意；有一个n*w的公告栏，有q条消息，每条消息占据1*x的位置，消息摆放的位置是最上边最左边，每次给定消息输出位置

分析：附加值为最大值，每次访问判断最大值。边访问边更新，每次优先往左更新，返回位置。

注意：1.注意刚开始需要拿n和q进行比较，不然n的范围太大存不了。 2.build的时候将所有maxx[rt]都变成w即可。 3.每次给定长度时直接判断maxx[1]是否满足条件。 4.注意边query边update的写法

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

HDOJ2795

6.（POJ2828）http://poj.org/problem?id=2828

题意：有n个人，第i个人会排在当前pos[i]位置后面的那个位置，每人有一个编号，求最后队伍从头到尾的编号

分析：因为后面每次操作会影响前面人的位置，所有考虑从最后开始考虑。

我的思路（WA）：对于第i个人最初应该站在cnt[i]=pos[i]+1的位置上，随着后面人的加入他的位置会不断往后，但是往后多少呢？首先可以求出在该项（第i项）以后（i<j<=n）所有项中cnt[j]<=cnt[i]的位置有多少个(这里用x表示满足条件的位置的个数)，表示的含义是后面有多少人插到了他的前面(即第i个人应该坐到从cnt[i]开始数，第x个空位置上)。用线段树来维护空位置的个数（返回位置下标），同时还需要用线段树来维护第i项往后位置<=cnt[i]的个数。但是不知道为啥WA了...

正确思路（AC）：用线段树来维护空位置的个数。首先考虑最后一个人（即第n个人），最后一个人的位置不受前面任何人的影响，所有可以直接放入队列当中，即cnt[n]这个位置被占据。而对倒数第二个人（即n-1）来说，若cnt[n-1]<cnt[n]，那么第n-1所坐的位置不受第n个人的影响。若cnt[n-1]>=cnt[n]，因为cnt[n]，已经被占据，所以第n-1个人的位置受到影响自动延后一个。总的来说就是每次做到第cnt[i]个空位置上。用线段树来维护区间范围内空位置的个数。对于元素来说是从头到尾逐一添加，边访问边修改

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 #define lson l,m,rt*2
 6 #define rson m+1,r,rt*2+1
 7 #define root 1,n,1
 8 const int maxn=2e5+10;
 9 int ans[maxn],sum[maxn*4];
10 struct node{
11     int pos;
12     int val;
13 }arr[maxn];
14 
15 void pushup(int rt)
16 {
17     sum[rt]=sum[rt*2]+sum[rt*2+1];
18 }
19 
20 void build(int l,int r,int rt)
21 {
22     if ( l==r ) {
23         sum[rt]=1;
24         return;
25     }
26     int m=(l+r)/2;
27     build(lson);
28     build(rson);
29     pushup(rt);
30 }
31 
32 int query(int p,int l,int r,int rt)
33 {
34     if ( l==r ) {
35         sum[rt]=0;
36         return l;
37     }
38     int m=(l+r)/2;
39     int ret=0;
40     if ( sum[rt*2]>=p ) ret=query(p,lson);
41     else ret=query(p-sum[rt*2],rson);
42     pushup(rt); 
43     return ret;
44 }
45 
46 int main()
47 {
48     int n,i,j,k,x,y,z;
49     while ( scanf("%d",&n)!=EOF ) {
50         build(root);
51         for ( i=0;i<n;i++ ) {
52             scanf("%d%d",&x,&arr[i].val);
53             arr[i].pos=x+1;
54         }
55         for ( i=n-1;i>=0;i-- ) {
56             x=query(arr[i].pos,root);
57             ans[x]=arr[i].val;
58         }
59         for ( i=1;i<=n;i++ ) {
60             printf("%d",ans[i]);
61             if ( i!=n ) printf(" ");
62             else printf("
");
63         }
64     }
65     return 0;
66 }

POJ2828

7.（POJ2452）http://poj.org/problem?id=2452

题意：给定一段长度为n的序列，先求一段最长的区间满足开头si为最小，sj为最大，中间的数都比si大比sj小。

分析：因为既要求一个大的值又要求一个小的值，那么我们将其中一个固定求另一个，即把每项都当作最小项，在他的后面去求最大。首先计算出第i项后有多少项大于si（记作cnt[i]），然后利用线段树贮存区间的最大值，对于每一项求出i到i+cnt[i]这个范围内的最大值，然后不断更新ans。但是用线段树做不知道为什么WA了，后来借鉴了网络上的路径压缩的方法十分巧妙，值得一学。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 #define lson l,m,rt*2
 6 #define rson m+1,r,rt*2+1
 7 #define root 1,n,1
 8 typedef long long ll;
 9 const ll maxn=1e5+10;
10 ll num[maxn],cnt[maxn],maxx[maxn*4],pos[maxn*4];
11 
12 void pushup(ll rt)
13 {
14     if ( maxx[rt*2]>=maxx[rt*2+1] ) {
15         maxx[rt]=maxx[rt*2];
16         pos[rt]=pos[rt*2];
17     }
18     else {
19         maxx[rt]=maxx[rt*2+1];
20         pos[rt]=pos[rt*2+1];
21     }
22 }
23 
24 void build(ll l,ll r,ll rt)
25 {
26     if ( l==r ) {
27         maxx[rt]=num[l];
28         pos[rt]=l;
29         return;
30     }
31     ll m=(l+r)/2;
32     build(lson);
33     build(rson);
34     pushup(rt);
35 }
36 
37 ll query(ll L,ll R,ll l,ll r,ll rt)
38 {
39     if ( L<=l && r<=R ) return pos[rt];
40     ll m=(l+r)/2;
41     if ( maxx[rt*2]==maxx[rt] ) return query(L,R,lson);
42     else return query(L,R,rson);
43 }
44 
45 int main()
46 {
47     ll n,i,j,k,x,y,z,ans,now;
48     while ( scanf("%lld",&n)!=EOF ) {
49         for ( i=1;i<=n;i++ ) scanf("%lld",&num[i]);
50         memset(cnt,0,sizeof(cnt));
51         for ( i=1;i<=n;i++ ) {
52             for ( j=i+1;j<=n;j++ ) {
53                 if ( num[j]>num[i] ) cnt[i]++;
54                 else break;
55             }
56         } 
57         build(root);
58         ans=-1;
59         for ( i=1;i<=n;i++ ) {
60             if ( cnt[i]>0 ) {
61                 now=query(i,i+cnt[i],root)-i;
62                 ans=max(now,ans);
63             }
64         }
65         printf("%lld
",ans);
66     }
67     return 0;
68 }

POJ2452（线段树WA）

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 const int maxn=5e4+10;
 6 int num[maxn],cnt[maxn]; //num记录初始的数组,cnt[i]-1表示从i后面有多少个连续的数大于num[i] 
 7 
 8 int main()
 9 {
10     int i,j,k,n,m,x,y,z,ans,now,maxx,add;
11     while ( scanf("%d",&n)!=EOF ) {
12         for ( i=1;i<=n;i++ ) {
13             scanf("%d",&num[i]);
14             cnt[i]=1;
15         }
16         cnt[n+1]=-1; //主要要对末尾进行特殊处理 
17         ans=0;
18         for ( i=n;i>0;i-- ) { //从后往前计算 
19             while ( num[i]<num[i+cnt[i]] ) { //使得每次不止跳1的长度 
20                 cnt[i]+=cnt[i+cnt[i]];
21             }
22         }
23         for ( i=1;i<=n;i+=(add+1) ) { //第i次结束后跳到对于i来说的最大值的下一个位置 
24             maxx=add=-1; //maxx记录最大值，add记录长度 
25             for ( j=0;j<cnt[i];j++ ) {
26                 if ( num[i+j]>maxx ) {
27                     maxx=num[i+j];
28                     add=j;
29                 }
30             }
31             ans=max(ans,add);
32         }
33         if ( ans ) printf("%d
",ans);
34         else printf("-1
");
35     }
36     return 0;
37 }

POJ2452（数组+路径压缩AC）

区间染色

1.（HDOJ1689）http://acm.hdu.edu.cn/showproblem.php?pid=1698

题意：一条铁链有n段，初始时每段价值都是1，进行q次操作，每次操作给出x,y,z，表示将x到y这段区域中所有的子段替换成价值为z。求最后这个铁链的价值

分析：为经典的区间染色题，将模板进行稍许的修改即可

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 #define lson l,m,rt*2
 6 #define rson m+1,r,rt*2+1
 7 #define root 1,n,1
 8 const int maxn=100500;
 9 struct node{
10     int sum;
11 }arr[maxn*4];
12 int add[maxn*4];
13 
14 void pushup(int rt)
15 {
16     arr[rt].sum=arr[rt*2].sum+arr[rt*2+1].sum;
17 }
18 
19 void pushdown(int rt,int m)
20 {
21     if ( add[rt] ) {
22         add[rt*2]=add[rt];
23         add[rt*2+1]=add[rt];
24         arr[rt*2].sum=add[rt]*(m-m/2);
25         arr[rt*2+1].sum=add[rt]*(m/2);
26         add[rt]=0;
27     }
28 }
29 
30 void build(int l,int r,int rt)
31 {
32     add[rt]=0;
33     if ( l==r ) {
34         arr[rt].sum=1;
35         return;
36     }
37     int m=(l+r)/2;
38     build(lson);
39     build(rson);
40     pushup(rt);
41 }
42 
43 void update(int L,int R,int c,int l,int r,int rt)
44 {
45     if ( L<=l && r<=R ) {
46         add[rt]=c;
47         arr[rt].sum=c*(r-l+1);
48         return;
49     }
50     pushdown(rt,r-l+1);
51     int m=(l+r)/2;
52     if ( L<=m ) update(L,R,c,lson);
53     if ( m<R ) update(L,R,c,rson);
54     pushup(rt);
55 }
56 
57 int query(int L,int R,int l,int r,int rt)
58 {
59     if ( L<=l && r<=R ) return arr[rt].sum;
60     pushdown(rt,r-l+1);
61     int m=(l+r)/2;
62     int ret=0;
63     if ( L<=m ) ret+=query(L,R,lson);
64     if ( m<R ) ret+=query(L,R,rson);
65     return ret;
66 } 
67 
68 int main()
69 {
70     int i,j,k,T,x,y,z,n,m,q,h;
71     scanf("%d",&T);
72     for ( h=1;h<=T;h++ ) {
73         scanf("%d",&n);
74         build(root);
75         scanf("%d",&q);
76         while ( q-- ) {
77             scanf("%d%d%d",&x,&y,&z);
78             update(x,y,z,root);
79         }
80         printf("Case %d: The total value of the hook is %d.
",h,arr[1].sum);
81     }
82     return 0;
83 }

HDOJ1689

2.（HDOJ3308）http://acm.hdu.edu.cn/showproblem.php?pid=3308

题意：给定一段序列，有两种操作：1.单点替换，2.区间查找最长连续递增子串的长度

分析：考察区间合并，使用数组较为方便。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 #define lson l,m,rt*2
 6 #define rson m+1,r,rt*2+1
 7 #define root 1,n,1
 8 const int maxn=1e5+10;
 9 int lmax[maxn*4],rmax[maxn*4],num[maxn],maxx[maxn*4];
10 //lmax表示一段中前缀的最长递增子串，rmax表示后缀的，maxx表示整个区间的
11 //特别注意num，是按照序号存储本身的值，而不表示一段一段 
12 
13 void pushup(int l,int r,int rt)
14 {
15     int x,y;
16     int m=(l+r)/2; //区间中值 
17     int len=r-l+1; //区间长度 
18     //在不考虑合并区间时有以下三个操作 
19     maxx[rt]=max(maxx[rt*2],maxx[rt*2+1]); 
20     lmax[rt]=lmax[rt*2];
21     rmax[rt]=rmax[rt*2+1];
22     if ( num[m+1]>num[m] ) { //当两个区间满足条件即可合并 
23         x=rmax[rt*2]+lmax[rt*2+1];
24         maxx[rt]=max(maxx[rt],x);
25         if ( lmax[rt*2]==(len-len/2) ) lmax[rt]+=lmax[rt*2+1];
26         if ( rmax[rt*2+1]==len/2 ) rmax[rt]+=rmax[rt*2];
27     }
28 }
29 
30 void build(int l,int r,int rt)
31 {
32     if ( l==r ) {
33         scanf("%d",&num[l]);
34         maxx[rt]=lmax[rt]=rmax[rt]=1;
35         return;
36     }
37     maxx[rt]=lmax[rt]=rmax[rt]=0;
38     int m=(l+r)/2;
39     build(lson);
40     build(rson);
41     pushup(l,r,rt);
42 }
43 
44 void update(int p,int add,int l,int r,int rt)
45 {
46     if ( l==r ) {
47         num[p]=add;
48         return;
49     }
50     int m=(l+r)/2;
51     if ( p<=m ) update(p,add,lson);
52     else update(p,add,rson);
53     pushup(l,r,rt); 
54 }
55 
56 int query(int L,int R,int l,int r,int rt)
57 {
58     if ( L<=l && r<=R ) return maxx[rt];
59     int m=(l+r)/2;
60     int ret=0;
61     if ( L<=m ) ret=max(ret,query(L,R,lson));
62     if ( R>m ) ret=max(ret,query(L,R,rson));
63     //以下还有一个区间合并的操作 
64     if ( num[m]<num[m+1] ) {
65         int c=min(rmax[rt*2],m-L+1)+min(lmax[rt*2+1],R-m); 
66         //可能左子树的范围会超过所要求解区间的左半部分，所有取两个中较小的那个。右边同理 
67         ret=max(ret,c);
68     }
69     return ret;
70 }
71 
72 int main()
73 {
74     int T,i,j,k,n,m,x,y;
75     char s[10];
76     scanf("%d",&T);
77     while ( T-- ) {
78         scanf("%d%d",&n,&m);
79         build(1,n,1);
80         while ( m-- ) {
81             scanf("%s%d%d",s,&x,&y);
82             x++; //因为模板是从1开始的，而题目的编号从0开始 
83             if ( s[0]=='U' ) update(x,y,root);
84             else printf("%d
",query(x,++y,root));
85         }
86     }
87     return 0;
88 }

HDOJ3308

3.（POJ3368）http://poj.org/problem?id=3368

题意：从小到大给定一段长度为n的序列，有q次询问，每次询问给定一段[x,y]，求在[x,y]范围内出现最频繁数出现的次数

分析：和上题类似，考察区间合并。序列本身的值存在num[]中，设置3个数组分别维护前缀的最大长度、后缀的最大长度以及整个段的最大长度

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 #define lson l,m,rt*2
 6 #define rson m+1,r,rt*2+1
 7 #define root 1,n,1
 8 const int maxn=1e5+10;
 9 int num[maxn],lmax[maxn*4],rmax[maxn*4],maxx[maxn*4];
10 
11 void pushup(int l,int r,int rt)
12 {
13     int m=(l+r)/2;
14     int len=r-l+1;
15     maxx[rt]=max(maxx[rt*2],maxx[rt*2+1]);
16     lmax[rt]=lmax[rt*2];
17     rmax[rt]=rmax[rt*2+1];
18     if ( num[m]==num[m+1] ) {
19         maxx[rt]=max(maxx[rt],rmax[rt*2]+lmax[rt*2+1]);
20         if ( lmax[rt*2]==(len-len/2) ) lmax[rt]+=lmax[rt*2+1];
21         if ( rmax[rt*2+1]==len/2 ) rmax[rt]+=rmax[rt*2]; 
22     }
23 }
24 
25 void build(int l,int r,int rt)
26 {
27     if ( l==r ) {
28         scanf("%d",&num[l]);
29         maxx[rt]=lmax[rt]=rmax[rt]=1;
30         return;
31     }
32     int m=(l+r)/2;
33     build(lson);
34     build(rson);
35     pushup(l,r,rt);
36 }
37 
38 int query(int L,int R,int l,int r,int rt)
39 {
40     if ( L<=l && r<=R ) return maxx[rt];
41     int m=(l+r)/2;
42     int ret=0;
43     if ( L<=m ) ret=max(ret,query(L,R,lson));
44     if ( R>m ) ret=max(ret,query(L,R,rson));
45     if ( num[m]==num[m+1] ) {
46         int c=min(rmax[rt*2],m-L+1)+min(lmax[rt*2+1],R-m);
47         ret=max(ret,c);
48     }
49     return ret;
50 }
51 
52 int main()
53 {
54     int n,i,j,k,q,x,y;
55     while ( scanf("%d",&n)!=EOF && n ) {
56         scanf("%d",&q);
57         build(root);
58         while ( q-- ) {
59             scanf("%d%d",&x,&y);
60             printf("%d
",query(x,y,root));
61         }
62     }
63     return 0;
64 }

POJ3368

4.(POJ2777)http://poj.org/problem?id=2777

题意：给定一段长度为n的序列，用数字表示颜色，起初序列全为1，存在两种操作：1.将某一段全部替换成另一种颜色 2.输出某一段存在的颜色个数

分析：采用二进制的思想，对于颜色i来说用1<<（i-1）表示。当求有几种颜色的时候用|进行叠加，最后还原出一个数在二进制下多少个1，即为有几种颜色。同时特别注意给定的区间可能前面大于后面注意一定要交换

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 #define lson l,m,rt*2
 6 #define rson m+1,r,rt*2+1
 7 #define root 1,n,1
 8 typedef long long ll;
 9 const ll maxn=1e5+10;
10 ll sum[maxn*4],add[maxn*4],w;
11 
12 void pushup(ll rt)
13 {
14     sum[rt]=sum[rt*2]|sum[rt*2+1];
15 }
16 
17 void pushdown(ll rt,ll m)
18 {
19     if ( add[rt] ) {
20         add[rt*2]=add[rt];
21         add[rt*2+1]=add[rt];
22         sum[rt*2]=1<<(add[rt]-1);
23         sum[rt*2+1]=1<<(add[rt]-1);
24         add[rt]=0;
25     }
26 }
27 
28 void build(ll l,ll r,ll rt)
29 {
30     add[rt]=0;
31     if ( l==r ) {
32         sum[rt]=1;
33         return;
34     }
35     ll m=(l+r)/2;
36     build(lson);
37     build(rson);
38     pushup(rt);
39 }
40 
41 void update(ll L,ll R,ll c,ll l,ll r,ll rt)
42 {
43     if ( L<=l && r<=R ) {
44         add[rt]=c;
45         sum[rt]=1<<(c-1);
46         return;
47     }
48     pushdown(rt,r-l+1);
49     ll m=(l+r)/2;
50     if ( L<=m ) update(L,R,c,lson);
51     if ( m<R ) update(L,R,c,rson);
52     pushup(rt);
53 }
54 
55 ll query(ll L,ll R,ll l,ll r,ll rt)
56 {
57     if ( L<=l && r<=R ) return sum[rt];
58     pushdown(rt,r-l+1);
59     ll m=(l+r)/2;
60     ll ret=0;
61     if ( L<=m ) ret|=query(L,R,lson);
62     if ( m<R ) ret|=query(L,R,rson);
63     return ret;
64 }
65 
66 ll judge(ll x)
67 {
68     ll cnt=0;
69     for ( ll i=0;i<w;i++ ) {
70         if ( x&(1<<(i)) ) cnt++;
71     }
72     return cnt;
73 }
74 
75 int main()
76 {
77     ll n,m,x,y,z,u,v,i,j,k;
78     char s[10];
79     while ( scanf("%lld%lld%lld",&n,&w,&m)!=EOF ) {
80         build(root);
81         memset(add,0,sizeof(add));
82         for ( i=0;i<m;i++ ) {
83             scanf("%s",s);
84             if ( s[0]=='C' ) {
85                 scanf("%lld%lld%lld",&x,&y,&z);
86                 if ( x>y ) swap(x,y);
87                 update(x,y,z,root);
88             }
89             else {
90                 scanf("%lld%lld",&x,&y);
91                 if ( x>y ) swap(x,y);
92                 u=query(x,y,root);
93                 printf("%lld
",judge(u));
94             }
95         }
96     }
97     return 0;
98 }

POJ2777

5.（POJ3667）http://poj.org/problem?id=3667

离线操作

小结：一般都是对某一区间满足某个条件的一些数进行操作。这时候需要将访问的区间存起来。按照某一规则进行排列。对于每一个访问去除掉那些不符合条件的数。这样可以将其变成普通线段树，对于每个访问就是先更新某个值，在进行询问操作。

1.（HDOJ4417）http://acm.hdu.edu.cn/showproblem.php?pid=4417

题意：有一条长度为n的管道，每段高为h[i]，有m个询问，每次询问给出x,y,z代表在[x,y]这个范围内他的跳跃高度z，对于每次询问输出可以撞到几段的顶部（即z>=h[i]算撞到）

首先转变一下题意：有一个长度为n的序列，每项的值为num[i]，给出一段访问区间和一个数k，求在这个范围内<=k的的数有多少

分析：采用线段树离线操作，将所有询问先保存下来。将每个询问按h从大到小进行排序，对于第i个询问，在该区间中将所有num[i]>h的一段去除。剩下的部分采用线段树经典求和即可。初始化将所有叶子节点的sum[rt]=1，对于每个num[i]>=h的那段，将第i个位置的sum更新为0。但是因为对于每个区间查找需要O(n)的复杂度，会倒是超时

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 #define lson l,m,rt*2
 6 #define rson m+1,r,rt*2+1
 7 #define root 1,n,1
 8 const int maxn=1e5+10;
 9 int sum[maxn*4],num[maxn],ans[maxn];
10 struct node{
11     int l;
12     int r;
13     int h;
14     int index;
15 }arr[maxn];
16 
17 void pushup(int rt)
18 {
19     sum[rt]=sum[rt*2]+sum[rt*2+1];
20 }
21 
22 void build(int l,int r,int rt)
23 {
24     if ( l==r ) {
25         sum[rt]=1;
26         return;
27     }
28     int m=(l+r)/2;
29     build(lson);
30     build(rson);
31     pushup(rt);
32 }
33 
34 void update(int p,int l,int r,int rt)
35 {
36     if ( l==r ) {
37         sum[rt]=0;
38         return;
39     }
40     int m=(l+r)/2;
41     if ( p<=m ) update(p,lson);
42     else update(p,rson);
43     pushup(rt);
44 }
45 
46 int query(int L,int R,int l,int r,int rt)
47 {
48     if ( L<=l && r<=R ) return sum[rt];
49     int m=(l+r)/2;
50     int ret=0;
51     if ( L<=m ) ret+=query(L,R,lson);
52     if ( R>m ) ret+=query(L,R,rson);
53     return ret;
54 }
55 
56 bool cmp(node a,node b)
57 {
58     return a.h>b.h;
59 }
60 
61 int main()
62 {
63     int T,i,j,k,h,n,m;
64     scanf("%d",&T);
65     for ( h=1;h<=T;h++ ) {
66         scanf("%d%d",&n,&m);
67         for ( i=1;i<=n;i++ ) scanf("%d",&num[i]);
68         build(root);
69         for ( i=1;i<=m;i++ ) {
70             scanf("%d%d%d",&arr[i].l,&arr[i].r,&arr[i].h);
71             arr[i].l++;
72             arr[i].r++;
73             arr[i].index=i;
74         }
75         sort(arr+1,arr+m+1,cmp);
76         for ( i=1;i<=m;i++ ) {
77             for ( j=arr[i].l;j<=arr[i].r;j++ ) {
78                 if ( num[j]>arr[i].h ) {
79                     update(j,root);
80                 }
81             }
82             ans[arr[i].index]=query(arr[i].l,arr[i].r,root);
83         }
84         printf("Case %d:
",h);
85         for ( i=1;i<=m;i++ ) printf("%d
",ans[i]);
86     }
87     return 0;
88 }

HDOJ4417（TLE）

所以改进查找区间范围内>k的数的范围。将其（对于每一个i，都有num和index=i两项）保存在结构体，按照num的值从大到小进行排列，每次查找时都接着上次查找结束的位置继续查找，可以将全体范围内>k的数都删除。

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<algorithm>
  4 using namespace std;
  5 #define lson l,m,rt*2
  6 #define rson m+1,r,rt*2+1
  7 #define root 1,n,1
  8 const int maxn=1e5+10;
  9 int sum[maxn*4],num[maxn],ans[maxn];
 10 struct node{
 11     int l;
 12     int r;
 13     int h;
 14     int index;
 15 }arr[maxn];
 16 struct node_{
 17     int val;
 18     int index;
 19 }arr_[maxn];
 20 
 21 void pushup(int rt)
 22 {
 23     sum[rt]=sum[rt*2]+sum[rt*2+1];
 24 }
 25 
 26 void build(int l,int r,int rt)
 27 {
 28     if ( l==r ) {
 29         sum[rt]=1;
 30         return;
 31     }
 32     int m=(l+r)/2;
 33     build(lson);
 34     build(rson);
 35     pushup(rt);
 36 }
 37 
 38 void update(int p,int l,int r,int rt)
 39 {
 40     if ( l==r ) {
 41         sum[rt]=0;
 42         return;
 43     }
 44     int m=(l+r)/2;
 45     if ( p<=m ) update(p,lson);
 46     else update(p,rson);
 47     pushup(rt);
 48 }
 49 
 50 int query(int L,int R,int l,int r,int rt)
 51 {
 52     if ( L<=l && r<=R ) return sum[rt];
 53     int m=(l+r)/2;
 54     int ret=0;
 55     if ( L<=m ) ret+=query(L,R,lson);
 56     if ( R>m ) ret+=query(L,R,rson);
 57     return ret;
 58 }
 59 
 60 bool cmp(node a,node b)
 61 {
 62     return a.h>b.h;
 63 }
 64 
 65 bool cmp_(node_ a,node_ b)
 66 {
 67     return a.val>b.val;
 68 }
 69 
 70 int main()
 71 {
 72     int T,i,j,h,n,m,cnt;
 73     scanf("%d",&T);
 74     for ( h=1;h<=T;h++ ) {
 75         scanf("%d%d",&n,&m);
 76         for ( i=1;i<=n;i++ ) {
 77             scanf("%d",&arr_[i].val);
 78             arr_[i].index=i;
 79         }
 80         sort(arr_+1,arr_+n+1,cmp_);
 81         build(root);
 82         for ( i=1;i<=m;i++ ) {
 83             scanf("%d%d%d",&arr[i].l,&arr[i].r,&arr[i].h);
 84             arr[i].l++;
 85             arr[i].r++;
 86             arr[i].index=i;
 87         }
 88         sort(arr+1,arr+m+1,cmp);
 89         cnt=1;
 90         for ( i=1;i<=m;i++ ) {
 91             for ( j=cnt;j<=n;j++&&cnt++ ) {
 92                 if ( arr_[j].val>arr[i].h ) {
 93                     update(arr_[j].index,root);
 94                 }
 95                 else break;
 96             }
 97             ans[arr[i].index]=query(arr[i].l,arr[i].r,root);
 98         }
 99         printf("Case %d:
",h);
100         for ( i=1;i<=m;i++ ) printf("%d
",ans[i]);
101     }
102     return 0;
103 }

HDOJ4417

2.（HDOJ3333）http://acm.hdu.edu.cn/showproblem.php?pid=3333 （HDOJ3874同，只是那道题数据范围更小）

题意：有一段长度为n的序列，每次给定一个范围，求这个范围内不相等数的和

分析：如果一次将所有值都存入线段树内则无法判断哪些数相等。所有采用先将所有访问按照右边界的值从小到大排列（至于这么做为什么可以？因为对于每个重复的数来说，只有从右端点起向左的第一个数才是有效的，其他的都是无用的），然后再依次添加。同时用map记录每个数对应的下标，如果遇到相同的数，则将之前位置的那个数变成0，同时更新map。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #include<map>
 5 using namespace std;
 6 #define lson l,m,rt*2
 7 #define rson m+1,r,rt*2+1
 8 #define root 1,n,1
 9 typedef long long ll;
10 const ll maxn=1e5+10;
11 const ll maxm=1e5+10;
12 ll sum[maxn*4],num[maxn],ans[maxn];
13 map<ll,ll>mp;
14 struct node{
15     ll l;
16     ll r;
17     ll index;
18 }arr[maxm];
19 
20 void pushup(ll rt)
21 {
22     sum[rt]=sum[rt*2]+sum[rt*2+1];
23 }
24 
25 void build(ll l,ll r,ll rt)
26 {
27     if ( l==r ) {
28         sum[rt]=num[l];
29         return;
30     }
31     ll m=(l+r)/2;
32     build(lson);
33     build(rson);
34     pushup(rt);
35 }
36 
37 void update(ll p,ll l,ll r,ll rt)
38 {
39     if ( l==r ) {
40         sum[rt]=0;
41         return;
42     }
43     ll m=(l+r)/2;
44     if ( p<=m ) update(p,lson);
45     else update(p,rson);
46     pushup(rt);
47 }
48 
49 ll query(ll L,ll R,ll l,ll r,ll rt)
50 {
51     if ( L<=l && r<=R ) return sum[rt];
52     ll m=(l+r)/2;
53     ll ret=0;
54     if ( L<=m ) ret+=query(L,R,lson);
55     if ( m<R ) ret+=query(L,R,rson);
56     return ret;
57 }
58 
59 bool cmp(node a,node b)
60 {
61     return a.r<b.r;
62 }
63 
64 int main()
65 {
66     ll T,i,j,k,n,m,x,y,z,cnt;
67     scanf("%lld",&T);
68     while ( T-- ) {
69         scanf("%lld",&n);
70         mp.clear();
71         for ( i=1;i<=n;i++ ) scanf("%lld",&num[i]);
72         build(root);
73         scanf("%lld",&m);
74         for ( i=1;i<=m;i++ ) {
75             scanf("%lld%lld",&arr[i].l,&arr[i].r);
76             arr[i].index=i;
77         }
78         sort(arr+1,arr+1+m,cmp);
79         cnt=1;
80         for ( i=1;i<=m;i++ ) {
81             for ( ;cnt<=arr[i].r;cnt++ ) {
82                 if ( mp[num[cnt]]!=0 ) update(mp[num[cnt]],root);
83                 mp[num[cnt]]=cnt;
84             }
85             ans[arr[i].index]=query(arr[i].l,arr[i].r,root);
86         }
87         for ( i=1;i<=m;i++ ) printf("%I64d
",ans[i]);
88     }
89     return 0;
90 }

HDOJ3333

DFS序和线段树

DFS序：即将原本的树状结构转化成线性结构，通过DFS记录进栈的时间戳in[i]和出栈的时间戳out[i]，而[in[i],out[i]]为该节点所维护的区间，对于任意处于[in[i]+1,out[i]]都是i的子节点。建树时对于结点i将所维护的值添加到in[i]这个位置即可。每次对某个节点操作时就是对该节点所在的区间进行操作。

1.（HDOJ4366）http://acm.hdu.edu.cn/showproblem.php?pid=4366

题意：先总共有n个人，老板的编号为n,员工的编号从1到n-1，每个人都有一个能力值和忠诚度和对应上司。现在老板要解雇几个人，对于每一个解雇的人，从能力值大于他的下属中（直接/间接）选择忠诚度最高的来接替他。

分析：离线处理+DFS序+线段树

DFS序将原本的关系网（树）转化成线性结构。因为选择的下属能力值必须要大于上司，所有将能力值按从大到小进行排序、操作（离线操作），每次访问他的子节点中（即[in[i]+1,out[i]]这个区间）忠诚度最大的（利用map将忠诚度和编号对应，这样得到能力值就知道编号了），然后将其添加到线段树中。另一个关键是如何处理能力值相同的人，添加的顺序会影响最终的结果，所以排序时将id小的排在后面（id小的会影响id大的）

2.（HDOJ3974）http://acm.hdu.edu.cn/showproblem.php?pid=3974

题意：有n个员工编号从1到n，有n-1条关系每条关系输入x,y,表示y是x的上司。有m条操作，有两类操作第一类是分配给某个人一项任务（则他的全部下属全部和他做同样的工作，有新工作时直接覆盖），另一种是查询某个人当前在做什么工作

分析：DFS序+线段树。因为是关系网（树状结构），所有采用DFS序将其转化成线性结构。当上司做一项工作时他的属下全部和上司做一样的工作，那么我们可以采用线段树当中的替换。于此同时我们可以设置一个父节点，和那些没有父亲的点相连。

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<algorithm>
  4 #include<vector>
  5 using namespace std;
  6 #define lson l,m,rt*2
  7 #define rson m+1,r,rt*2+1
  8 #define root 1,cnt,1
  9 const int maxn=1e5+10;
 10 int a[maxn*4],add[maxn*4],cnt,in[maxn],out[maxn];
 11 bool vis[maxn];
 12 vector<int>G[maxn];
 13 
 14 void pushdown(int rt,int m)
 15 {
 16     if ( add[rt] ) {
 17         add[rt*2]=add[rt];
 18         add[rt*2+1]=add[rt];
 19         a[rt*2]=add[rt];
 20         a[rt*2+1]=add[rt];
 21         add[rt]=0;
 22     }
 23 }
 24 
 25 void build(int l,int r,int rt)
 26 {
 27     add[rt]=0;
 28     a[rt]=-1;
 29     if ( l==r ) return;
 30     int m=(l+r)/2;
 31     build(lson);
 32     build(rson);
 33 }
 34 
 35 void update(int L,int R,int c,int l,int r,int rt)
 36 {
 37     if ( L<=l && r<=R ) {
 38         add[rt]=c;
 39         a[rt]=c;
 40         return;
 41     }
 42     pushdown(rt,r-l+1);
 43     int m=(l+r)/2;
 44     if ( L<=m ) update(L,R,c,lson);
 45     if ( m<R ) update(L,R,c,rson);
 46 } 
 47 
 48 int query(int L,int R,int l,int r,int rt)
 49 {
 50     if ( L<=l && r<=R ) return a[rt];
 51     pushdown(rt,r-l+1);
 52     int m=(l+r)/2;
 53     if ( L<=m ) return query(L,R,lson);
 54     else return query(L,R,rson);
 55 }
 56 
 57 void DFS(int u)
 58 {
 59     in[u]=++cnt;
 60     for ( int i=0;i<G[u].size();i++ ) {
 61         int v=G[u][i];
 62         DFS(v);
 63     }
 64     out[u]=cnt;
 65 }
 66 
 67 int main()
 68 {
 69     int T,i,j,k,h,x,y,z,n,m;
 70     char s[10];
 71     scanf("%d",&T);
 72     for ( h=1;h<=T;h++ ) {
 73         scanf("%d",&n);
 74         for ( i=0;i<=n;i++ ) {
 75             G[i].clear();
 76             vis[i]=false;
 77         }
 78         for ( i=1;i<n;i++ ) {
 79             scanf("%d%d",&x,&y);
 80             G[y].push_back(x);
 81             vis[x]=true;
 82         }
 83         for ( i=1;i<=n;i++ ) {
 84             if ( !vis[i] ) {
 85                 G[0].push_back(i);
 86             }
 87         }
 88         cnt=0;
 89         DFS(0);
 90         memset(a,-1,sizeof(a));
 91         memset(add,0,sizeof(add));
 92         printf("Case #%d:
",h);
 93         scanf("%d",&m);
 94         while ( m-- ) {
 95             scanf("%s",s);
 96             if ( s[0]=='T' ) {
 97                 scanf("%d%d",&x,&y);
 98                 update(in[x],out[x],y,root);
 99             }
100             else {
101                 scanf("%d",&x);
102                 printf("%d
",query(in[x],out[x],root));
103             }
104         }
105     }
106     return 0;
107 }

HDOJ3974

3.（HDOJ5692）http://acm.hdu.edu.cn/showproblem.php?pid=5692

区间合并