구간 중수
블록 배열 은 배열 을 몇 개의 블록 으로 나 누 는 것 (일반적으로 sqrt (n) 으로 복잡 도 를 최소 화 하 는 것) 입 니 다. i ~ j 블록 의 답 (복잡 도 는 n * sqrt (n) 내 에서 보장 할 수 있 습 니 다) 을 미리 처리 하 는 것 입 니 다.
답 을 구 할 때 는 예비 처 리 된 답 과 폭력 에 따라 수미 의 나머지 개 수 를 매 거 하여 최종 답 을 얻 고, 수미 의 나머지 개 수 는 2 * sqrt (n) 를 초과 하지 않 는 다. 이러한 전체적인 복잡 도 는
(n + q) sqrt (n), q 를 조회 하 는 횟수 입 니 다.
구간 중수
1. 제목 설명
n 개 수 x, 조회 q 회, [L, R] 구간 의 중수 개수 (그 중 n, q < = 20000, 0 < = L < = R
대부분의 일반적인 중수 문 제 는 폭력 구간 에서 답 을 구 할 수 있 지만 데이터 가 너무 커서 폭력 을 행사 할 수 없다. 우 리 는 덩어리 수 조 를 이용 하여 이런 문제 (복잡 도 n * sqrt (n) 를 해결 해 야 한다.
문 제 를 더욱 일반적인 가설 로 하기 위해 서 각 수 0 < = x
먼저 i ~ j 블록의 개수 개 수 를 미리 처리 합 니 다. i ~ j - 1 의 개수 개 수 를 구하 면 지금 i ~ j 의 개수 개 수 를 요구 합 니 다. 간단 하지 않 습 니까? 개수 개 수 는 i ~ j - 1 의 개수 이거 나 j 블록의 숫자 가 나 오 는 횟수 입 니 다. 그러면 j 블록의 숫자 를 매 거 할 수 있 습 니 다. 만약 에 우리 가 앞의 i 블록의 숫자 j 가 나 오 는 횟수 (sum [i] [j] 로 정의 합 니 다) 를 미리 처리 하면그러면 j 블록 에 나타 난 숫자 a [p] (그 중에서 p 는 j 블록 에 있 음) 가 i ~ j 블록 에 나타 난 횟수 는 sum [j] [a [p] - sum [i - 1] [a [p] 입 니 다. 그리고 sum 숫자의 예비 처 리 는 간단 합 니 다.
예 처리 가 끝 난 후에 바로 조회 문제 입 니 다. 조 회 는 사실 예 처리 의 원리 와 같 습 니 다. 만약 에 L 이 x 블록 에 속 하고 R 이 y 블록 에 속한다 고 가정 하면 이 구간 의 중수 개 수 는 x + 1 ~ y - 1 블록의 중수 개수 이거 나 L ~ x 블록 종료 에서 숫자 가 나타 난 횟수 이거 나 Y 블록 시작 ~ R 에서 숫자 가 나타 난 횟수 입 니 다. x + 1 ~ y - 1 블록의 중수 개수 가 처리 되 었 기 때문에그러면 O (1) 만 있 으 면 알 수 있 습 니 다. 다른 두 조각 은 개 수 를 직접 폭력 적 으로 통계 할 수 있 습 니 다. (여기 서 주의해 야 합 니 다. 이 두 조각 에 나타 난 숫자 만 초기 화 하면 복잡 도 는 sqrt (n) 뿐 이 고 초기 값 은 sum [y - 1] [p] - sum [x] [p], p 는 블록 에 나타 난 숫자 입 니 다)또 L 과 R 이 같은 곳 에 있 는 경우 에 주의 하면 구간 중수 문제 가 해결 된다.
#include
using namespace std;
const int maxn = 50005, N = 305;
int sum[N][maxn], a[maxn], mul[N][N], cc[N][N];
int tmp[maxn];
//sum[i][j] i j
//mul[i][j]
//cc[i][j]
void solve ( )
{
int n, Q;
//freopen ( "in0.in", "r", stdin );
//freopen ( "in1.out", "w", stdout );
scanf ( "%d%d", &n, &Q );
for ( int i = 0; i < n; i ++ )
scanf ( "%d", &a[i] );
int blo = ( int )sqrt ( n )+1;
int cnt = ( n+blo-1 )/blo;
for ( int i = 1; i <= blo; i ++ )
{
for ( int j = 0; j < n; j ++ )
sum[i][j] = sum[i-1][j];
for ( int j = ( i-1 )*cnt; j < n && j < i*cnt; j ++ )
sum[i][ a[j] ] ++;
}
for ( int i = 1; i <= blo; i ++ )
{
for ( int j = i; j <= blo; j ++ )
{
cc[i][j] = cc[i][j-1]; //
mul[i][j] = mul[i][j-1];
for ( int k = ( j-1 )*cnt; k < n && k < j*cnt; k ++ )
{
int x = sum[j][ a[k] ]-sum[i-1][ a[k] ];
if ( x > cc[i][j] || x == cc[i][j] && mul[i][j] > a[k] )
{
cc[i][j] = x;
mul[i][j] = a[k];
}
}
}
}
int L, R, ans, anspos;
//ans ，anspos
while ( Q -- )
{
scanf ( "%d%d", &L, &R );
int x = L/cnt+1, y = R/cnt+1;
ans = cc[x+1][y-1], anspos = mul[x+1][y-1];
for ( int i = L; i <= R && i < x*cnt; i ++ )
tmp[ a[i] ] = max ( 0, sum[y-1][ a[i] ]-sum[x][ a[i] ] );
for ( int i = max ( L, ( y-1 )*cnt ); i <= R; i ++ )
tmp[ a[i] ] = max ( 0, sum[y-1][ a[i] ]-sum[x][ a[i] ] );
for ( int i = L; i < x*cnt && i <= R; i ++ )
{
tmp[ a[i] ] ++;
if ( tmp[ a[i] ] > ans || tmp[ a[i] ] == ans && a[i] < anspos )
{
ans = tmp[ a[i] ];
anspos = a[i];
}
}
if ( x != y ) //
{
for ( int i = ( y-1 )*cnt; i <= R; i ++ )
{
tmp[ a[i] ] ++;
if ( tmp[ a[i] ] > ans || tmp[ a[i] ] == ans && a[i] < anspos )
{
ans = tmp[ a[i] ];
anspos = a[i];
}
}
}
printf ( "%d %d
", anspos, ans );
}
}
int main ( )
{
solve ( );
return 0;
} x 값 이 구간 [0, n) 에 없 을 때 우 리 는 이산 을 통 해 [0, n) 에 투사 할 수 있다.
이산 화 코드:
memcpy ( b, a, sizeof ( a ) );
sort ( a, a+n );
for ( int i = 0; i < n; i ++ )
b[i] = lower_bound ( a, a+n, b[i] )-a;3. 수 정 된 구간 의 중수
수정 되 지 않 은 구간 의 중 수 를 잘 해 결 했 기 때문에 예비 처 리 는 모두 같 습 니 다. 다만 우리 가 해 야 할 일 은 수정 할 때 sum 과 cc 의 값 을 업데이트 하면 됩 니 다. 한 수 를 수정 할 때 blo ^ 2 개 구간 (blo 는 덩어리) 에 영향 을 줄 수 있 습 니 다. blo = sqrt (n) 라면 복잡 도 는 n 입 니 다. 이것 은 받 아들 일 수 없습니다. 우 리 는 blo = n ^ (1 / 3)그러면 복잡 도 는 n ^ (2 / 3) 입 니 다. 만약 에 우리 가 i ~ j 블록 숫자 x 가 나타 난 횟수 (bb [i] [j] [x]), i ~ j 블록 이 나타 난 횟수 가 x 의 개수 (tim [i] [j] [x]) 를 동시에 미리 처리 하면 a [L] = R 을 수정 할 때 (L 은 x 블록 에 속 함) x 블록 을 포함 한 모든 구간 블록 에 영향 을 줄 것 입 니 다. bb [i] [j] [x] 와 tim [i] [j] [x] 의 수정 이 간단 하기 때문에 cc [i] [j]의 값 은 어 떻 습 니까? 최대 횟수 의 변화 범 위 는 [- 1, 1] 사이 에 있 기 때문에 (예전 의 수의 횟수 가 1 을 줄 였 기 때문에 현재 의 수 는 1 을 더 하면 중수 개 수 는 하나 가 아 닐 수 있 기 때문에 중수 변화 [- 1, 1] 안에 있 기 때문에 tim 의 개 수 를 직접 판단 하여 cc 의 값 을 구 할 수 있 습 니 다. sum 의 값 은 하나의 순환 으로 업데이트 할 수 있 습 니 다. 전체적인 복잡 도 는 O (n + q) * n ^ (2 / 3) 입 니 다.
여기 서 bb [i] [j] 와 tim [i] [j] 의 처 리 는 앞의 cc [i] [j] 의 처리 와 같 습 니 다. i ~ j - 1 의 값 을 구 했 습 니 다. bb [i] [j - 1], tim [i] [j - 1] 의 값 을 복사 해 야 합 니 다.
#include
using namespace std;
const int maxn = 20005, N = 28;
int sum[N][maxn], a[maxn], cc[N][N];
int tmp[maxn], tim[N][N][maxn], bb[N][N][maxn];
void solve ( )
{
int n, Q;
//freopen ( "in0.in", "r", stdin );
//freopen ( "in1.out", "w", stdout );
scanf ( "%d%d", &n, &Q );
for ( int i = 0; i < n; i ++ )
scanf ( "%d", &a[i] );
int blo = ( int )pow ( n, 1.0/3 )+1;
int cnt = ( n+blo-1 )/blo;
for ( int i = 1; i <= blo; i ++ )
{
for ( int j = 0; j < n; j ++ )
sum[i][j] = sum[i-1][j];
for ( int j = ( i-1 )*cnt; j < n && j < i*cnt; j ++ )
sum[i][ a[j] ] ++;
}
for ( int i = 1; i <= blo; i ++ )
{
for ( int j = i; j <= blo; j ++ )
{
cc[i][j] = cc[i][j-1];
for ( int k = 0; k < n; k ++ ) //
{
bb[i][j][k] = bb[i][j-1][k];
tim[i][j][k] = tim[i][j-1][k];
}
for ( int k = ( j-1 )*cnt; k < n && k < j*cnt; k ++ )
{
int p = bb[i][j][ a[k] ] ++;
tim[i][j][p] --;
tim[i][j][p+1] ++;
int x = sum[j][ a[k] ]-sum[i-1][ a[k] ];
if ( x > cc[i][j] )
cc[i][j] = x;
}
}
}
int op, L, R, ans;
while ( Q -- )
{
scanf ( "%d%d%d", &op, &L, &R );
if ( op )
{
int x = L/cnt+1, y = R/cnt+1;
ans = cc[x+1][y-1];
for ( int i = L; i <= R && i < x*cnt; i ++ )
tmp[ a[i] ] = max ( 0, sum[y-1][ a[i] ]-sum[x][ a[i] ] );
for ( int i = ( y-1 )*cnt; i <= R; i ++ )
tmp[ a[i] ] = max ( 0, sum[y-1][ a[i] ]-sum[x][ a[i] ] );
for ( int i = L; i < x*cnt && i <= R; i ++ )
{
tmp[ a[i] ] ++;
if ( tmp[ a[i] ] > ans )
ans = tmp[ a[i] ];
}
if ( x != y )
{
for ( int i = ( y-1 )*cnt; i <= R; i ++ )
{
tmp[ a[i] ] ++;
if ( tmp[ a[i] ] > ans )
ans = tmp[ a[i] ];
}
}
printf ( "%d
", ans );
}
else
{
int p = a[L];
a[L] = R;
int x = L/cnt+1;
for ( int i = x; i <= blo; i ++ )
{
sum[i][p] --;
sum[i][R] ++;
}
for ( int i = 1; i <= blo; i ++ )
{
for ( int j = i; j <= blo; j ++ )
{
if ( i <= x && x <= j ) // x
{
int t = bb[i][j][p] --;
tim[i][j][t] --; //
tim[i][j][t-1] ++;
t = bb[i][j][R] ++;
tim[i][j][t] --;
tim[i][j][t+1] ++;
t = cc[i][j];
if ( tim[i][j][t-1] )//
cc[i][j] = t-1;
if ( tim[i][j][t] )
cc[i][j] = t;
if ( tim[i][j][t+1] )
cc[i][j] = t+1;
}
}
}
}
}
}
int main ( )
{
solve ( );
return 0;
}
4. 수 정 된 구간 중수 의 기타 문제
1. 숫자의 x 는 [0, n) 에 한정 되 지 않 을 때 도 마찬가지 로 이산 화 처 리 를 할 수 있 지만 수정 이 있 기 때문에 모든 수 정 된 수 를 넣 고 정렬 해 야 한다. 그러면 [0, 2n) 구간 에 한정 된다.
2. 횟수 가 가장 많 고 숫자 가 가장 작은 숫자 가 필요 할 때 tim 을 set 로 정의 할 수 있 습 니 다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
