【BZOJ】2724: [Violet 6]蒲公英

2724: [Violet 6]蒲公英

Time Limit: 40 Sec  Memory Limit: 512 MB
Submit: 2900  Solved: 1031
[Submit][Status][Discuss]

Description

Input

修正一下

l = (l_0 + x - 1) mod n + 1, r = (r_0 + x - 1) mod n + 1

Output

Sample Input

6 3
1 2 3 2 1 2
1 5
3 6
1 5

Sample Output

1
2
1

HINT

修正下：

n <= 40000, m <= 50000

Source

Vani原创

[Submit][Status][Discuss]

HOME 

写的第一道分块题...结果几乎全都是照着$hzwer$写的QAQ，tcltcl...

先离散化，维护块块之间的众数，用$vector$存每个颜色出现的每个位置，查询的时候在$vector$里面用$upper_bound$和$lower_bound$计算区间颜色数量，统计的时候，整个块答案先直接得到，块两边多余的元素暴力计算贡献，如果可以更优就更新。

主要是注意分块中的一些细节，比如块的左闭右开（每次都要改很久aaa！！！），区间范围！还有就是不要再不小心把一个变量重新定义两次叻...QAQ

#include<iostream>

#include<cstdio>

#include<vector>

#include<algorithm>

#include<cstring>

#include<cmath>

#define ll long long

using namespace std;

int n, m;

ll a[], ls[], id[], cnt[];

int blo, bl[], f[][];

vector < int > vc[];

void init ( int x ) {

    memset ( cnt, , sizeof ( cnt ) );

    int mx = , ans = ;

    for ( int i = ( x -  ) * blo + ; i <= n; i ++ ) {

        cnt[a[i]] ++;

        int t = bl[i];

        if ( cnt[a[i]] > mx || ( cnt[a[i]] == mx && id[ans] > id[a[i]] ) )

            mx = cnt[a[i]], ans = a[i];

        f[x][t] = ans;

    }

}

int query ( int l, int r, int x ) {

    int t = upper_bound ( vc[x].begin ( ), vc[x].end ( ), r ) - lower_bound ( vc[x].begin ( ), vc[x].end ( ), l );

    return t;

}

int query ( int l, int r ) {

    int ans, mx;

    ans = f[bl[l]+][bl[r]-];

    mx = query ( l, r, ans );

    for ( int i = l; i <= min ( bl[l] * blo, r ); i ++ ) {

        int t = query ( l, r, a[i] );

        if ( t > mx || ( t == mx && id[a[i]] < id[ans] ) )

            ans = a[i], mx = t;

    }

    if ( bl[l] != bl[r] )

        for ( int i = ( bl[r] -  ) * blo + ; i <= r; i ++ ) {

            int t = query ( l, r, a[i] );

            if ( t > mx || ( t == mx && id[a[i]] < id[ans] ) )

                ans = a[i], mx = t;

        }

    return ans;

}

int main ( ) {

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

    blo = sqrt ( n );

    for ( int i = ; i <= n; i ++ ) {

        scanf ( "%lld", &a[i] );

        ls[i] = a[i];

    }

    sort ( ls + , ls +  + n );

    int tot = unique ( ls + , ls +  + n ) - ls - ;

    int s = ;

    for ( int i = ; i <= n; i ++ ) {

        int qwq = lower_bound ( ls + , ls +  + tot, a[i] ) - ls;

        vc[qwq].push_back ( i );

        id[qwq] = a[i];

        a[i] = qwq;

    }

    for ( int i = ; i <= n; i ++ ) bl[i] = ( i + blo -  ) / blo;

    for ( int i = ; i <= bl[n]; i ++ )    init ( i );

    int x = ;

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

        int l0, r0;

        scanf ( "%d%d", &l0, &r0 );

        int l = ( l0 + x -  ) % n + , r = ( r0 + x -  ) % n + ;

        if ( l > r ) swap ( l, r );

        x = id[query ( l, r )];

        printf ( "%d\n", x );

    }

    return ;

}