注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

GreenCloudS

 
 
 

日志

 
 

BZOJ-2752: [HAOI2012]高速公路(road)(线段树)  

2014-05-14 20:06:00|  分类: oi,bzoj,数据结构 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

题目:http://www.lydsy.com/JudgeOnline/problem.php?id=2752

 

被某位大神吐槽题解太简洁了,这次就来难得的写详细一次吧:

首先一共有C(r-l+1,2)中情况,然后求每种情况的总和明显不好直接求,那么对于每一个d(i)分开统计贡献(d(i)表示第i个和第i+1个之间的距离),那么总和就是sigma( ( i - l + 1 ) * ( r - i ) * d( i ) ) ( l <= i < r ) ,然后拆一下,就成了- sigma( i^2 d[ i ] ) + ( r + l - 1 ) sigma( i d[ i ] ) - ( l - 1 ) r sigma( d[ i ] ) ,于是乎用线段树维护sigma( i^2 d[ i ] ) , sigma( i d[ i ] ) , sigma( d[ i ] )即可。

 

代码:

  • #include <cstdio>

  • #include <algorithm>

  • #include <cstring>

  •   

  • using namespace std ;

  •   

  • #define rep( i , x ) for ( int i = 0 ; i ++ < x ; )

  • #define right( t ) ( left( t ) ^ 1 )

  • #define left( t ) ( t << 1 )

  • #define L( t ) sgt[ t ].l

  • #define R( t ) sgt[ t ].r

  • #define D( t ) sgt[ t ].delta

  • #define I( t ) sum[ t ]

  • #define sum( t ) sum[ t ].sum

  • #define isum( t ) sum[ t ].isum

  • #define iisum( t ) sum[ t ].iisum 

  •   

  • const int maxn = 100100 ;

  • const int maxv = maxn << 2 ; 

  •   

  • typedef long long ll ;

  •   

  • struct itype {

  •     ll sum , isum , iisum ;

  •     itype(  ) {

  •         sum = isum = iisum = 0 ; 

  •     }

  • } sum[ maxv ] ;

  •   

  • itype operator + ( const itype &x , const itype &y ) {

  •     itype rec ;

  •     rec.sum = x.sum + y.sum ;

  •     rec.isum = x.isum + y.isum ;

  •     rec.iisum = x.iisum + y.iisum ;

  •     return rec ;

  • }

  •   

  • struct node {

  •     int l , r , delta ;

  •     node(  ) {

  •         delta = 0 ; 

  •     }

  • } sgt[ maxv ] ;

  •   

  • void build( int l , int r , int t ) {

  •     L( t ) = l , R( t ) = r ;

  •     if ( l == r ) return ; 

  •     int mid = ( l + r ) >> 1 ; 

  •     build( l , mid , left( t ) ) , build( mid + 1 , r , right( t ) ) ;

  • }

  •   

  • ll ipre[ maxn ] , iipre[ maxn ] ;

  •   

  • void pushdown( int t ) {

  •     if ( t && D( t ) ) {

  •         sum( t ) += ll( D( t ) ) * ll( R( t ) - L( t ) + 1 ) ;

  •         isum( t ) += ll( D( t ) ) * ( ipre[ R( t ) ] - ipre[ L( t ) - 1 ] ) ;

  •         iisum( t ) += ll( D( t ) ) * ( iipre[ R( t ) ] - iipre[ L( t ) - 1 ] ) ;

  •         if ( L( t ) < R( t ) ) {

  •             D( left( t ) ) += D( t ) , D( right( t ) ) += D( t ) ;

  •         }

  •         D( t ) = 0 ; 

  •     }

  • }

  •   

  • void update( int t ) {

  •     pushdown( left( t ) ) , pushdown( right( t ) ) ;

  •     I( t ) = I( left( t ) ) + I( right( t ) ) ;

  • }

  •   

  • void change( int l , int r , int d , int t ) {

  •     pushdown( t ) ;

  •     if ( l == L( t ) && r == R( t ) ) {

  •         D( t ) += d ;

  •         pushdown( t ) ;

  •         return ;

  •     }

  •     int mid = ( L( t ) + R( t ) ) >> 1 ; 

  •     if ( r <= mid ) change( l , r , d , left( t ) ) ; else 

  •     if ( l > mid ) change( l , r , d , right( t ) ) ; else 

  •     change( l , mid , d , left( t ) ) , change( mid + 1 , r , d , right( t ) ) ;

  •     update( t ) ;

  • }

  •   

  • itype query( int l , int r , int t ) {

  •     pushdown( t ) ;

  •     if ( l == L( t ) && r == R( t ) ) return I( t ) ;

  •     int mid = ( L( t ) + R( t ) ) >> 1 ; 

  •     if ( r <= mid ) return query( l , r , left( t ) ) ; else 

  •     if ( l > mid ) return query( l , r , right( t ) ) ; else 

  •     return query( l , mid , left( t ) ) + query( mid + 1 , r , right( t ) ) ;

  • }

  •   

  • int n , m ; 

  • char s[ 5 ] ;

  •   

  • ll gcd( ll x , ll y ) {

  •     if ( x < y ) swap( x , y ) ;

  •     for ( ll k ; y ; k = y , y = x % y , x = k ) ;

  •     return x ;

  • }

  •   

  • int main(  ) {

  •     scanf( "%d%d" , &n , &m ) ;

  •     ipre[ 0 ] = iipre[ 0 ] = 0 ; 

  •     rep( i , n ) {

  •         ipre[ i ] = ipre[ i - 1 ] + ll( i ) ;

  •         iipre[ i ] = iipre[ i - 1 ] + ll( i ) * ll( i ) ;

  •     }

  •     build( 1 , n - 1 , 1 ) ;

  •     while ( m -- ) {

  •         scanf( "%s" , s ) ;

  •         if ( s[ 0 ] == 'C' ) {

  •             int l , r , d ; scanf( "%d%d%d" , &l , &r , &d ) ;

  •             change( l , r - 1 , d , 1 ) ;

  •         } else {

  •             int l , r ; scanf( "%d%d" , &l , &r ) ;

  •             itype temp = query( l , r - 1 , 1 ) ;

  •             ll x = - temp.iisum + ll( r + l - 1 ) * temp.isum - ll( l - 1 ) * ll( r ) * temp.sum ;

  •             ll y = ll( r - l + 1 ) * ll( r - l ) / ll( 2 ) ;

  •             ll g = gcd( x , y ) ;

  •             printf( "%lld/%lld\n" , x / g , y / g ) ;

  •         }

  •     }

  •     return 0 ; 

  • }

 

  评论这张
 
阅读(2)| 评论(4)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017