题解 | 作诗题解

和蒲公英差不多的套路，预处理整块的答案，查询的时候分类讨论，如果一个数在整段中是偶数次，在中间的整块是奇数次那么，在整段是奇数次在中间的整块是偶数次就。效率是。必须O2+优秀的块的大小才可以卡过去。注意不要用memset，每次处理过后for一遍清空就好，memset是对整个数组清空.

#include <bits/stdc++.h>

#define ll long long
#define inf 0x3f3f3f3f 
#define il inline 

namespace io {

    #define debug_ puts("debuging ... ") ;
    #define in(a) a=read()
    #define out(a) write(a)
    #define outn(a) out(a),putchar('\n')

    #define I_int int 
    inline I_int read() {
        I_int x = 0 , f = 1 ; char c = getchar() ;
        while( c < '0' || c > '9' ) { if( c == '-' ) f = -1 ; c = getchar() ; } 
        while( c >= '0' && c <= '9' ) { x = x * 10 + c - '0' ; c = getchar() ; } 
        return x * f ;
    } 
    char F[ 200 ] ;
    inline void write( I_int x ) {
        I_int tmp = x > 0 ? x : -x ;
        if( x == 0 ) putchar( '0' ) ;
        if( x < 0 ) putchar( '-' ) ;
        int cnt = 0 ;
        while( tmp > 0 ) {
            F[ cnt ++ ] = tmp % 10 + '0' ;
            tmp /= 10 ;
        }
        while( cnt > 0 ) putchar( F[ -- cnt ] ) ;
    }
    #undef I_int

}
using namespace io ;

using namespace std ;

#define N 100010

vector < int > vt[ N ] ;
int n = read() , c = read() , m = read() ;
int L[ N ] , R[ N ] , bl[ N ] , cnt[ 1510 ][ 1510 ] ;
int block , num , tot[ N ] , a[ N ] ;

void pre( int x ) {
    int ans = 0 ;
    for( int i = L[ x ] ; i <= n ; i ++ ) {
        int t = bl[ i ] ;        
        tot[ a[ i ] ] ++ ;
        if( tot[ a[ i ] ] % 2 == 0 && tot[ a[ i ] ] ) ans ++ ;
        if( tot[ a[ i ] ] % 2 && tot[ a[ i ] ] > 1 ) ans -- ; 
        cnt[ x ][ t ] = ans ;
    }
    for( int i = L[ x ] ; i <= n ; i ++ ) tot[ a[ i ] ] = 0 ;
}

void build() { 
    block = sqrt((double)n/log((double)n)*log(2)) ; 
    num = n / block ; 
    if( n % block ) num ++ ;
    for( int i = 1 ; i <= num ; i ++ ) {
        L[ i ] = (i - 1) * block + 1 ;
        R[ i ] = i * block ;
    } 
    for( int i = 1 ; i <= n ; i ++ ) 
        bl[ i ] = (i - 1) / block + 1 ;
    for( int i = 1 ; i <= num ; i ++ ) pre( i ) ; 
}

int serach_ans( int l , int r , int x ) {
    int t = upper_bound( vt[ x ].begin() , vt[ x ].end() , r ) - lower_bound( vt[ x ].begin() , vt[ x ].end() , l ) ;
    return t ; 
}

int query( int x , int y ) {
    int ans = 0 ;
    if( bl[ x ] == bl[ y ] ) {
        for( int i = x ; i <= y ; i ++ ) {
            if( tot[ a[ i ] ] ) continue ;
            tot[ a[ i ] ] = 1 ;
            int t = serach_ans( x , y , a[ i ] ) ;
            if( t % 2 == 0 && t ) ans ++ ; 
        }
        for( int i = x ; i <= y ; i ++ ) tot[ a[ i ] ] = 0 ;
        return ans ;
    }
    int l = L[ bl[ x ] + 1 ] , r = R[ bl[ y ] - 1 ] ; 
    ans = cnt[ bl[ x ] + 1 ][ bl[ y ] - 1 ] ;
    for( int i = x ; i <= R[ bl[ x ] ] ; i ++ ) {
        if( tot[ a[ i ] ] ) continue ;
        tot[ a[ i ] ] = 1 ;
        int t2 = serach_ans( l , r , a[ i ] ) , t1 = serach_ans( x , y , a[ i ] ) ;
        if( t1 % 2 == 0 ) {
            if( t2 % 2 || !t2 ) ans ++ ;
        } else if( t2 % 2 == 0 && t2 ) ans -- ;
    }
    for( int i = L[ bl[ y ] ] ; i <= y ; i ++ ) {
        if( tot[ a[ i ] ] ) continue ;
        tot[ a[ i ] ] = 1 ;
        int t2 = serach_ans( l , r , a[ i ] ) , t1 = serach_ans( x , y , a[ i ] ) ;
        if( t1 % 2 == 0 ) {
            if( t2 % 2 || !t2 ) ans ++ ;
        } else if( t2 % 2 == 0 && t2 ) ans -- ;
    }
    for( int i = x ; i <= R[ bl[ x ] ] ; i ++ ) tot[ a[ i ] ] = 0 ;
    for( int i = L[ bl[ y ] ] ; i <= y ; i ++ ) tot[ a[ i ] ] = 0 ;
    return ans ;
} 

int main() {
    int ans = 0 ;
    for( int i = 1 ; i <= n ; i ++ ) {
        a[ i ] = read() ;
        vt[ a[ i ] ].push_back( i ) ;
    }
    build() ;
    for( int i = 1 ; i <= m ; i ++ ) {
        int l = read() , r = read() ;
        l = (l + ans) % n + 1 , r = (r + ans) % n + 1 ;
        if( l > r ) swap( l , r ) ;
        outn( ans = query( l , r ) ) ; 
    } 
    return 0 ; 
}