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

题目：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 ;

}