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

GreenCloudS

 
 
 

日志

 
 

2038: [2009国家集训队]小Z的袜子(hose)(莫队)  

2014-02-24 21:46:00|  分类: oi,bzoj,数据结构 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

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


作为一个GDKOI被虐了之后才滚过来学莫队的蒟蒻,我就不想吐槽自己什么了,明明可以早一天看就可以多水40分的说。。。

莫队其实听好写的,对l分块,然后按r排序,然后直接转移即可,这样的复杂度明显是O(n^(3/2))。


代码:

  • #include <cstdio>

  • #include <algorithm>

  • #include <cstring>

  • #include <cmath>

  •  

  • using namespace std ;

  •  

  • #define ll long long

  • #define MAXN 50010

  • #define MAXM 50010

  •  

  • ll gcd( ll x , ll y ) {

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

  •     while ( y ) {

  •         ll k = y ;

  •         y = x % y ;

  •         x = k ;

  •     }

  •     return x ;

  • }

  •  

  • int n , N ;

  •  

  • struct query {

  •     int l , r , t ;

  •     bool operator < ( const query &a ) const {

  •         return ( l / N ) < ( a.l / N ) || ( ( l / N ) == ( a.l / N ) && r < a.r ) ;

  •     }

  • } q[ MAXM ] ;

  •  

  • ll Ans[ MAXM ][ 2 ] ;

  •  

  • int m , c[ MAXN ] , cnt[ MAXN ] ;

  •  

  • int main(  ) {

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

  •     N = int( sqrt( n ) ) ;

  •     for ( int i = 0 ; i ++ < n ; ) scanf( "%d" , c + i ) ;

  •     for ( int i = 0 ; i ++ < m ; ) {

  •         scanf( "%d%d" , &q[ i ].l , &q[ i ].r ) ;

  •         q[ i ].t = i ;

  •     }

  •     sort( q + 1 , q + m + 1 ) ;

  •     ll rec ;

  •     for ( int i = 0 , l , r ; i ++ < m ; ) {

  •         if ( i == 1 || q[ i ].l / N != q[ i - 1 ].l / N ) {

  •             for ( int j = 0 ; j <= n ; ++ j ) cnt[ j ] = 0 ;

  •             l = q[ i ].l , r = q[ i ].r ;

  •             for ( int j = l ; j <= r ; ++ j ) ++ cnt[ c[ j ] ] ;

  •             rec = 0 ;

  •             for ( int j = 0 ; j <= n ; ++ j ) {

  •                 rec += ( ll )( cnt[ j ] ) * ( ll )( cnt[ j ] - 1 ) ;

  •             }

  •         }

  •         for ( ; r < q[ i ].r ; ++ r ) {

  •             int s = c[ r + 1 ] ;

  •             rec -= ( ll )( cnt[ s ] ) * ( ll )( cnt[ s ] - 1 ) ;

  •             ++ cnt[ s ] ;

  •             rec += ( ll )( cnt[ s ] ) * ( ll )( cnt[ s ] - 1 ) ;

  •         }

  •         for ( ; l < q[ i ].l ; ++ l ) {

  •             int s = c[ l ] ;

  •             rec -= ( ll )( cnt[ s ] ) * ( ll )( cnt[ s ] - 1 ) ;

  •             -- cnt[ s ] ;

  •             rec += ( ll )( cnt[ s ] ) * ( ll )( cnt[ s ] - 1 ) ;

  •         }

  •         for ( ; l > q[ i ].l ; -- l ) {

  •             int s = c[ l - 1 ] ;

  •             rec -= ( ll )( cnt[ s ] ) * ( ll )( cnt[ s ] - 1 ) ;

  •             ++ cnt[ s ] ;

  •             rec += ( ll )( cnt[ s ] ) * ( ll )( cnt[ s ] - 1 ) ;

  •         }

  •         if ( rec ) {

  •             ll ret = gcd( rec , ( ll )( r - l + 1 ) * ( ll )( r - l ) ) ;

  •             Ans[ q[ i ].t ][ 0 ] = rec / ret , Ans[ q[ i ].t ][ 1 ] = ( ( ll )( r - l + 1 ) * ( ll )( r - l ) ) / ret ;

  •         } else Ans[ q[ i ].t ][ 0 ] = 0 , Ans[ q[ i ].t ][ 1 ] = 1 ;

  •     }

  •     for ( int i = 0 ; i ++ < m ; ) printf( "%lld/%lld\n" , Ans[ i ][ 0 ] , Ans[ i ][ 1 ] ) ;

  •     return 0 ;

  • }


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

历史上的今天

评论

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

页脚

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