前几天学习了划分树和SBT,一直没机会训练一下，今天实验室有网了，就训练POJ上面一道水题。分别用两种数据结构来实现了一下！

   这道题题目很简单，就是给定序列，求区间最小值！

   SBT：

1. #include<stdio.h> 
2. #include<algorithm> 
3. using namespace std; 
4. #define M 100005 
5. struct SBT{ 
6.     int key,left,right,size; 
7. }tree[M]; 
8. int root,top; 
9.  
10. int a[M]; 
11. struct Query{ 
12.     int ql,qr,k,id,ans; 
13. }que[M/2]; 
14. bool cmp(const Query &q1,const Query &q2){ 
15.     if(q1.ql==q2.ql){ 
16.         return q1.qr<q2.qr; 
17.     } 
18.     return q1.ql<q2.ql; 
19. } 
20. bool cmp2(const Query &q1,const Query &q2){ 
21.     return q1.id<q2.id; 
22. } 
23. void init(){ 
24.     root=top=0; 
25. } 
26. //这两种旋转看起来是挺容易的，但自己写容易混乱，最好能结合图 
27. void rotate_left(int &x){ 
28.     int y=tree[x].right; 
29.     tree[x].right=tree[y].left; 
30.     tree[y].left=x; 
31.     tree[y].size=tree[x].size; 
32.     tree[x].size=tree[tree[x].left].size+tree[tree[x].right].size+1; 
33.     x=y; 
34.  
35. } 
36. void rotate_right(int &x){ 
37.     int y=tree[x].left; 
38.     tree[x].left=tree[y].right; 
39.     tree[y].right=x; 
40.     tree[y].size=tree[x].size; 
41.     tree[x].size=tree[tree[x].left].size+tree[tree[x].right].size+1; 
42.     x=y; 
43. } 
44. void maintain(int &x,bool flag){ 
45.     if(flag==false){
    //数据插入到左边了 
46.         if(tree[tree[tree[x].left].left].size>tree[tree[x].right].size){
    //情况 1 
47.             //左孩子的左子树大于右孩子 
48.             rotate_right(x); 
49.         }else if(tree[tree[tree[x].left].right].size>tree[tree[x].right].size){ //情况 2 
50.             rotate_left(tree[x].left);//先把树旋转成: 情况 1 
51.             rotate_right(x);//按照情况1进行旋转 
52.         }else return ; 
53.     }else{
    //数据插入到右边了 
54.         if(tree[tree[tree[x].right].right].size>tree[tree[x].left].size){ 
55.             rotate_left(x); 
56.         }else if(tree[tree[tree[x].right].left].size>tree[tree[x].left].size){ 
57.             rotate_right(tree[x].right); 
58.             rotate_left(x); 
59.         }else return ; 
60.     } 
61.     maintain(tree[x].left,false); 
62.     maintain(tree[x].right,true); 
63.     maintain(x,false); 
64.     maintain(x,true); 
65. } 
66. /* 
67.  * 这里用数组实现，递归插入，挺巧妙的，我自己用数组做的时候都不会想到这样做 
68.  * tree的0位置空着不用; 帅气，如果不进行调整的话，root能保持root=1 
69.  * */ 
70. void insert(int &x,int key){ 
71.     if(x==0){ 
72.         x=++top;//确定插入的数组下标 
73.         tree[x].left=tree[x].right=0; 
74.         tree[x].key=key; 
75.         tree[x].size=1; 
76.     }else{ 
77.         tree[x].size++; 
78.         if(key<=tree[x].key)//把相同的元素插入到左边 
79.             insert(tree[x].left,key); 
80.         else insert(tree[x].right,key); 
81.         maintain(x,key>tree[x].key); 
82.     } 
83. } 
84. //这里要保证删除的数据存在 
85. void remove(int &x,int key){ 
86.     tree[x].size--; 
87.     if(key>tree[x].key){ 
88.         remove(tree[x].right,key); 
89.     }else if(key<tree[x].key){ 
90.         remove(tree[x].left,key); 
91.     }else{ 
92.         //有左子树，无右子树 
93.         if(tree[x].left!=0&&tree[x].right==0){ 
94.             x=tree[x].left; 
95.             //无左子树，有右子树 
96.         }else if(tree[x].right!=0&&tree[x].left==0){ 
97.             x=tree[x].right; 
98.         //叶子结点 
99.         }else if(tree[x].left==0&&tree[x].right==0){ 
100.             x=0; 
101.             //有左子树，也有右子树 
102.         }else{ 
103.             int temp=tree[x].right; 
104.             while(tree[temp].left)temp=tree[temp].left; 
105.             tree[x].key=tree[temp].key; 
106.             remove(tree[x].right,tree[temp].key); 
107.         } 
108.     } 
109. } 
110. //求第k小的数 
111. int select(int &x,int k){ 
112.     int r=tree[tree[x].left].size+1; 
113.     if(r==k)return tree[x].key; 
114.     else if(r<k)return select(tree[x].right,k-r); 
115.     else return select(tree[x].left,k); 
116. } 
117. int main(){ 
118.     int n,m; 
119.     int i,j; 
120.     init(); 
121.     scanf("%d %d",&n,&m); 
122.     for(i=1;i<=n;i++){ 
123.         scanf("%d",&a[i]); 
124.     } 
125.     int ql,qr,k; 
126.     for(i=0;i<m;i++){ 
127.         scanf("%d %d %d",&ql,&qr,&k); 
128.         que[i].id=i; 
129.         que[i].k=k; 
130.         que[i].ql=ql; 
131.         que[i].qr=qr; 
132.     } 
133.     sort(que,que+m,cmp); 
134.     for(i=que[0].ql;i<=que[0].qr;i++){ 
135.         insert(root,a[i]); 
136.     } 
137.     que[0].ans=select(root,que[0].k); 
138.     for(i=1;i<m;i++){ 
139.         //前一个区间与当前区间只有两种关系，相交或者不相交 
140.         if(que[i].ql<=que[i-1].qr){ 
141.             //看起点 
142.             if(que[i].ql>que[i-1].ql){ 
143.                 for(j=que[i-1].ql;j<que[i].ql;j++){ 
144.                     remove(root,a[j]); 
145.                 } 
146.             } 
147.             //看终点 
148.             if(que[i].qr<que[i-1].qr){
     // 
149.                 for(j=que[i].qr+1;j<=que[i-1].qr;j++){ 
150.                     remove(root,a[j]); 
151.                 } 
152.             }else if(que[i].qr>que[i-1].qr){ 
153.                 for(j=que[i-1].qr+1;j<=que[i].qr;j++){ 
154.                     insert(root,a[j]); 
155.                 } 
156.             } 
157.         }else{ 
158.             for(j=que[i-1].ql;j<=que[i-1].qr;j++){ 
159.                 remove(root,a[j]); 
160.             } 
161.             for(j=que[i].ql;j<=que[i].qr;j++){ 
162.                 insert(root,a[j]); 
163.             } 
164.         } 
165.  
166.         que[i].ans=select(root,que[i].k); 
167.     } 
168.     sort(que,que+m,cmp2); 
169.     for(i=0;i<m;i++){ 
170.         printf("%d\n",que[i].ans); 
171.     } 
172.     return 0; 
173. } 

划分树：

1. #include<stdio.h> 
2. #include<algorithm> 
3. using namespace std; 
4. #define M 100005 
5. int tree[30][M]; 
6. int toLeft[30][M]; 
7. int sorted[M]; 
8.  
9. int n,m; 
10. void build(int level,int left,int right){ 
11.     if(left==right)return; 
12.     int mid=(left+right)>>1; 
13.     int suppose; 
14.     int i; 
15.     suppose=mid-left+1; 
16.     for(i=left;i<=right;i++){ 
17.         if(tree[level][i]<sorted[mid]){ 
18.             suppose--; 
19.         } 
20.     } 
21.     int lpos=left,rpos=mid+1; 
22.     for(i=left;i<=right;i++){ 
23.         if(i==left){ 
24.             toLeft[level][i]=0; 
25.         }else{ 
26.             toLeft[level][i]=toLeft[level][i-1]; 
27.         } 
28.         if(tree[level][i]<sorted[mid]){ 
29.             toLeft[level][i]++; 
30.             tree[level+1][lpos++]=tree[level][i]; 
31.         }else if(tree[level][i]>sorted[mid]){ 
32.             tree[level+1][rpos++]=tree[level][i]; 
33.         }else{ 
34.             if(suppose){ 
35.                 suppose--; 
36.                 toLeft[level][i]++; 
37.                 tree[level+1][lpos++]=tree[level][i]; 
38.             }else{ 
39.                 tree[level+1][rpos++]=tree[level][i]; 
40.             } 
41.         } 
42.     } 
43.     build(level+1,left,mid); 
44.     build(level+1,mid+1,right); 
45. } 
46. int query(int level,int left,int right,int ql,int qr,int k){ 
47.     if(ql==qr){ 
48.         return tree[level][ql]; 
49.     } 
50.     int s,ss; 
51.     int mid=(left+right)>>1; 
52.     if(left==ql){ 
53.         s=0; 
54.         ss=toLeft[level][qr]; 
55.     }else{ 
56.         s=toLeft[level][ql-1]; 
57.         ss=toLeft[level][qr]-s; 
58.     } 
59.     int nql,nqr; 
60.     if(k<=ss){ 
61.         nql=left+s; 
62.         nqr=left+s+ss-1; 
63.         return query(level+1,left,mid,nql,nqr,k); 
64.     }else{ 
65.         nql=mid-left+1+ql-s; 
66.         nqr=mid-left+1+qr-s-ss; 
67.         return query(level+1,mid+1,right,nql,nqr,k-ss); 
68.     } 
69.     return 0; 
70. } 
71. int main(){ 
72.     scanf("%d %d",&n,&m); 
73.     for(int i=1;i<=n;i++){ 
74.         scanf("%d",&sorted[i]); 
75.         tree[0][i]=sorted[i]; 
76.     } 
77.     sort(sorted+1,sorted+n+1); 
78.     build(0,1,n); 
79.     int ql,qr,k; 
80.     for(int i=0;i<m;i++){ 
81.         scanf("%d %d %d",&ql,&qr,&k); 
82.         int ans=query(0,1,n,ql,qr,k); 
83.         printf("%d\n",ans); 
84.     } 
85.  
86.     return 0; 
87. }