pku 2823 sliding window 线段树解题意：一组n个数，一个窗口，大小k，找出窗口中的min和max，然后移动窗口，循环操作。网上有部分说可以用双向单调队列来做，个人分析，觉得如果设计特殊数据的话，可能导致时间复杂度是n^2，而使用线段树的时间复杂度是nlog(n),这题是我做的第一个线段树！所以大概的写下解题报告；
每个节点中主要存的主要信息是当前区间的min和max，其实个人感觉线段树主要的是决定好节点中记录的信息！
如果设计了这样的数据结构基本上就可以解决了！
1
2
3
4 #include<stdio.h>
5
6 int data[1000010] ;
7
8 struct tnode
9 {
10 int left , right ;
11 int min , max ;
12 } t[1000010*4];
13
14 struct out
15 {
16 int min , max ;
17 } dataout[1000010] ;
18
19 void create( int st , int ed , int r )
20 {
21 t[r].left = st ;
22 t[r].right = ed ;
23
24 if( st == ed )
25 {
26 t[r].min = t[r].max = data[st] ;
27 return ;
28 }
29
30 int mid = (st+ed)>>1 ;
31 create( st , mid , r *2 ) ;
32 create( mid+1 , ed , r*2+1) ;
33
34 // min
35 t[r].min = t[r*2].min ;
36 if( t[r].min > t[r*2+1].min )
37 t[r].min = t[r*2+1].min ;
38
39 // max
40 t[r].max = t[r*2].max ;
41 if( t[r].max < t[r*2+1].max )
42 t[r].max = t[r*2+1].max ;
43
44 }
45
46 void search( int st ,int ed , int & min , int & max , int r = 1)
47 {
48 if( st == t[r].left && ed == t[r].right )
49 {
50 min = t[r].min ;
51 max = t[r].max ;
52 return ;
53 }
54
55 int mid = ( t[r].left + t[r].right ) >> 1 ;
56
57 if( mid >= ed )
58 {
59 search( st , ed , min , max , r * 2 ) ;
60 }
61 else if( mid < st )
62 {
63 search( st , ed , min , max , r * 2 +1 ) ;
64 }
65 else
66 {
67 int min2 , max2 ;
68 search( st , mid , min , max , r * 2 ) ;
69 search( mid+1 , ed , min2 , max2 , r *2 +1 ) ;
70
71 if( min > min2 )
72 min = min2 ;
73 if( max < max2 )
74 max = max2 ;
75
76 }
77 }
78
79 int main()
80 {
81 //freopen( "in.txt" , "r" , stdin ) ;
82 int n , k ;
83 int i ;
84 scanf( "%d%d" , &n , & k ) ;
85 for( i = 1 ; i<= n ; i++ )
86 scanf( "%d" , & data[i]);
87
88 create( 1 , n , 1 ) ;
89
90 for( i = 1 ; i <= n -k +1 ; i++ )
91 {
92 search( i , i + k -1 , dataout[i].min , dataout[i].max , 1 ) ;
93 }
94 printf( "%d" , dataout[1].min ) ;
95 for( i = 2 ; i<= n- k +1 ; i++ )
96 printf( " %d" , dataout[i].min ) ;
97 printf("\n") ;
98
99 printf("%d" , dataout[1].max ) ;
100 for( i = 2 ; i<= n-k +1 ; i++ )
101 printf(" %d" , dataout[i].max ) ;
102 printf("\n") ;
103 return 0 ;
104 }