In mathematics you don't understand things, you just get used to them.

Description

Link.

区间众数出现次数强制在线。

Solution

三个 YLST 中比较清新的一个分块。

比较重点的地方在于询问散块的处理。

先离散化一下序列。

我们首先预处理出来一个 vector 数组 fur[i]fur[i] 里面依次存的是所有 isa[i](即这个序列,详见代码)的出现位置,再预处理一个 pos[i] 表示在当前第 $i$ 位时 fur[i] 的大小也就是一共出现了多少个 isa[i]。由于 vector 的下标是从 $0$ 开始的,所以所有的 pos[i] 都需要减个一。

然后询问处理整块的时候,我们先假设当前询问的区间是 [opl,opr],然后把当前询问的答案 res 先置为 App[bel[opl] + 1][bel[opr] - 1]

然后来考虑散块,在处理出的 vector 数组中判断即可。

设散块处理到数 isa[i],那么如果存在 pos[i] + res <= fur[isa[i]].size() - 1fur[isa[i]][pos[i] + res] <= opr,那么则说明这个数出现了至少 res + 1 次,将 res 加一即可。

由于 res 最多加不超过 $\Theta(2\sqrt{n})$ 次,所以复杂度是对的。

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>

using namespace std;

const int MAXN = 5e5 + 5, MAXM = 720 + 5;

char buf[1 << 21], *p1 = buf, *p2 = buf;
#define getchar( ) ( p1 == p2 && ( p2 = ( p1 = buf ) + fread( buf, 1, 1 << 21, stdin ), p1 == p2 ) ? EOF : *p1 ++ )

template<typename _T>
void read( _T &x ){
    x = 0; char c = getchar( ); _T f = 1;
    while( c < '0' || c > '9' ){ if( c == '-' )    f = -1; c = getchar( ); }
    while( c >= '0' && c <= '9' ){ x = ( x << 3 ) + ( x << 1 ) + ( c & 15 ); c = getchar( ); }
    x *= f;
}

template<typename _T>
void write( _T x ){
    if( x < 0 ){ putchar( '-' ); x = -x; }
    if( x > 9 ){ write( x / 10 ); }
    putchar( x % 10 + '0' );
}

template<typename _T>
void swapp( _T &one, _T &another ){ int temp = one; one = another; another = temp; }

template<typename _T>
_T MIN( _T one, _T another ){ return one > another ? another : one; }

template<typename _T>
_T MAX( _T one, _T another ){ return one > another ? one : another; }

int N, M;
int cube, each, kase, isa[MAXN], cnt[MAXN], pos[MAXN], vis[MAXN], bel[MAXN];
int lps[MAXM], rps[MAXM], app[MAXM], App[MAXM][MAXM];
vector<int> disc, fur[MAXN];

int getID( int x ){ return lower_bound( disc.begin( ), disc.end( ), x ) - disc.begin( ) + 1; }

void build( ){
    for( int i = 1; i <= cube; ++ i ){
        kase ++;
        for( int j = lps[i]; j <= rps[i]; ++ j ){
            if( vis[isa[j]] != kase )    cnt[isa[j]] = 0;
            cnt[isa[j]] ++; app[i] = MAX( app[i], cnt[isa[j]] );
            vis[isa[j]] = kase;
        }
    }
    memset( cnt, 0, sizeof( cnt ) );
    for( int i = 1; i <= cube; ++ i ){
        kase ++;
        for( int j = i; j <= cube; ++ j ){
            App[i][j] = App[i][j - 1];
            for( int k = lps[j]; k <= rps[j]; ++ k ){
                if( vis[isa[k]] != kase )    cnt[isa[k]] = 0;
                cnt[isa[k]] ++; App[i][j] = MAX( App[i][j], cnt[isa[k]] );
                vis[isa[k]] = kase;
            }
        }
    }
    memset( cnt, 0, sizeof( cnt ) );
}

int query( int opl, int opr ){
    if( bel[opl] == bel[opr] ){
        int res = 0; kase ++;
        for( int i = opl; i <= opr; ++ i ){
            if( vis[isa[i]] != kase )    cnt[isa[i]] = 0;
            cnt[isa[i]] ++; res = MAX( res, cnt[isa[i]] );
            vis[isa[i]] = kase;
        }
        return res;
    }
    int res = 0;
//    res = App[bel[opl] + 1][bel[opr] - 1];
    for( int i = bel[opl] + 1; i < bel[opr]; ++ i )    res += app[i];
//    for( int i = bel[opl] + 1; i < bel[opr]; ++ i )    res += App[i][i];
    for( int i = opl; i <= rps[bel[opl]]; ++ i ){
        int lim = fur[isa[i]].size( ) - 1;
        while( pos[i] + res <= lim && fur[isa[i]][pos[i] + res] <= opr )    res ++;
    }
    for( int i = lps[bel[opr]]; i <= opr; ++ i ){
        while( pos[i] - res >= 0 && fur[isa[i]][pos[i] - res] >= opl )    res ++;
    }
    return res;
}

signed main( ){
    read( N ); read( M ); each = 720; cube = ( N - 1 ) / each + 1;
    for( int i = 1; i <= N; ++ i ){ read( isa[i] ); disc.push_back( isa[i] ); }
    sort( disc.begin( ), disc.end( ) );
    disc.erase( unique( disc.begin( ), disc.end( ) ), disc.end( ) );
    for( int i = 1; i <= N; ++ i ){
        isa[i] = getID( isa[i] );
        fur[isa[i]].push_back( i );
        pos[i] = fur[isa[i]].size( ) - 1;
    }
    for( int i = 1; i <= cube; ++ i ){
        lps[i] = rps[i - 1] + 1; rps[i] = rps[i - 1] + each;
        if( i == cube )    rps[i] = N;
        for( int j = lps[i]; j <= rps[i]; ++ j )    bel[j] = i;
    }
    build( );
    int Ans = 0, opl, opr;
    while( M -- > 0 ){
        read( opl ); read( opr ); opl ^= Ans; opr ^= Ans;
        Ans = 0; if( opl > opr )    swapp( opl, opr );
        write( Ans = query( opl, opr ) ); putchar( '\n' );
    }
    return 0;
}

data structures brute force

Note -「普通生成函数 OGF」
上一篇 «
Solution -「洛谷 P5355」「YunoOI 2017」由乃的玉米田
» 下一篇