hdu--2795--又是线段树

应该就是算线段树的单点更新吧.

但一开始给了我一个错觉是二维线段树我也是醉了

tree[root].x// x = L || R表示root这个结点表示的是L - > R这个区间

tree[root].leftLen//表示 root这个结点所在的区间现在还存在的最长连续格子数

更让人郁闷的是我用cin cout写即使写上了cin.sync_with_stdio(false)还是TLE。。。

我也是无语了以前在Hdu上都是有效的啊...

然后我改成scanf printf就过了...

 1 #include <iostream>
 2 #include <algorithm>
 3 using namespace std;
 4 
 5 const int size = 200010;
 6 struct data
 7 {
 8     int L;
 9     int R;
10     int leftLen;
11 }tree[size*4]; 
12 
13 void build( int root , int L , int R , int w )
14 {
15     int Mid = ( R + L ) >> 1;
16     tree[root].L = L;
17     tree[root].R = R;
18     tree[root].leftLen = w;
19     if( L==R )
20     {
21         return ;
22     }
23     build( root<<1 , L , Mid , w );
24     build( root<<1|1 , Mid+1 , R , w );
25 }
26 
27 void pushUp( int root )
28 {
29     tree[root].leftLen = max( tree[root<<1].leftLen , tree[root<<1|1].leftLen );    
30 }
31 
32 void update( int root , int w )
33 {
34     int ans;
35     if( tree[root].L == tree[root].R )
36     {
37         tree[root].leftLen -= w;
38          cout << tree[root].L << endl;
39          return ;
40     }    
41     if( tree[root<<1].leftLen >= w )
42          update( root<<1 , w );
43     else if( tree[root<<1|1].leftLen >= w )
44          update( root<<1|1 , w );
45      pushUp( root );
46 }
47     
48 int main()
49 {
50     cin.sync_with_stdio(false);
51     int h , w , n;
52     while( cin >> h >> w >> n )
53     {
54         h = min( h , n );
55         build( 1 , 1 , h , w );
56         while( n-- )
57         {
58             cin >> w;
59             if( tree[1].leftLen < w )
60                 cout << -1 << endl;
61             else
62                 update( 1 , w );
63         }
64     }
65     return 0;
66 }

View Code

我这边就还是贴 tle的代码了还是比较喜欢cin cout的风格 =_=

today:

　　你平静地像一抹夕阳

　　他们都忘了你朝阳时的模样

just follow your heart