루트 번호 복잡 도 데이터 구조 (1)
설명 하기 전에 먼저 문제 목록 BF 의 데이터 구조 문제 목록 - 선택 루트 데이터 구조
기초 막 대
모 팀 알고리즘 의 핵심 은 폭력 적 인 풀이 이다. 단지 많은 기 교 를 가지 고 있어 서 알고리즘 의 복잡 도 는 데이터 규모 1e5 정도 의 문 제 를 처리 할 때 상당 하 다.간단 한 문 제 를 예 로 들 면 길이 가 n n n 인 서열 을 제시 하고 m m 차 구간 문 의 를 첨부 하여 구간 내의 모든 숫자 출현 횟수 의 제곱 합 을 구한다.가장 간단 한 폭력 사 고 는 첫 번 째 로 성실 하 게 구간 의 왼쪽 끝 점 에서 오른쪽 끝 점 까지 구간 내 에서 발생 횟수 를 집계 하면 서 제곱 과 공식 n 2 - (n - 1) 2 = 2 n - 1 n ^ 2 - (n - 1) ^ 2 = 2n - 1 n2 - (n - 1) 2 = 2 n - 1 누적 구 해 를 묻 는 것 이다.이후 매번 질문 할 때마다 이전 질문 을 바탕 으로 구간 의 왼쪽 점 과 오른쪽 점 을 계속 이동 하면 된다.매번 문의 하 는 복잡 도 는 O (n) O (n) O (n) 로 모두 n n 회 문의 하 며, 총 시간 복잡 도 는 O (n 2) O (n ^ 2) O (n2) 로 5e 4 의 데 이 터 량 은 절대 시간 을 초과 합 니 다.
모 팀 은 단지 이전의 해법 을 약간 수정 할 뿐이다.먼저 길이 n n n 의 서열 을 n \ sqrt {n} n 블록 으로 나 누고 각 조각의 길 이 는 n \ sqrt {n} n 이다. 그 다음 에 다음 과 같은 규칙 에 따라 문의 한 것 을 정렬 한다. 첫 번 째 키 워드 는 구간 왼쪽 끝 점 이 있 는 블록 으로 작은 것 부터 큰 것 까지 이다.두 번 째 키 워드 는 구간 오른쪽 단점 으로 작은 것 부터 큰 것 까지 누 릅 니 다.이 작업 의 시간 복잡 도 는 정렬 의 복잡 도 O (n l o g n) O (nlogn) O (nlogn) 이다.그 다음 에 이 새로운 질문 순서에 따라 폭력 적 인 사 고 를 실 행 했 는데 그 결과 시간 복잡 도 는 O (n) O (n \ sqrt {n}) O (N) 였 다.어떻게 이해 하 는 지 에 대해 서 는 정렬 후 물 어 볼 수 있 는 분포 연구.왼쪽 점 이 같은 블록 안에 있 는 질문 은 오른쪽 점 이 단 조 롭 게 증가 하기 때문에 오른쪽 점 은 항상 오른쪽으로 이동 합 니 다.왼쪽 점 이 같은 블록 안에 있 는 질문 에 대해 그들의 오른쪽 점 이동 은 모두 O (n) O (n) O (n) O (n) 이 고 모두 n \ sqrt {n} n 블록 이 있 기 때문에 오른쪽 점 이동 의 전체 시간 복잡 도 는 O (n) O (n \ sqrt {n}) O (n) 이다.왼쪽 점 을 보면 같은 블록 안의 왼쪽 점 의 이동 길 이 는 n \ sqrt {n} n 보다 작 을 것 이 고, 인접 블록 안의 이동 은 고작 2 n 2 \ sqrt {n} 2n 이다. 평균 적 으로 물 어 볼 때마다 왼쪽 점 을 n \ sqrt {n} n 개의 위치 로 이동 해 야 한다. 모두 n n 개의 문의, 즉 왼쪽 점 이동 의 전체 시간 복잡 도 는 O (n n) O (n \ sqrt {n}) O 이다.(N). 정렬, 좌우 점 이동 을 통합 하고 전체 시간 복잡 도 는 O (n) O (n \ sqrt {n}) O (N) 등급 입 니 다.
P4462 [CQOI 2018] 이상 또는 시퀀스
- 문제 설명 - 원제 참조 - 문제 풀이 사고 - 본 문 제 는 모 팀 이 해결 할 수 있 는 전형 적 인 데이터 구조 문제 입 니 다. 먼저 서열 의 접두사 가 다 르 거나 이 서열 을 s u m sum sum 이 라 고 부 릅 니 다. 우리 가 어느 구간 의 차이 점 이나 k k k k k k 를 알 고 싶 을 때 사실은 한 쌍 의 l l l 과 r r 만족, s u m l - 1 * 8853 ° s u m r = k sum {l - 1}\ \ oplus sum {r} = k suml - 1 ⊕ sumr = k, 이 또는 성질 에 따라 s u m l - 1 ⊕ k = s u m r sum {l - 1} \ \ oplus k = sum {r} suml - 1 ⊕ k = sumr 또는 s u m r ⊕ k = s u m l - 1 sum {r} \ \ oplus k = sum {l - 1}sumr ⊕ k = suml − 1. 따라서 이 또는 i 의 구간 개 수 를 기록 하 는 데 사용 할 배열 만 필요 합 니 다. 이후 정렬 된 질문 에서 구간 이 새로운 경계 로 확 대 될 때마다 이 또는 값 을 누적 합 니 다.\ \ oplus k sum 경 계 는 8853 ° k 의 구간 갯 수 입 니 다. 여기 서 모 팀 의 최적화 기 교 를 제시 합 니 다. 정렬 을 물 을 때 왼쪽 끝 점 이 있 는 블록 이 홀수 라면 오른쪽 끝 점 은 작은 것 에서 큰 것 으로 정렬 하고 짝수 라면 오른쪽 끝 점 은 큰 것 에서 작은 것 으로 배열 할 수 있 습 니 다. 이러한 장점 은 문의 왼쪽 끝 점 이 한 조각 에서 다른 조각 으로 갈 때 오른쪽 끝 점 입 니 다.블록 에서 가장 작은 오른쪽 점 으로 한꺼번에 되 돌아 가 는 것 이 아니 라 가 까 운 곳 으로 먼저 이동 할 수 있 습 니 다. 이론 적 으로 시간 과 비용 을 절약 할 수 있 습 니 다. 코드 -
#include
", ans[i]);
}
return 0;
}
수모 대 를 거느리다
말 그대로 수정 작업 을 지원 하 는 모 쌍 알고리즘 입 니 다. 일반적인 제목 에 포 함 된 설명 은 구간 의 한 점 값 에 대한 변 화 를 포함 합 니 다. 예 를 들 어 길이 n n n 의 서열 을 제시 하고 m m m 의 조작 이 있 습 니 다. 작업 은 두 가 지 를 포함 합 니 다. 하 나 는 해당 하 는 숫자 를 다른 숫자 로 바 꾸 는 것 입 니 다. 하 나 는 구간 [l, r] [l, r] [l, r] [l, r] 의 조회 입 니 다.
띠 슈 모 팀 은 기초 모 팀 에 시간 축 을 추가 했다. 매번 수정 할 때마다 새로운 시간 점 으로 기록 하고 문의 하 는 정렬 방식: 첫 번 째 키 워드 는 왼쪽 끝 점 의 블록 으로 작은 것 에서 큰 것 으로, 두 번 째 키 워드 는 오른쪽 끝 점 의 블록 으로 작은 것 에서 큰 것 으로, 세 번 째 키 워드 는 수정 시간 으로 똑 같이 작은 것 에서 큰 것 으로 한다. 일반적으로 이런 문제 블록 의 크기 는 n 23 n 을 취 하 는 경향 이 있다.^ {\ frac {2} {3}} n32. 하나의 질문 에서 새로운 질문 으로 이동 하려 면 좌우 점 의 이동 뿐만 아니 라 시간의 흐름 도 고려 해 야 합 니 다. 현재 질문 의 시간 이 이전 질문 의 시간 보다 적 으 면 시간 순서에 따라 순 서 를 역 추적 하여 복원 해 야 합 니 다. 시간 복잡 도의 증명 과 기초 모 팀 은 대동소이 합 니 다. O (n 5 3) O (n ^ {\ frac {5} {3}) O 입 니 다.(n35)。
P1903 [국가 훈련 팀] 색상 / 유지 보수 대기 열
- 문제 설명 - 하나의 서열 을 제시 하고 두 가지 조작 이 있 습 니 다. 1. 질문 구간 [l, r] [l, r] [l, r]중, 서로 다른 숫자의 개수, 2. 아래 표 가 x x x 인 숫자 를 다른 숫자 로 바 꿉 니 다. 문제 풀이 사고방식 - 하나의 수 조 를 만들어 구간 에 있 는 모든 숫자 가 나타 나 는 횟수 를 유지 합 니 다. 구간 이 확장 되 었 을 때, 현재 위치의 숫자 가 이전의 누적 횟수 가 0 이면 답 수 는 1 을 추가 합 니 다. 구간 이 축소 되 었 을 때, 현재 위치의 숫자 가 이전의 누적 횟수 에 있 으 면.숫자 가 1 이면 답 수 에 1 을 더 합 니 다. 좌우 점 이 다 이동 한 다음 에 시간 선 이동 을 고려 하여 시간 을 과거 나 미래 에서 현재 시간 으로 미 루 고 수 정 된 위치 가 질문 구간 에 있 는 지 를 고려 할 때마다 답 수 를 비슷 한 구간 확장 이나 축소 시 수정 합 니 다. 코드 -
#include
", ans[i]);
}
return 0;
}
스크롤 백 막 대
스크롤 백 모 팀 이 해결 하 는 문 제 는 일반적으로 '지속 가능 화' 의 맛 이 묻 습 니 다. 구간 두 점 의 이동 은 누적 개수 의 문제 가 아니 라 확장 전에 기 록 된 역사 버 전 을 고려 해 야 합 니 다. 예 를 들 어 길이 n n n 의 순 서 를 제시 하고 m m m 의 질문 이 있 습 니 다. 문 제 는 구간 [l, r] [l, r] [l, r] 에서 같은 숫자 로 떨 어 진 가장 먼 거리 입 니 다.
두 개의 배열 을 유지 하고 있 습 니 다. 하나의 기록 구간 에서 가장 왼쪽 에 있 는 위치, 다른 기록 이 가장 오른쪽 에 있 는 위 치 를 유지 하고 있 습 니 다. 만약 에 원래 구간 에 같은 수치 v a l val 이 세 개 포함 되 어 있다 면 구간 이 축소 되 고 두 개의 v a l val 만 남 았 을 때 세 개의 v a l val 의 중간 위 치 를 어떻게 알 수 있 습 니까? 직관 적 인 생각 은 하나의 대기 열 로 차원 을 유지 하 는 것 입 니 다.모든 v a l val 의 위 치 를 보호 합 니 다. 이렇게 하면 공간 적 인 비용 이 많이 증가 합 니 다.
모 팀 알고리즘 을 잘 사용 하 는 블록 사 고 는 비교적 적은 공간 을 사용 하 는 동시에 시간 복잡 도 를 O (n) O (n \ sqrt {n}) O (N) 로 유지 할 수 있 습 니 다.단계. 정렬 과 시퀀스 블록 을 묻 는 규칙 은 기본 모 팀 과 같 습 니 다. 유일한 차이 점 은 구간 이동 입 니 다. 구간 의 좌우 점 이 같은 블록 에 있 으 면 직접 폭력 으로 답 을 스 캔 합 니 다. 블록 크기 는 n \ sqrt {n} n 이 므 로 시간 복잡 도 는 O (n) O (\ sqrt {n}) O (n) 입 니 다.구간 의 좌우 점 이 서로 다른 블록 에 있 으 면 왼쪽 점 이 같은 블록 에 있 는 모든 질문 에 대해 우 리 는 왼쪽 점 의 위 치 를 블록 의 오른쪽 경계 에 정 하고 왼쪽 점 이 오른쪽 경계 와 문의 하 는 왼쪽 점 사이 에서 계속 이동 하도록 한다. 오른쪽 점 의 이동 은 기초 모 팀 과 같다. 우 리 는 먼저 오른쪽 점 을 이동 하여 현재 의 답 을 기록 하 자.(이 답 은 왼쪽 점 이 오른쪽 경계 에 있 을 때의 상황 을 나타 낸다)그리고 왼쪽 끝 점 을 질문 의 목표 위치 로 이동 합 니 다. 이 때 전체 질문 의 답 을 얻 을 수 있 습 니 다. 마지막 으로 왼쪽 끝 점 을 블록의 경계 가 있 는 곳 으로 거 슬러 올 라 가 가장 오른쪽 에 나타 난 위치 가 왼쪽 끝 점 에 굴 러 간 데 이 터 를 지 워 야 합 니 다. 현재 기 록 된 가장 먼 거리 도 왼쪽 끝 점 에서 왼쪽으로 확장 하기 전의 크기 로 거 슬러 올 라 갑 니 다. 현재 왼쪽 끝 점 이 있 는 블록 이 이전 질문 과 다르다 면.왼쪽 끝 점 의 시작 위 치 를 현재 블록의 오른쪽 경계 로 다시 설정 하 는 동시에 두 개의 유지 보수 그룹 을 비 워 야 합 니 다. 이 작업 은 본질 적 으로 왼쪽 끝 점 의 왕복 스크롤 일 뿐 실제 시간 복잡 도 는 O (n) O (\ sqrt {n}) O (n) 입 니 다. 따라서 전체적으로 스크롤 모 팀 과 기초 모 팀 의 시간 복잡 도 는 상수 상의 차이 일 뿐 입 니 다.
P5906 【 템 플 릿 】 막 대 를 굴 리 기 & 막 대 를 삭제 하지 않 기
- 제목 설명 - 원 제 를 보 세 요. 문제 풀이 방향 - 위 글 - 코드 를 보 세 요.
#include
", ans[i]);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
