首页 > 代码库 > hdu--2795--又是线段树

hdu--2795--又是线段树

2024-07-30 19:23:33   222人阅读

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

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

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             else62                 update( 1 , w );63         }64     }65     return 0;66 }
View Code

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

 

today:

　　你平静地像一抹夕阳

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

 

hdu--2795--又是线段树


联系
我们