题解 | 算法竞赛进阶指南 小Z的袜子

思路

莫队基础题.
对于每个区间,设颜色的出现次数为,答案就是,分子的意义是任意选两只袜子,颜色相同的对数(可重复选,与顺序有关)减去重复选同一只的情况.
莫队维护.
加入一个数,减去加入前该数出现次数的平方,加上加入后该数出现次数的平方,删去一个数则恰恰相反.
因为是以前写的代码,计算时分子分母先除了个2(表示与顺序无关),事实上是不用的.

代码

#include<bits/stdc++.h>
using namespace std;
#define open(s) freopen( s".in", "r", stdin ), freopen( s".out", "w", stdout )
#define MAXN 50005
#define LL long long

LL N, M;
LL C[MAXN];
LL s[MAXN];

LL gcd( LL x, LL y ){
    if ( y == 0 ) return x;
    return gcd( y, x % y );
}

struct ppp{
    LL l, r, id, ans;
    void print(){
        if ( l == r || ans <= 0 ){ printf( "0/1\n" ); return; }
        LL x(ans), y( ( ( r - l + 1 ) * ( r - l ) ) >> 1 ), t; t = gcd( y, x );
        x /= t; y /= t; printf( "%lld/%lld\n", x, y );
    }
}q[MAXN];

LL B(222);
inline LL GetBlock( LL x ){ return ( x - 1 ) / B; }

bool cp( ppp x, ppp y ){
    if ( GetBlock( x.l ) == GetBlock( y.l ) ) return x.r < y.r;
    return GetBlock( x.l ) < GetBlock( y.l );
}
bool cmp( ppp x, ppp y ){ return x.id < y.id; }

int main(){
    scanf( "%lld%lld", &N, &M );
    for ( LL i = 1; i <= N; ++i ) scanf( "%lld", &C[i] );
    for ( LL i = 1; i <= M; ++i ) scanf( "%lld%lld", &q[i].l, &q[i].r ), q[i].id = i;
    sort( q + 1, q + M + 1, cp );

    int l(1), r(1); s[C[1]]++;
    LL c(1);
    for ( LL i = 1; i <= M; ++i ){
        if ( q[i].l == q[i].r ) continue;
        while( r < q[i].r ) r++, c = c - s[C[r]] * s[C[r]] + ( s[C[r]] + 1 ) * ( s[C[r]] + 1 ), s[C[r]]++;
        while( r > q[i].r ) c = c - s[C[r]] * s[C[r]] + ( s[C[r]] - 1 ) * ( s[C[r]] - 1 ), s[C[r]]--, r--;
        while( l < q[i].l ) c = c - s[C[l]] * s[C[l]] + ( s[C[l]] - 1 ) * ( s[C[l]] - 1 ), s[C[l]]--, l++;
        while( l > q[i].l ) l--, c = c - s[C[l]] * s[C[l]] + ( s[C[l]] + 1 ) * ( s[C[l]] + 1 ), s[C[l]]++;
        q[i].ans = ( c - q[i].r + q[i].l - 1 ) >> 1;
    }

    sort( q + 1, q + M + 1, cmp );

    for ( int i = 1; i <= M; ++i ) q[i].print();
    return 0;
}