Mobius_LCA @ 2023-10-17 18:41:12
这里是代码:
#include <bits/stdc++.h>
using namespace std ;
const int N = 40010 , T = 35 ;
int n , m , a[N] , L , R ;
int ssum , sum , len ; //ssum 离散化 , sum 端点个数(原来)
int c[N] , b[N] , rb[N] , rsum ;
int cnt[80][80][N] , mm[80][80] , kin[80][80] , d[N] ;
int rec[N] ;
int Query(int l , int r ) {
int x1 = lower_bound(rb +1 , rb + rsum + 1 , l ) - rb ,
x2 = upper_bound(rb + 1 , rb + rsum + 1 , r) - rb - 1 ;
L = rb[x1] , R = rb[x2] ;
// cout << "x1:" << x1 << endl ;
// cout << L << ' ' << R << endl ;
if(L >= R) { //brufe
int nm = 0 , rkin = 0 ;
for ( int i = l ; i <= r ; ++i ) {
int rf = lower_bound(d + 1 , d + ssum + 1, a[i]) - d ;
rec[rf] ++ ;
if(nm < rec[rf]) nm = rec[rf] , rkin = a[i] ;
else if(nm == rec[rf]) {
if(rkin == 0 || rkin > a[i]) rkin = a[i] ;
}
// cout << "nm : " << nm << endl ;
// cout << "rkin:" << rkin << endl ;
}
for ( int i = l ; i <= r ; ++i ) {
int rf = lower_bound(d + 1 , d + ssum + 1, a[i]) - d ;
rec[rf] -- ;
}
return rkin ;
}
// cout << "LR" << ' ' << L << ' ' << R << endl ;
int ma1 = mm[x1][x2] , nm = 0 , k1 = kin[x1][x2] ;
// cout <<"k1" <<' ' << k1 << endl ;
// cout << "ma1:" << ma1 << endl ;
int rkin = 0 ;
for (int i = l ; i < L ; ++ i ) {
int rf = lower_bound(d + 1 , d + ssum + 1 , a[i]) - d ;
// cout << rf << endl ;
cnt[x1][x2][rf] ++ ;
// cout << cnt[x1][x2][rf] << endl ;
if(nm < cnt[x1][x2][rf]) cnt[x1][x2][rf] , rkin = a[i] ;
else if(nm == cnt[x1][x2][rf] ) {
if(rkin == 0 || rkin > a[i]) rkin = a[i] ;
}
}
for (int i = R + 1 ; i <= r ; ++ i ) {
int rf = lower_bound(d + 1 , d + ssum + 1 , a[i]) - d ;
cnt[x1][x2][rf] ++ ;
if(nm < cnt[x1][x2][rf]) cnt[x1][x2][rf] , rkin = a[i] ;
else if(nm == cnt[x1][x2][rf] ) {
if(rkin == 0 || rkin > a[i]) rkin = a[i] ;
}
}
int fim = max(ma1 , nm ) ;
for (int i = l ; i < L ; ++ i ) {
int rf = lower_bound(d + 1 , d + ssum + 1 , a[i]) - d ;
cnt[x1][x2][rf]-- ;
}
for (int i = R + 1 ; i <= r ; ++ i ) {
int rf = lower_bound(d + 1 , d + ssum + 1 , a[i]) - d ;
cnt[x1][x2][rf]-- ;
}
if(ma1 == nm ) {
return min(k1 , rkin) ;
}
if(fim == ma1) return k1 ;
else return rkin ;
}
int main() {
freopen("P4168_1.in","r",stdin);
freopen("P4168_1.ans","w",stdout) ;
cin >> n >> m ; len = n / T ;
for ( int i = 1 ; i <= n ; ++i ) cin >>a[i] , c[i] = a[i] ;
sort(c + 1, c + n + 1) ;
for ( int i = 1 ; i <= n ; ++i )
if( i == 1 || c[i] != c[i - 1] ) d[++ssum] = c[i] ;
for ( int i = 1 ; i <= T ; ++i )
b[++sum] = (i - 1) * len + 1 , b[++sum] = i * len ;
if( b[sum] < n ) {
sum++ , b[sum] = b[sum - 1] + 1 ;
sum++ , b[sum] = n ;
}
sort(b + 1 , b + sum + 1) ;
for ( int i = 1 ; i <= sum ; ++i )
if(i == 1 || b[i] != b[i - 1] ) rb[++rsum] = b[i] ;
// for ( int i = 1 ; i <= rsum ; ++i ) {
// cout << "rb" << i << ":" << rb[i] << endl ;
// }
for ( int i = 1 ; i <= rsum ; ++i )
for (int j = i ; j <= rsum ; ++j ) {
int lmax = 0 , lkind = 0 ;
for( int k = rb[i] ; k <= rb[j] ; ++k ) {
int rf = lower_bound(d + 1 , d + ssum + 1 , a[k]) - d ;
cnt[i][j][rf] ++ ;
if(lmax < cnt[i][j][rf]) lmax = cnt[i][j][rf] , lkind = a[k] ;
else if(lmax == cnt[i][j][rf] ) {
if(lkind == 0 || lkind > a[k]) lkind = a[k] ;
}
}
mm[i][j] = lmax , kin[i][j] = lkind ;
}
int lq = 0 , l0 , r0 ;
for( int i = 1 ; i <= m ; ++i ) {
cin >> l0 >> r0 ;
int l = (l0 + lq - 1) % n + 1 ;
int r = (r0 + lq - 1 ) % n + 1 ;
// int l = l0 , r = r0 ;
if( l > r) swap( l , r) ;
// cout << "lr:" << l << ' ' << r << endl ;
int res = Query( l , r ) ;
cout << res << endl ;
lq = res ;
}
return 0 ;
}
目前调了 20 多次 , 一直 WA 0 pts,大样例第一个对了一些,真的找不出来问题了,救救孩子【哭】
by Mobius_LCA @ 2023-10-17 18:42:41
P.S. 这个做法是 lyd 书上的第一个做法