[HDU] 5213 Lucky [블록 (온라인 알고리즘)]

전송 문: 【 HDU 】 5213 Lucky
제목 분석:
이 문제 의 온라인 방법 을 말씀 드 리 겠 습 니 다.
우선 우 리 는 구간 을 n √ 원 으로 나 누고 f [x] [y] 로 x 원 의 수 와 y 원 의 수 를 K 의 대수 와 더 하면 O (N √) 의 예비 처 리 를 할 수 있다.그 다음 에 g [x] [y] 는 1 ~ x 블록 에 있 는 크기 가 y 인 수의 개 수 를 나타 내 는데 이것 의 복잡 도 는 똑 같이 O (N √) 이다.
그 다음 에 각 조 의 문의 에 대해 우 리 는 한 구간 을 고려 합 니 다. 이 구간 안의 완전한 블록 은 최대 n √ 개 이 고 완전한 블록 을 제외 한 후에 도 n √ 개 만 분 산 된 수 입 니 다.
설정 A = 첫 번 째 구간 내 온전한 블록, B = 첫 번 째 구간 내 분 산 된 수, C = 두 번 째 구간 내 온전한 블록, D = 두 번 째 구간 내 분 산 된 수.
X ⋅ Y 로 하여 금 X 와 Y 의 공동 작용 이 답 에 기여 한 것 을 나타 내 게 하면 이번 질문 의 답 은 ans = A ⋅ C + A ⋅ D + B ⋅ C + B ⋅ D 이다.
이렇게 해서 우 리 는 온라인 처 리 를 해 냈 다.
my code：

#include <stdio.h> #include <string.h> #include <set> #include <map> #include <math.h> #include <algorithm> using namespace std ; typedef long long LL ; #define clr( a , x ) memset ( a , x , sizeof a ) #define cpy( a , x ) memcpy ( a , x , sizeof a ) const int MAXN = 30005 ; const int SQR = 300 ; int n , m , K , sqr ; int a[MAXN] ; int f[SQR][SQR] ; int g[SQR][MAXN] ; int vis[MAXN] , Time ; int cnt[MAXN] , cnt2[MAXN] ; void solve () { int l1 , l2 , r1 , r2 ; clr ( f , 0 ) ; clr ( a , 0 ) ; clr ( g , 0 ) ; sqr = sqrt ( 1.0 * n ) ; for ( int i = 1 ; i <= n ; ++ i ) scanf ( "%d" , &a[i] ) ; for ( int i = 1 , x = 1 ; i <= n ; i += sqr , ++ x ) { for ( int j = i ; j <= min ( i + sqr - 1 , n ) ; ++ j ) ++ g[x][a[j]] ; for ( int j = 1 ; j <= n ; ++ j ) g[x][j] += g[x - 1][j] ; for ( int j = 1 , y = 1 ; j <= n ; j += sqr , ++ y ) { ++ Time ; for ( int k = j ; k <= min ( j + sqr - 1 , n ) ; ++ k ) { if ( vis[a[k]] == Time ) ++ cnt[a[k]] ; else { vis[a[k]] = Time ; cnt[a[k]] = 1 ; } } for ( int k = i ; k <= min ( i + sqr - 1 , n ) ; ++ k ) { if ( K - a[k] > 0 && K - a[k] <= n && vis[K - a[k]] == Time ) { f[x][y] += cnt[K - a[k]] ; } } } for ( int y = 1 ; y < SQR ; ++ y ) f[x][y] += f[x][y - 1] ; } scanf ( "%d" , &m ) ; for ( int o = 1 ; o <= m ; ++ o ) { scanf ( "%d%d%d%d" , &l1 , &r1 , &l2 , &r2 ) ; int ans = 0 ; int L1 = ( l1 - 1 ) / sqr + 2 ; int R1 = ( r1 - 1 ) / sqr ; int L2 = ( l2 - 1 ) / sqr + 2 ; int R2 = ( r2 - 1 ) / sqr ; if ( L1 <= R1 && L2 <= R2 ) { for ( int i = L1 ; i <= R1 ; ++ i ) { ans += f[i][R2] - f[i][L2 - 1] ; } } ++ Time ; int t = min ( r2 , ( L2 - 1 ) * sqr ) ; for ( int i = l2 ; i <= t ; ++ i ) { int tt = K - a[i] ; if ( tt > 0 && tt <= n & R1 >= L1 ) ans += g[R1][tt] - g[L1 - 1][tt] ; if ( vis[a[i]] == Time ) ++ cnt2[a[i]] ; else { vis[a[i]] = Time ; cnt2[a[i]] = 1 ; } } if ( t != r2 ) { for ( int i = R2 * sqr + 1 ; i <= r2 ; ++ i ) { int tt = K - a[i] ; if ( tt > 0 && tt <= n && R1 >= L1 ) ans += g[R1][tt] - g[L1 - 1][tt] ; if ( vis[a[i]] == Time ) ++ cnt2[a[i]] ; else { vis[a[i]] = Time ; cnt2[a[i]] = 1 ; } } } t = min ( r1 , ( L1 - 1 ) * sqr ) ; for ( int i = l1 ; i <= t ; ++ i ) { int tt = K - a[i] ; if ( tt > 0 && tt <= n && R2 >= L2 ) ans += g[R2][tt] - g[L2 - 1][tt] ; if ( tt > 0 && tt <= n && vis[tt] == Time ) ans += cnt2[tt] ; } if ( t != r1 ) { for ( int i = R1 * sqr + 1 ; i <= r1 ; ++ i ) { int tt = K - a[i] ; if ( tt > 0 && tt <= n && R2 >= L2 ) ans += g[R2][tt] - g[L2 - 1][tt] ; if ( tt > 0 && tt <= n && vis[tt] == Time ) ans += cnt2[tt] ; } } printf ( "%d
" , ans ) ; } } int main () { Time = 0 ; clr ( vis , 0 ) ; while ( ~scanf ( "%d%d" , &n , &K ) ) solve () ; return 0 ; }