수열 블록 입문 1 ~ 9 문제 풀이
176476 단어 조각 을 나누다- - 데이터 구조 -알고리즘 총화
개술
블록 을 나 누 는 것 은 수열 을 여러 개의 블록 으로 나 누 어 각각 블록 안의 정 보 를 유지 하 는 것 이다. 조 회 는 각 블록 안의 정 보 를 호출 하면 매우 유연 한 데이터 구조 이다.
우선 변수 정의:
l e n len 각 블록의 크기 n u m num num 블록의 수량 b l [i] bl [i] bl [i] i 번 요 소 는 몇 번 블록 l [i], r [i] l [i], r [i] l [i], l [i], r [i] 각 블록의 좌우 단점 에 속한다.
평균 값 부등식 에 따라 우 리 는 n \ sqrt n 개의 블록 을 만 드 는 것 이 가장 좋 고 모든 블록 크기 도 n \ sqrt n 이다.
어떻게 블록 을 만 들 수 있 습 니까?
void build() {
len = sqrt(n), num = (n - 1) / len + 1 ;
rep(i, 1, n) bl[i] = (i - 1) / len + 1 ;
rep(i, 1, num) l[i] = (i - 1) * len + 1, r[i] = i * len ;
r[num] = n ; //
}
코드 는 비교적 분명 하 다. 유일 하 게 주의해 야 할 것 은 마지막 조각 이 이전 보다 작 을 것 이다. 왜냐하면 그의 오른쪽 단점 은 반드시 n n 이기 때문이다.
그리고 저 희 는 L. O. J. LOJ 의 9999 문 제 를 통 해 P. r. o. b. l. e. m 를 분석 해 보도 록 하 겠 습 니 다. S e t Problem \ Set Problem Set
예제 1
n n n 으로 긴 수열 과 n n n 개의 조작 을 제시 하고 구간 덧셈, 단일 검사 값 을 조작 합 니 다.
가장 기본 적 인 문제 부터.
우 리 는 t a g [i] tag [i] tag [i] 로 i i 블록 증가 값 을 기록 합 니 다.
수정 작업 [x, y] [x, y] [x, y] [x, y]
만약 x x x 와 y y y 가 같은 덩어리 에 속한다 면 a [x..... y] a [x... y] a [x... y] a [x... y] 를 직접 폭력 적 으로 수정 합 니 다.
그렇지 않 으 면 전체 블록 에 대해 t a g tag 를 직접 수정 하고 다른 분산 요소 에 대해 a [i] a [i] a [i] a [i] a [i] 를 직접 폭력 적 으로 수정 합 니 다.
검색 의 x x x 에 대한 답 은 a [x] + t a g [b l [x] a [x] + tag [bl [x] a [x] + tag [bl [x]]]] 이다.
시간 복잡 도 O n ) O(n~\sqrt n) O(n n )
const int N = 100010 ;
const int M = 320 ;
int bl[N], l[M], r[M], tag[M], a[N] ;
int n, len, num ;
/* bl[i] : i
* l[i] i
r[i] i
tag[i] i
*/
void build() {
len = sqrt(n), num = (n - 1) / len + 1 ;
rep(i, 1, n) bl[i] = (i - 1) / len + 1 ;
rep(i, 1, num) l[i] = (i - 1) * len + 1, r[i] = i * len ;
r[num] = n ;
}
void change(int x, int y, int val) {
if (bl[x] == bl[y]) rep(i, x, y) a[i] += val ; // ，
else {
rep(i, bl[x] + 1, bl[y] - 1) tag[i] += val ; //
rep(i, x, r[bl[x]]) a[i] += val ; //
rep(i, l[bl[y]], y) a[i] += val ;
}
}
int query(int x) {
return a[x] + tag[bl[x]] ; // O(1)
}
signed main(){
scanf("%d", &n) ; int m = n ;
rep(i, 1, n) scanf("%d", &a[i]) ;
build() ;
while (m--) {
int op ; scanf("%d", &op) ;
if (op == 0) {
int x, y, val ; scanf("%d%d%d", &x, &y, &val) ;
change(x, y, val) ;
} else {
int x, y, val ; scanf("%d%d%d", &x, &y, &val) ;
printf("%d
", query(y)) ;
}
}
return 0 ;
}
이 문제 의 연습 을 통 해 우 리 는 블록 버스터 의 작업 원 리 를 대충 요약 할 수 있다. 블록 버스터 처리, 작은 폭력 이다.
예제 2
n n n 으로 긴 수열 과 n n n 개의 조작 을 제시 하고 구간 덧셈 과 관련 되 며 구간 내 에서 특정한 값 x x x 보다 작은 요소 개 수 를 문의 합 니 다.
우선 당신 은 조작 을 수정 하지 않 고 어떻게 하 는 지 알 아야 합 니 다.
분석 총 시간 복잡 도 O (n) l o g n ) O(n \sqrt n \ log \ n) O(nn log n)
int n, m, len, num ;
int a[N], bl[N], l[M], r[M], tag[M] ;
vi v[M] ;
void build() {
len = sqrt(n), num = (n - 1) / len + 1 ;
rep(i, 1, n) {
bl[i] = (i - 1) / len + 1 ;
v[bl[i]].pb(a[i]) ;
}
rep(i, 1, num) {
l[i] = (i - 1) * len + 1 ;
r[i] = i * len ;
sort(v[i].begin(), v[i].end()) ;
}
r[num] = n ;
}
void reset(int x) { // x
v[x].clear() ;
rep(i, l[x], r[x]) v[x].pb(a[i]) ;
sort(v[x].begin(), v[x].end()) ;
}
void change(int x, int y, int val) {
if (bl[x] == bl[y]) { // ，
rep(i, x, y) a[i] += val ;
reset(bl[x]) ;
} else {
rep(i, bl[x] + 1, bl[y] - 1) tag[i] += val ;
rep(i, x, r[bl[x]]) a[i] += val ;
rep(i, l[bl[y]], y) a[i] += val ;
reset(bl[x]) ; reset(bl[y]) ; //
}
}
int query(int x, int y, int val) {
int ans = 0 ;
if (bl[x] == bl[y]) { // ，
rep(i, x, y) if (a[i] + tag[bl[i]] < val) ans++ ;
} else {
rep(i, bl[x] + 1, bl[y] - 1)
ans += lower_bound(v[i].begin(), v[i].end(), val - tag[i]) - v[i].begin() ; //
rep(i, x, r[bl[x]]) if (a[i] + tag[bl[i]] < val) ans++ ; //
rep(i, l[bl[y]], y) if (a[i] + tag[bl[i]] < val) ans++ ;
}
return ans ;
}
signed main(){
scanf("%d", &n) ; int m = n ;
rep(i, 1, n) scanf("%d", &a[i]) ;
build() ;
while (m--) {
int op, x, y, val ;
scanf("%d%d%d%d", &op, &x, &y, &val) ;
if (!op) change(x, y, val) ;
else printf("%d
", query(x, y, val * val)) ;
}
return 0 ;
}
예제 3
n n 의 시퀀스 와 n n n 의 길 이 를 지정 합 니 다.구간 덧셈 지원, 구간 조회 v v v 의 전구.
이것 은 앞의 저것 과 차이 가 많 지 않 으 니, 단지 2 점 만 수정 하면 된다. 독자 들 은 직접 코드 를 볼 수 있다.
int n, m, len, num ;
int a[N], bl[N], l[M], r[M], tag[M] ;
vi v[M] ;
void build() {
len = sqrt(n), num = (n - 1) / len + 1 ;
rep(i, 1, n) {
bl[i] = (i - 1) / len + 1 ;
v[bl[i]].pb(a[i]) ;
}
rep(i, 1, num) {
l[i] = (i - 1) * len - 1, r[i] = i * len ;
sort(v[i].begin(), v[i].end()) ;
}
r[num] = n ;
}
void reset(int x) {
v[x].clear() ;
rep(i, l[x], r[x]) v[x].pb(a[i]) ;
sort(v[x].begin(), v[x].end()) ;
}
void change(int x, int y, int val) {
if (bl[x] == bl[y]) {
rep(i, x, y) a[i] += val ;
reset(bl[x]) ;
} else {
rep(i, bl[x] + 1, bl[y] - 1) tag[i] += val ;
rep(i, x, r[bl[x]]) a[i] += val ;
rep(i, l[bl[y]], y) a[i] += val ;
reset(bl[x]) ; reset(bl[y]) ;
}
}
int query(int x, int y, int val) {
int ans = -1 ;
if (bl[x] == bl[y]) {
rep(i, x, y) if (a[i] + tag[bl[i]] < val) ans = max(ans, a[i] + tag[bl[i]]) ;
} else {
rep(i, bl[x] + 1, bl[y] - 1) {
vector <int>::iterator it = lower_bound(v[i].begin(), v[i].end(), val - tag[i]) ;
if (it != v[i].begin()) ans = max(ans, *(--it) + tag[i]) ;
}
rep(i, x, r[bl[x]]) if (a[i] + tag[bl[i]] < val) ans = max(ans, a[i] + tag[bl[i]]) ;
rep(i, l[bl[y]], y) if (a[i] + tag[bl[i]] < val) ans = max(ans, a[i] + tag[bl[i]]) ;
}
return ans ;
}
signed main(){
scanf("%d", &n) ; int m = n ;
rep(i, 1, n) scanf("%d", &a[i]) ;
build() ;
while (m--) {
int op, x, y, val ;
scanf("%d%d%d%d", &op, &x, &y, &val) ;
if (!op) change(x, y, val) ;
else printf("%d
", query(x, y, val)) ;
}
return 0 ;
}
예제 4
n n 의 시퀀스 와 n n n 의 길 이 를 지정 합 니 다.구간 덧셈, 구간 구 화 를 지원 합 니 다.정 답 은 0 9 + 7 10 ^ 9 + 7 109 + 7 모델 링.
구간 구 화?t a g tag tag 조회 만으로 O (n) O (\ sqrt n) O (n) 가 됩 니 다.
우 리 는 s u m [i] sum [i] sum [i] 을 정의 합 니 다.
우 리 는 조작 수정 을 고려 하고 있다.
int n, m, len, num ;
ll a[N], bl[N], l[M], r[M], tag[M], sum[M] ;
void build() {
len = sqrt(n) ; num = (n - 1) / len + 1 ;
rep(i, 1, n) {
bl[i] = (i - 1) / len + 1 ;
sum[bl[i]] += a[i] ;
}
rep(i, 1, num) {
l[i] = (i - 1) * len + 1 ;
r[i] = i * len ;
}
r[num] = n ;
}
void change(int x, int y, int val) {
if (bl[x] == bl[y]) {
rep(i, x, y) a[i] += val ;
sum[bl[x]] += 1ll * (y - x + 1) * val ;
} else {
rep(i, bl[x] + 1, bl[y] - 1) tag[i] += val ;
rep(i, x, r[bl[x]]) a[i] += val ;
sum[bl[x]] += 1ll * (r[bl[x]] - x + 1) * val ;
rep(i, l[bl[y]], y) a[i] += val ;
sum[bl[y]] += 1ll * (y - l[bl[y]] + 1) * val ;
}
}
ll query(int x, int y, int MOD) {
int ans = 0 ;
if (bl[x] == bl[y]) {
rep(i, x, y) ans = (ans + a[i]) % MOD ;
ans = (ans + 1ll * (y - x + 1) * tag[bl[x]] % MOD) % MOD ;
} else {
rep(i, bl[x] + 1, bl[y] - 1) {
ans = (ans + sum[i]) % MOD ;
ans = (ans + 1ll * tag[i] * len % MOD) % MOD ;
}
rep(i, x, r[bl[x]]) ans = (ans + a[i]) % MOD ;
ans = (ans + 1ll * (r[bl[x]] - x + 1) * tag[bl[x]] % MOD) % MOD ;
rep(i, l[bl[y]], y) ans = (ans + a[i]) % MOD ;
ans = (ans + 1ll * (y - l[bl[y]] + 1) * tag[bl[y]] % MOD) % MOD ;
}
return ans ;
}
signed main(){
scanf("%d", &n) ; m = n ;
rep(i, 1, n) scanf("%lld", &a[i]) ;
build() ;
while (m--) {
int op, l, r, val ; scanf("%d%d%d%d", &op, &l, &r, &val) ;
if (!op) change(l, r, val) ;
else printf("%lld
", query(l, r, val + 1)) ;
}
return 0 ;
}
예제 5
n n 의 시퀀스 와 n n n 의 길 이 를 지정 합 니 다.구간 개방, 구간 구 화 를 지원 합 니 다.
이 문제 도 매우 체계 적 이어서 '화신 이 각국 을 여행 하 다' 고 한 사람 은 모두 이 방법 을 알 것 이다.
우 리 는 1, 0, 9, 10, 9, 109 의 수 를 발 견 했 는데, 최대 55 제곱 을 열 면 1, 1, 1 이 된다.
모든 구간 이 1 인 구간 에 대해 개방 작업 을 하 는 것 은 분명 의미 가 없다.
그러면 우 리 는 그 블록 들 을 기록 할 수 있 고 개방 적 인 조작 도 할 수 있 으 며 폭력 으로 끝 날 것 이다.
시간 복잡 도 O (n) O (n \ sqrt n) O (n)
int n, m, len, num ;
int a[N], bl[N], l[M], r[M], flg[M], sum[M] ;
void build() {
len = sqrt(n) ; num = (n - 1) / len + 1 ;
rep(i, 1, n) bl[i] = (i - 1) / len + 1, sum[bl[i]] += a[i] ;
rep(i, 1, num) l[i] = (i - 1) * len + 1, r[i] = i * len ;
r[num] = n ;
}
void modify(int x, int y) {
if (bl[x] == bl[y]) {
rep(i, x, y) {
sum[bl[i]] -= a[i] ;
a[i] = sqrt(a[i]) ;
sum[bl[i]] += a[i] ;
}
} else {
rep(i, bl[x] + 1, bl[y] - 1) {
if (flg[i]) continue ;
sum[i] = 0, flg[i] = 1 ;
rep(j, l[i], r[i]) {
a[j] = sqrt(a[j]) ;
sum[i] += a[j] ;
flg[i] &= (a[j] <= 1) ;
}
}
rep(i, x, r[bl[x]]) {
sum[bl[i]] -= a[i] ;
a[i] = sqrt(a[i]) ;
sum[bl[i]] += a[i] ;
}
rep(i, l[bl[y]], y) {
sum[bl[i]] -= a[i] ;
a[i] = sqrt(a[i]) ;
sum[bl[i]] += a[i] ;
}
}
}
int query(int x, int y) {
int ans = 0 ;
if (bl[x] == bl[y]) {
rep(i, x, y) ans += a[i] ;
} else {
rep(i, bl[x] + 1, bl[y] - 1) ans += sum[i] ;
rep(i, x, r[bl[x]]) ans += a[i] ;
rep(i, l[bl[y]], y) ans += a[i] ;
}
return ans ;
}
signed main(){
scanf("%d", &n) ; m = n ;
rep(i, 1, n) scanf("%d", &a[i]) ;
build() ;
while (m--) {
int op, x, y, val ;
scanf("%d%d%d%d", &op, &x, &y, &val) ;
if (op == 0) modify(x, y) ;
else printf("%d
", query(x, y)) ;
}
return 0 ;
}
예제
n n n 으로 긴 수열 과 n n n 개의 조작 을 보 여 줍 니 다. 조작 은 한 점 삽입, 한 점 문의, 데이터 무 작위 생 성 과 관련 됩 니 다.
다음 알고리즘 은 무 작위 생 성 에 대응 할 수 있 습 니 다.
무 작위 로 생 성 된 데이터 에 대해 서 는 블록 마다 삽입 횟수 가 균등 하 게 분담 되 어 있 습 니 다. 우 리 는 하나의 v e c t o r vector vector 를 통 해 만 해결 할 수 있 습 니 다.
그러나 극한 데이터 에서 블록 에 n n 회 이상 삽입 하면 블록 이 매우 큰 상황 을 초래 할 수 있 습 니 다.
그러면 우 리 는 시간의 복잡 도 를 유지 하기 위해 블록 을 재 구성 할 수 있 습 니 다. 블록 크기 가 20 * 8727 ° n 20 * \ sqrt n 20 * 8727 ° n 에 이 르 렀 을 때 서열 을 재 구성 할 수 있 습 니 다.
총 시간 복잡 도 O (n) O (n \ sqrt n) O (n)
int n, m, len, num ;
int a[N], st[N << 1], bl[M] ;
vi v[M] ;
void build() {
len = sqrt(n), num = (n - 1) / len + 1 ;
rep(i, 1, n) bl[i] = (i - 1) / len + 1, v[bl[i]].pb(a[i]) ;
}
void cg() { //
int top = 0 ;
rep(i, 1, num) {
rep(j, 0, siz(v[i]) - 1) st[++top] = v[i][j] ;
v[i].clear() ;
}
len = sqrt(top), num = (top - 1) / len + 1 ;
rep(i, 1, top) bl[i] = (i - 1) / len + 1, v[bl[i]].pb(st[i]) ;
}
pii get(int k) { // x
int x = 1 ;
while (k > siz(v[x])) k -= siz(v[x]), x++ ;
return mp(x, k - 1) ;
}
void change(int x, int y) {
pii r = get(x) ;
int i = r.fi ;
v[i].insert(v[i].begin() + r.se, y) ; // vector
if (siz(v[i]) > 20 * len) cg() ;
}
int query(int x) {
pii r = get(x) ;
return v[r.fi][r.se] ;
}
signed main(){
scanf("%d", &n) ; m = n ;
rep(i, 1, n) scanf("%d", &a[i]) ;
build() ;
while (m--) {
int op, x, y, val ; scanf("%d%d%d%d", &op, &x, &y, &val) ;
if (!op) change(x, y) ;
else printf("%d
", query(y)) ;
}
return 0 ;
}
예제
n n n 으로 긴 수열 과 n n n 개의 조작 을 제시 하고 구간 곱셈, 구간 덧셈, 단점 질문 과 관련된다.
또 하나의 틀 에 박 힌 문제 이다.
선분 나무 로 이 문 제 를 어떻게 풀 었 습 니까?두 개의 배열 m u l [i], a d [i] mul [i], add [i] mul [i], add [i] 를 열 고 유지 합 니 다.
그러면 블록 도 비슷 해 요.
우선 강제 곱셈 이 덧셈 보다 우선이다
각 블록 에 대해 a d [i], m u l [i] add [i], mul [i] add [i], mul [i] add [i], mul [i] 로 각각 전체 블록 내 더하기 와 곱 하기 값 을 표시 합 니 다.
하나의 요소 에 대해 a [i] a [i] a [i] 의 실제 값 은 a [i] * 8727 ° m u l [b l [i] + a d [b l [i] a [i]] * mul [bl [i]] + add [bl [i]] a [i]] * 8727 ° mul [bl [i]]] + add [bl [i]]]]]]
곱셈 수정 작업 에 대해 a d [i] add [i] add [i] 와 m u l [i] mul [i] mul [i] 는 각각 a d [i] ∗ v a l add [i] * val add [i] ∗ val 과 m u l [i] ∗ v a l mul [i] * val mul [i] ∗
덧셈 조작 에 대해 a d [i] add [i] add [i] 와 m u l [i] mul [i] mul [i] 를 각각 a d [i] + v a l add [i] + val add [i] + val 과 m u l [i] mul [i] mul [i] mul [i] mul [i] 로 표시 합 니 다.
분산 요소 에 대해 서 는 직접 폭력 전 투 를 통 해 비 워 두 고 그 자 체 를 수정 하면 된다.
int n, m, len, num ;
int a[N], bl[N], l[M], r[M], add[M], mul[M] ;
void build() {
len = sqrt(n), num = (n - 1) / len + 1 ;
rep(i, 1, n) bl[i] = (i - 1) / len + 1 ;
rep(i, 1, num) l[i] = (i - 1) * len + 1, r[i] = i * len, mul[i] = 1 ;
r[num] = n ;
}
void reset(int x) {
rep(i, l[x], r[x]) a[i] = (a[i] * mul[x] + add[x]) % MOD ;
add[x] = 0, mul[x] = 1 ;
}
void Add(int x, int y, int val) {
if (bl[x] == bl[y]) {
reset(bl[x]) ;
rep(i, x, y) a[i] = (a[i] + val) % MOD ;
} else {
rep(i, bl[x] + 1, bl[y] - 1) add[i] = (add[i] + val) % MOD ;
reset(bl[x]) ; reset(bl[y]) ;
rep(i, x, r[bl[x]]) a[i] = (a[i] + val) % MOD ;
rep(i, l[bl[y]], y) a[i] = (a[i] + val) % MOD ;
}
}
void Mul(int x, int y, int val) {
if (bl[x] == bl[y]) {
reset(bl[x]) ;
rep(i, x, y) a[i] = a[i] * val % MOD ;
} else {
rep(i, bl[x] + 1, bl[y] - 1) {
add[i] = add[i] * val % MOD ;
mul[i] = mul[i] * val % MOD ;
}
reset(bl[x]) ; reset(bl[y]) ;
rep(i, x, r[bl[x]]) a[i] = a[i] * val % MOD ;
rep(i, l[bl[y]], y) a[i] = a[i] * val % MOD ;
}
}
int query(int x) {
return (a[x] * mul[bl[x]] + add[bl[x]]) % MOD ;
}
signed main(){
scanf("%d", &n) ; m = n ;
rep(i, 1, n) scanf("%d", &a[i]) ;
build() ;
while (m--) {
int op, l, r, val ; scanf("%d%d%d%d", &op, &l, &r, &val) ;
if (op == 0) Add(l, r, val % MOD) ;
else if (op == 1) Mul(l, r, val % MOD) ;
else printf("%d
", query(r)) ;
}
return 0 ;
}
예제
n n n 으로 긴 수열 과 n n n 개 동작 을 보 여 줍 니 다. 구간 문의 와 같은 수 c c c 의 요 소 를 조작 하고 이 구간 의 모든 요 소 를 c c c c 로 바 꿉 니 다.
우 리 는 폭력 적 인 방법 을 고려 했다.
수정 작업
문의 조작
자세히 분석:
초기 서열 이 모두 같은 값 이 라 고 가정 하면 단어 조회 의 시간 복잡 도 는 O (n) O (\ sqrt n) O (n) 이다.
구간 조작 이 라면 가장 많은 파괴 링 1 위 가 222 인 블록 의 표 시 를 통 해 우 리 는 두 개의 폭력 시간 을 증가 시 켰 다. 평균 분담 시간 은 여전히 O (n) O (\ sqrt n) O (n) 이다.
쉽게 말 하면 출제 자 는 O (n) O (n) O (n) 의 시간 을 한 번 써 서 대답 하 기 를 원한 다. 그 는 O (n) O (\ sqrt n) O (n) 의 수정 작업 을 써 야 한다.
그래서 평균 분담 시간 복잡 도 O (n) O (n \ sqrt n) O (N)
int n, m, len, num ;
int a[N], bl[N], l[M], r[M], cov[M], tag[M] ;
void build() {
len = sqrt(n), num = (n - 1) / len + 1 ;
rep(i, 1, n) bl[i] = (i - 1) / len + 1 ;
rep(i, 1, num) l[i] = (i - 1) * len + 1, r[i] = i * len ;
r[num] = n ;
}
void reset(int x) {
if (!tag[x]) return ;
rep(i, l[x], r[x]) a[i] = cov[x] ;
tag[x] = 0 ;
}
void modify(int x, int y, int val) {
if (bl[x] == bl[y]) {
reset(bl[x]) ;
rep(i, x, y) a[i] = val ;
} else {
rep(i, bl[x] + 1, bl[y] - 1) tag[i] = 1, cov[i] = val ;
reset(bl[x]) ; reset(bl[y]) ;
rep(i, x, r[bl[x]]) a[i] = val ;
rep(i, l[bl[y]], y) a[i] = val ;
}
}
int query(int x, int y, int val) {
int ans = 0 ;
if (bl[x] == bl[y]) {
reset(bl[x]) ;
rep(i, x, y) ans += (a[i] == val) ;
} else {
rep(i, bl[x] + 1, bl[y] - 1)
if (tag[i]) ans += (cov[i] == val ? len : 0) ;
else {
rep(j, l[i], r[i]) ans += (a[j] == val) ;
}
reset(bl[x]) ; reset(bl[y]) ;
rep(i, x, r[bl[x]]) ans += (a[i] == val) ;
rep(i, l[bl[y]], y) ans += (a[i] == val) ;
}
return ans ;
}
signed main(){
scanf("%d", &n) ; m = n ;
rep(i, 1, n) scanf("%d", &a[i]) ;
build() ;
while (m--) {
int x, y, val ; scanf("%d%d%d", &x, &y, &val) ;
printf("%d
", query(x, y, val)) ;
modify(x, y, val) ;
}
return 0 ;
}
예제
n n n 으로 긴 수열 과 n n n 개의 조작 을 제시 하고 질문 구간 과 관련 된 최소 중 수 를 조작 합 니 다.
이것 은 조금 어렵 습 니 다. 우 리 는 먼저 조작 을 수정 하지 않 은 문 제 를 고려 합 시다.
먼저 m o d e (i) mode (i) mode (i) 를 i i 개의 전체 블록 으로 정의 합 니 다.
우 리 는 하나의 성질 을 발견 했다. 하나의 질문 에 대해 [x, y] [x, y] [x, y], 답 은 8712 ° m o d e (i \ in mode (i * 8712 ° mode (i ~ j) ∪ j)~ \cup j) 분산 원소
이 성질 은 분명 하 다.
x x x 는 블록 a a a, y y 는 블록 b b 에 속 합 니 다.
그러면 [x, y] [x, y] [x, y] 는 다음 과 같이 나 눌 수 있다.
이 성질 에 따라 우 리 는 n \ sqrt n 개 수의 출현 횟수 만 비교 하면 된다.
우 리 는 O (n) O (n \ sqrt n) O (N) 를 예 처리 할 수 있다.
질문 에 대해 [x, y] [x, y] [x, y]
계산 을 편리 하 게 하기 위해 서 우 리 는 데이터 에 대해 이산 화 해 야 한다.
시간 복잡 도 O l o g n ) O(n \sqrt n ~log~n) O(nn log n)
int n, m, len, num ;
int a[N], tmp[N], bl[N], l[M], r[M], cnt[N], f[M][M] ;
vi p[N] ;
void build() {
rep(i, 1, n) tmp[i] = a[i] ;
sort(tmp + 1, tmp + n + 1) ;
int sz = unique(tmp + 1, tmp + n + 1) - tmp - 1 ;
rep(i, 1, n) {
a[i] = lower_bound(tmp + 1, tmp + sz + 1, a[i]) - tmp ;
p[a[i]].pb(i) ;
}
len = sqrt(n / log2(n)), num = (n - 1) / len + 1 ;
rep(i, 1, n) bl[i] = (i - 1) / len + 1 ;
rep(i, 1, num) l[i] = (i - 1) * len + 1, r[i] = i * len ;
r[num] = n ;
}
void init() {
rep(i, 1, num) {
clr(cnt) ;
int ans = 0, mx = 0 ;
rep(j, i, num) {
rep(k, l[j], r[j]) {
cnt[a[k]]++ ;
if (cnt[a[k]] > mx || (cnt[a[k]] == mx && a[k] < ans)) ans = a[k], mx = cnt[a[k]] ;
}
f[i][j] = ans ;
}
}
}
int sum(int l, int r, int val) {
return upper_bound(p[val].begin(), p[val].end(), r) -
lower_bound(p[val].begin(), p[val].end(), l) ;
}
void solve(int x, int y, int l, int r, int &ans, int &mx) {
rep(i, x, y) {
int now = sum(l, r, a[i]) ;
if (now > mx || (now == mx && a[i] < ans)) ans = a[i], mx = now ;
}
}
int query(int x, int y) {
int ans = 0, mx = 0 ;
if (bl[x] + 1 >= bl[y]) solve(x, y, x, y, ans, mx) ;
else {
ans = f[bl[x] + 1][bl[y] - 1], mx = sum(x, y, ans) ;
solve(x, r[bl[x]], x, y, ans, mx) ;
solve(l[bl[y]], y, x, y, ans, mx) ;
}
return ans ;
}
signed main(){
scanf("%d", &n) ; m = n ;
rep(i, 1, n) scanf("%d", &a[i]) ;
build() ; init() ;
while (m--) {
int x, y ; scanf("%d%d", &x, &y) ;
printf("%d
", tmp[query(x, y)]) ;
}
return 0 ;
}
감사합니다
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
수열 블록 입문 1 ~ 9 문제 풀이그렇지 않 으 면 전체 블록 에 대해 t a g tag 를 직접 수정 하고 다른 분산 요소 에 대해 a [i] a [i] a [i] a [i] a [i] 를 직접 폭력 적 으로 수정 합 니 다. 분산 요소 에 대해 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
