무 타오(Mo Tao)가 개발한 이 알고리즘은 일반적으로 구간 작업을 비효율적으로 처리하는 데 사용됩니다
짧은 프레임워크, 쉽게 기억할 수 있는 템플릿 표현, 그리고 우수한 복잡도로 유명합니다
하지만 무 알고리즘이 적용되는 문제의 복잡성으로 인해 많은 템플릿 문제들이 높은 난이도 등급을 가지고 있어 초보자들이 접근하기 어렵습니다
하지만 무 알고리즘의 원리를 정말로 이해한다면 사용하는 것은 매우 간단합니다
[]사전 지식 요구사항
무 알고리즘은 상대적으로 독립적입니다. 하지만 다음과 같은 지식을 알고 있어야 합니다:
- 분할 정복의 기본 개념
- STL에서 sort 사용법 (cmp 함수 수동 작성 또는 구조체 다중 키워드 정렬을 위한 연산자 오버로딩 구현)
- 다양한 최적화 기법
- LCA(최소 공통 조상)를 위한 배수 증가/트리 분할 기법 (트리 기반 무 알고리즘에 필요)
- 값 이산화 (많은 문제에 대응하기 위해 사용)
[]기본 구현
무 알고리즘의 핵심 최적화는 분할 정복과 정렬입니다
크기가 \(n\)인 시퀀스를 \(\sqrt{n}\)개의 블록으로 나누고, 1부터 \(\sqrt{n}\)까지 번호를 매긴 후, 이를 기반으로 쿼리 구간을 정렬합니다
하나의 방법은 쿼리 구간을 왼쪽 끝점이 속한 블록의 번호로 정렬하고, 왼쪽 끝점이 속한 블록이 동일하면 오른쪽 끝점으로 정렬하는 것입니다
정렬 후에는 왼쪽과 오른쪽 포인터를 이동시키는 작업을 수행하는데, 이는 별로 유용해 보이지 않지만 실제로는 상당한 최적화를 가져옵니다
정렬의 구체적인 규칙은 다음과 같습니다
bool 비교(노드 x, 노드 y){
return x.l / 블록크기 == y.l / 블록크기 ? x.r < y.r : x.l < y.l;
}
그리고 양쪽 포인터의 이동은 실제 구간과 목표 구간을 일치시키는 과정과 같습니다
각 질의 \((l,r)\)를 목표 구간으로 볼 수 있고, 우리의 양쪽 포인터 사이의 영역은 현재 유지되는 실제 구간입니다
우리는 실제 구간 내 각 점의 기여도만 계산했지만, 각 질의는 \((l,r)\) 사이의 모든 기여도를 요구하므로, 양쪽 포인터를 이동시켜 실제 구간과 목표 구간을 일치시키고, 이동 과정에서 새로 추가된 점의 기여도를 계산하며, 더 이상 실제 구간에 포함되지 않는 점의 기여도를 제거함으로써 각 구간 질의의 답을 얻습니다
양쪽 포인터의 이동, 즉 실제 구간의 확장 및 축소에 대해 현재 답이 이미 계산되었는지, 유지할 필요가 있는지 등을 먼저 결정해야 합니다
여기서 \((l,r)\)를 한 질의로, \(L,R\)을 각각 현재의 양쪽 포인터로 설정합니다
- 구간 확장: \(L>l\) 또는 \(R<r\)일 때, 즉 목표 구간의 일부가 실제 구간에 포함되지 않을 때, 목표 구간으로 현재 포인터를 이동시킨 후 해당 점의 기여도를 추가해야 합니다
- 구간 축소: \(L<l\) 또는 \(R>r\)일 때, 즉 실제 구간의 일부 또는 전체 기여도가 이 질의에 무용지물일 때, 사용하지 않는 점에서 포인터를 이동시켜야 하므로 먼저 이 점의 기여도를 제거한 후 이동해야 합니다
구체적인 코드 구현은 다음과 같습니다:
for(int i = 1; i <= q; i ++){
while(L > 질의[i].왼쪽) 추가(-- L);
while(R < 질의[i].오른쪽) 추가(++ R);
while(L < 질의[i].왼쪽) 삭제(L ++);
while(R > 질의[i].오른쪽) 삭제(R --);
결과[질의[i].ID] = 답변;
}
[]일부 확장 기능
수정이 포함된 무 알고리즘
일반적인 무 알고리즘은 수정 작업을 지원하지 않지만, 후에 개발된 것은 수정 작업을 지원할 수 있게 되었으며, 이를 수정이 포함된 무 알고리즘이라고 합니다
수정이 포함된 무 알고리즘의 원리는 각 질의 작업에 타임스탬프를 부여하고, 해당 질의 이전까지의 모든 수정 작업이 완료되었음을 기록하는 것입니다
그런 다음 특정 구간의 질의에 대해, 그 이전에 이 구간에 대한 모든 작업을 수행하고, 그 이후에 수행된 작업은 원상태로 복원한 후 답변을 계산하면 됩니다
정렬 규칙은 일반적인 것과 유사하며, 양쪽 끝점이 속한 블록이 동일할 때만 타임스탬프에 따라 정렬하면 됩니다
수정이 포함된 무 알고리즘의 블록 크기는 일반적으로 \(n^{\frac{2}3}\)이며, \(n^{\frac{1}3}\)개의 블록으로 나뉩니다
다음은 예제 문제를 통해 설명합니다
[국가 집단팀] 색상 수 / 큐 유지
두 가지 작업이 주어집니다. 하나는 특정 위치의 숫자를 수정하는 것이고, 다른 하나는 특정 구간에 있는 본질적으로 다른 숫자의 종류 수를 세는 것입니다. 각 질의에 대해 정확한 답변을 제공해야 합니다
수정이 포함된 무 알고리즘 템플릿 문제
- 수정 작업에 대해
입력 시 각 질의 작업에 해당 수정 작업의 인덱스를 태그로 지정하여, 각 질이 수행해야 할 수정 작업이 무엇인지 표시합니다
각 질의 이전의 작업에 대해, 그 작업 위치가 질의 범위 내에 있는지 확인하고, 그렇다면 작업에 따라 추가 또는 제거합니다
각 작업을 수행한 후, 다음에 이 작업을 다시 질의할 때 반드시 이 작업을 반대로 수행해야 하며, 어떤 작업이 이전에 수행되었는지 알 수 없으므로, 각 작업 전후의 숫자를 교환합니다
- 질의 작업에 대해
각 숫자의 출현 횟수를 유지하고, 이동 과정에서 각 유형의 숫자 변경이 답변에 영향을 미치는지 여부를 판단합니다. 즉, 이전에는 없었는데 지금은 있거나, 이전에는 있었는데 지금은 없는 경우, 답변에 상응하는 작업을 수행합니다
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define 최대크기 1000100
#define 무한대 0x3f3f3f3f
#define 정수 long long
using namespace std;
char 명령;
int 배열[최대크기],답변[최대크기],크기[최대크기];
int n,m,왼쪽=2,오른쪽=1,현재,블록크기,질의수,수정수,최종답변;
struct 수정{int 위치,색상;}수정배열[최대크기];
struct 질의{int 왼쪽,오른쪽,시간,ID;}질의배열[최대크기];
int 읽기(){
int s=0,w=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-') w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=(s<<1)+(s<<3)+ch-'0',ch=getchar();
return s*w;
}
bool 비교(질의 a,질의 b){
return a.왼쪽/블록크기!=b.왼쪽/블록크기?a.왼쪽<b.왼쪽:a.오른쪽/블록크기!=b.오른쪽/블록크기?a.오른쪽<b.오른쪽:a.시간<b.시간;
}
void 추가(int x){최종답변+=(++크기[x]==1);}
void 삭제(int x){최종답변-=(--크기[x]==0);}
void 수정(int x,int 시간){
if(수정배열[시간].위치<=질의배열[x].오른쪽&&수정배열[시간].위치>=질의배열[x].왼쪽)
삭제(배열[수정배열[시간].위치]),추가(수정배열[시간].색상);
swap(배열[수정배열[시간].위치],수정배열[시간].색상);
}
int main(){
n=읽기();m=읽기();블록크기=pow(n,2.0/3);
for(int i=1;i<=n;i++) 배열[i]=읽기();
for(int i=1;i<=m;i++){
cin>>명령;
if(명령=='Q'){
질의배열[++질의수].왼쪽=읽기(),질의배열[질의수].오른쪽=읽기(),
질의배열[질의수].ID=질의수,질의배열[질의수].시간=수정수;
}
else 수정배열[++수정수].위치=읽기(),수정배열[수정수].색상=읽기();
}
sort(질의배열+1,질의배열+질의수+1,비교);
for(int i=1;i<=질의수;i++){
while(왼쪽<질의배열[i].왼쪽) 삭제(배열[왼쪽++]);
while(왼쪽>질의배열[i].왼쪽) 추가(배열[--왼쪽]);
while(오른쪽<질의배열[i].오른쪽) 추가(배열[++오른쪽]);
while(오른쪽>질의배열[i].오른쪽) 삭제(배열[오른쪽--]);
while(현재<질의배열[i].시간) 수정(i,++현재);
while(현재>질의배열[i].시간) 수정(i,현재--);
답변[질의배열[i].ID]=최종답변;
}
for(int i=1;i<=질의수;i++) printf("%lld\n",답변[i]);
return 0;
}
[]롤백 무 알고리즘
일부 문제에서는 구간 이동 시 추가 또는 삭제 작업을 구현하기 어려운 경우가 있습니다
이러한 문제를 해결하기 위해 다른 종류의 무 알고리즘인 롤백 무 알고리즘을 사용할 수 있습니다
롤백 무 알고리즘의 본질은 원래의 문제를 추가만 필요하거나 삭제만 필요한 문제로 변환하여, 한쪽 작업을 구현하기 어려운 문제를 해결하는 것입니다
따라서 롤백 무 알고리즘은 두 가지로 나뉩니다: 삭제하지 않는 무 알고리즘과 추가하지 않는 무 알고리즘
삭제하지 않는 무 알고리즘은 실제 구간이 각 질의 구간 내에 있고 어떤 요소도 포함되지 않도록 보장하며, 각 질의에 대해 양쪽 포인터를 외부로 확장한 후, 각 질의를 처리한 후 포인터를 원래 위치로 되돌리는 방식으로, 구간 확장만으로 각 질의의 답변을 처리할 수 있습니다
추가하지 않는 무 알고리즘도 마찬가지로, 실제 구간이 각 질의의 목표 구간을 포함하도록 하고, 구간을 축소하여 요소를 삭제하면 됩니다
이러한 왕복 처리 방식이 이 무 알고리즘에 롤백이라는 이름을 부여하게 되었습니다
여기서도 두 가지 예제 문제를 통해 각각 삭제하지 않는 알고리즘과 추가하지 않는 알고리즘의 구체적인 구현을 설명합니다
역사 연구
주어진 시퀀스에서, 각 점의 가중치가 출현 횟수를 곱한 최대값을 구합니다
이것은 삭제하지 않는 무 알고리즘의 템플릿 문제입니다
먼저 구간 확장이 답변에 미치는 영향을 고려해 봅시다
실제 구간에 새로운 숫자가 추가될 때, 그 출현 횟수를 1 증가시키고, 그 점의 가중치가 출현 횟수를 곱한 값이 새로운 답변이 될 수 있는지 확인할 수 있습니다. 하지만 숫자를 삭제하고, 그 숫자의 원래 가중치가 출현 횟수가 답변 크기였다면, 새로운 답변이 무엇인지 알 수 없습니다
따라서 이러한 삭제 작업을 구현하기 어려운 문제는 삭제하지 않는 무 알고리즘을 고려할 수 있습니다
먼저 이 데이터를 이산화 처리 후 작업합니다
초기에 양쪽 포인터를 각 질의의 왼쪽 끝점이 속한 블록의 오른쪽 끌의 양쪽으로 설정하고, 그 사이에 어떤 요소도 없도록 합니다(즉, \(왼쪽>오른쪽\))
이때 각 질의에 대해, 양쪽 끝점이 동일한 블록에 있는지 먼저 확인합니다. 동일한 블록에 있다면 왼쪽에서 오른쪽으로 한 번 스캔하여 직접 처리합니다
양쪽 끝점이 다른 블록에 속해 있다면, 질의의 왼쪽 끝점은 반드시 왼쪽 포인터의 왼쪽에 있고, 오른쪽 끝점은 오른쪽 포인터의 오른쪽에 있습니다. 따라서 각 질의에 대해 양쪽 포인터를 확장하여 요소를 계속 추가하여 답변을 계산한 후, 다시 초기 위치로 롤백하면 됩니다
이제 우리는 추가만 하고 삭제하지 않는 방법으로 질의를 처리할 수 있습니다
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define 최대크기 100010
#define 정수 long long
using namespace std;
int n,m,블록크기,총개수,전체;
int 답변,이전블록,결과,왼쪽=1,오른쪽;
int 블록ID[최대크기],카운트[최대크기],카운트배열[최대크기],오른쪽끝[최대크기];
int 배열[최대크기],정렬배열[최대크기],왼쪽끝[최대크기],답변배열[최대크기];
struct 질의{int 왼쪽,오른쪽,현재;}질의배열[최대크기];
int 읽기(){
int s=0,w=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-') w=1;ch=getchar();}
while(ch>='0'&&ch<='9') s=(s<<1)+(s<<3)+ch-'0',ch=getchar();
return s*w;
}
void 삭제(int x){--카운트배열[배열[x]];}
void 추가(int x,int& 답변){
++카운트배열[배열[x]];답변=max(답변,정렬배열[배열[x]]*카운트배열[배열[x]]);
}
bool 비교(질의 a,질의 b){
return 블록ID[a.왼쪽]^블록ID[b.왼쪽]?블록ID[a.왼쪽]<블록ID[b.왼쪽]:a.오른쪽<b.오른쪽;
}
void 구축(){
n=읽기();m=읽기();
블록크기=sqrt(n+0.5);총개수=(!n%블록크기)?n/블록크기:n/블록크기+1;
for(int i=1;i<=n;i++)배열[i]=읽기(),정렬배열[i]=배열[i];
sort(정렬배열+1,정렬배열+n+1);전체=unique(정렬배열+1,정렬배열+n+1)-정렬배열-1;
for(int i=1;i<=n;i++)배열[i]=lower_bound(정렬배열+1,정렬배열+전체+1,배열[i])-정렬배열;
for(int i=1;i<=총개수;i++)왼쪽끝[i]=(i-1)*블록크기+1,오른쪽끝[i]=min(i*블록크기,n);
for(int i=1;i<=총개수;i++)for(int j=왼쪽끝[i];j<=오른쪽끝[i];j++)블록ID[j]=i;
}
int main(){
구축();
for(int i=1;i<=m;i++)
질의배열[i].왼쪽=읽기(),질의배열[i].오른쪽=읽기(),질의배열[i].현재=i;
sort(질의배열+1,질의배열+m+1,비교);
for(int i=1;i<=m;i++){
if(블록ID[질의배열[i].왼쪽]==블록ID[질의배열[i].오른쪽]){
for(int j=질의배열[i].왼쪽;j<=질의배열[i].오른쪽;j++) ++카운트[배열[j]];
for(int j=질의배열[i].왼쪽;j<=질의배열[i].오른쪽;j++)
답변배열[질의배열[i].현재]=max(답변배열[질의배열[i].현재],카운트[배열[j]]*정렬배열[배열[j]]);
for(int j=질의배열[i].왼쪽;j<=질의배열[i].오른쪽;j++) --카운트[배열[j]];
continue;
}
if(블록ID[질의배열[i].왼쪽]!=이전블록){
while(오른쪽>오른쪽끝[블록ID[질의배열[i].왼쪽]]) 삭제(오른쪽--);
while(왼쪽<오른쪽끝[블록ID[질의배열[i].왼쪽]]+1) 삭제(왼쪽++);
답변=0;이전블록=블록ID[질의배열[i].왼쪽];
}
while(오른쪽<질의배열[i].오른쪽) 추가(++오른쪽,답변);int 임시왼쪽=왼쪽;결과=답변;
while(임시왼쪽>질의배열[i].왼쪽) 추가(--임시왼쪽,결과);답변배열[질의배열[i].현재]=결과;
while(임시왼쪽<왼쪽) 삭제(임시왼쪽++);
}
for(int i=1;i<=m;i++) printf("%lld\n",답변배열[i]);
return 0;
}
Rmq 문제 / mex
주어진 시퀀스에서, 각 질의 구간의 mex(가장 작은 자연수로 나타나지 않은 값)를 구합니다
이것은 추가하지 않는 무 알고리즘의 템플릿 문제입니다
마찬가지로, 구간 확장 또는 축소 시 새로운 숫자를 추가하거나 삭제하는 것이 답변에 미치는 영향을 고려해 봅시다
명확하게 말하자면, 새로운 숫자를 추가할 때 그 숫자가 현재 답변이면 답변을 변경해야 하지만, 새로운 답변의 위치를 알 수 없습니다. 하지만 숫자를 삭제할 때는, 그 숫자와 현재 답변의 크기 관계와 그 출현 횟수만 판단하면 됩니다
따라서 삭제 작업만 지원하는 무 알고리즘을 유지해야 합니다
만약 삭제 작업을 지원한다면, 초기 양쪽 포인터는 현재 질의 구간을 포함해야 합니다. 왼쪽 포인터를 질의의 왼쪽 끝점이 속한 블록의 왼쪽 끝으로, 오른쪽 포인터를 \(n\) 노드로 설정한 후, 질의의 양쪽 끝점이 동일한 블록에 있는지 확인합니다. 동일한 블록에 있다면 한 번 스캔하여 답변을 찾고, 동일한 블록에 속하지 않으면 계속해서 삭제합니다
여기서 작은 결론이 있습니다: 가장 작은 자연수를 찾고 있고 시퀀스의 최대 길이가 \(n\)이므로, 답변은 반드시 \([1,n+1]\) 범위에 있으며, 이 범위에 없는 숫자는 직접 고려하지 않거나 초기에 \(n+1\)보다 큰 숫자를 \(n+1\)로 할당할 수 있습니다
나머지 작업은 삭제하지 않는 무 알고리즘과 유사하며, 삭제, 롤백, 다시 삭제, 다시 롤백의 과정입니다
구체적인 내용은 코드를 참조하세요
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define 최대크기 1000100
#define 정수 long long
using namespace std;
int n,m,블록크기,총개수,현재;
int 답변,이전블록,결과,왼쪽=1,오른쪽=n,전체;
int 블록ID[최대크기],카운트[최대크기],카운트배열[최대크기],오른쪽끝[최대크기];
int 배열[최대크기],정렬배열[최대크기],왼쪽끝[최대크기],답변배열[최대크기];
struct 질의{int 왼쪽,오른쪽,현재;}질의배열[최대크기];
int 읽기(){
int s=0,w=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-') w=1;ch=getchar();}
while(ch>='0'&&ch<='9') s=(s<<1)+(s<<3)+ch-'0',ch=getchar();
return s*w;
}
bool 비교(질의 a,질의 b){
return 블록ID[a.왼쪽]^블록ID[b.왼쪽]?블록ID[a.왼쪽]<블록ID[b.왼쪽]:a.오른쪽>b.오른쪽;
}
void 추가(int x){
if(배열[x]>n+1) return;카운트배열[배열[x]]++;
}
void 삭제(int x, int &최소값){
if(배열[x]>n+1) return;카운트배열[배열[x]]--;
if(!카운트배열[배열[x]]) 최소값=min(최소값,배열[x]);
}
void 구축(){
n=읽기();m=읽기();
블록크기=sqrt(n+0.5);총개수=(!n%블록크기)?n/블록크기:n/블록크기+1;
for(int i=1;i<=n;i++)배열[i]=읽기(),정렬배열[i]=배열[i];
for(int i=1;i<=n;i++)카운트배열[배열[i]]+=(배열[i]<=n+1);while(카운트배열[답변])답변++;
for(int i=1;i<=총개수;i++)왼쪽끝[i]=(i-1)*블록크기+1,오른쪽끝[i]=min(i*블록크기,n);
for(int i=1;i<=총개수;i++)for(int j=왼쪽끝[i];j<=오른쪽끝[i];j++)블록ID[j]=i;
}
int main(){
구축();
for(int i=1;i<=m;i++)
질의배열[i].왼쪽=읽기(),질의배열[i].오른쪽=읽기(),질의배열[i].현재=i;
sort(질의배열+1,질의배열+m+1,비교);
for(int i=1;i<=m;i++){
if(블록ID[질의배열[i].왼쪽]==블록ID[질의배열[i].오른쪽]){
for(int j=질의배열[i].왼쪽;j<=질의배열[i].오른쪽;j++) 카운트[배열[j]]+=(배열[j]<=n+1);
int 임시=0;while(카운트[임시]) 임시++;답변배열[질의배열[i].현재]=임시;
for(int j=질의배열[i].왼쪽;j<=질의배열[i].오른쪽;j++) 카운트[배열[j]]-=(배열[j]<=n+1);
continue;
}
if(블록ID[질의배열[i].왼쪽]!=이전블록){
while(오른쪽<n) 추가(++오른쪽);
while(왼쪽<왼쪽끝[블록ID[질의배열[i].왼쪽]]) 삭제(왼쪽++,답변);
현재=답변;이전블록=블록ID[질의배열[i].왼쪽];
}
while(오른쪽>질의배열[i].오른쪽) 삭제(오른쪽--,현재);
결과=현재;int 임시왼쪽=왼쪽;
while(임시왼쪽<질의배열[i].왼쪽) 삭제(임시왼쪽++,결과);
while(임시왼쪽>왼쪽) 추가(--임시왼쪽);
답변배열[질의배열[i].현재]=결과;
}
for(int i=1;i<=m;i++) printf("%lld\n",답변배열[i]);
return 0;
}
[]트리 기반 무 알고리즘
그 이름에서 알 수 있듯이, 트리에서 실행되는 무 알고리즘이며, 대부분 수정이 포함된 버전이나 일반 버전을 실행합니다
차이점은 일반적인 무 알고리즘은 시퀀스에서 실행되지만, 트리 기반 무 알고리즘은 트리에서 실행된다는 것입니다
트리의 숫자를 시퀀스에 매핑하는 무엇이 있는지 생각해 봅시다
우리가 평소에 작성하는 트리 분할은 트리의 정보를 선형으로 변환한 후 선분 트리 등을 실행하기 위한 것입니다. 그리고 사용하는 것은 dfs 순서입니다
물론 유사하게 트리 관계를 처리할 수 있는 오일러 순서와 같은 시퀀스도 사용할 수 있습니다
따라서 우리는 일반적으로 dfs 순서나 오일러 순서에서 무 알고리즘을 실행하며, 이것이 바로 트리 기반 무 알고리즘입니다
물론 몇 가지 세부 사항이 있으며, 여기서 두 가지 예제 문제를 설명합니다:
트리 및 질의
\(n\)개의 노드를 가진 트리가 주어지며, 루트 노드는 1입니다. 각 노드에는 색상 \(c_i\)가 있습니다. \(m\)번의 작업이 있습니다. 작업의 종류는 하나입니다:
u k: \(u\)를 루트로 하는 서브트리에서, 출현 횟수가 \(\ge k\)인 색상이 몇 가지인지 질의합니다.
만약 시퀀스의 특정 구간에서 색상 수를 묻는다면, 이는 일반적인 무 알고리즘 템플릿입니다
하지만 이것은 트리에서 이루어지므로, 방금 설명한 대로 dfs 순서로 변환하여 작업하면 됩니다
이 구현은 비교적 간단하며, 코드를 보면 쉽게 이해할 수 있습니다
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define 최대크기 1000100
#define 무한대 0x3f3f3f3f
//#define 정수 long long
using namespace std;
int n,m,블록크기,질의수,총개수,최종답변,전체,왼쪽=1,오른쪽;
int dfs순서[최대크기],크기[최대크기],사용[최대크기],결과[최대크기];
int 부모[최대크기],정렬배열[최대크기],오른쪽끝[최대크기],카운트[최대크기],To[최대크기];
int 깊이[최대크기],상단[최대크기],자식[최대크기],st[최대크기];
int head[최대크기],pre[최대크기],배열[최대크기],답변[최대크기];
struct 간선{int 시작,끝,다음;}간선배열[최대크기];
struct 질의{int 왼쪽,오른쪽,k,현재;}질의배열[최대크기];
int 읽기(){
int s=0,w=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-') w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=(s<<1)+(s<<3)+ch-'0',ch=getchar();
return s*w;
}
void 간선추가(int 시작,int 끝){
간선배열[++총개수].시작=시작;간선배열[총개수].끝=끝;
간선배열[총개수].다음=head[시작];head[시작]=총개수;
}
void 추가(int x){++카운트[x];++결과[카운트[x]];}
void 삭제(int x){--결과[카운트[x]];--카운트[x]}
bool 비교(질의 a,질의 b){
return (a.왼쪽/블록크기)^(b.왼쪽/블록크기)?a.왼쪽<b.왼쪽:a.오른쪽<b.오른쪽;
}
void dfs(int u,int 부모){
dfs순서[u]=++총개수;pre[총개수]=배열[u];크기[u]=1;
for(int i=head[u];i;i=간선배열[i].다음){
int 끝=간선배열[i].끝;
if(끝==부모) continue;
dfs(끝,u);
크기[u]+=크기[끝];
}
}
void 질의(){
for(int i=1,u,k;i<=m;i++){
u=읽기();k=읽기();
질의배열[i].왼쪽=dfs순서[u];
질의배열[i].오른쪽=dfs순서[u]+크기[u]-1;
질의배열[i].k=k;질의배열[i].현재=i;
}
}
void 구축(){
n=읽기();m=읽기();블록크기=sqrt(n+0.5);
for(int i=1;i<=n;i++)정렬배열[i]=배열[i]=읽기();
sort(정렬배열+1,정렬배열+n+1);전체=unique(정렬배열+1,정렬배열+n+1)-정렬배열-1;
for(int i=1;i<=n;i++)배열[i]=lower_bound(정렬배열+1,정렬배열+전체+1,배열[i])-정렬배열;
for(int i=1,시작,끝;i<=n-1;i++){
시작=읽기();끝=읽기();
간선추가(시작,끝);간선추가(끝,시작);
}
dfs(1,0);질의();sort(질의배열+1,질의배열+m+1,비교);
}
int main(){
구축();
for(int i=1;i<=m;i++){
while(왼쪽<질의배열[i].왼쪽) 삭제(pre[왼쪽++]);
while(왼쪽>질의배열[i].왼쪽) 추가(pre[--왼쪽]);
while(오른쪽<질의배열[i].오른쪽) 추가(pre[++오른쪽]);
while(오른쪽>질의배열[i].오른쪽) 삭제(pre[오른쪽--]);
답변[질의배열[i].현재]=결과[질의배열[i].k];
}
for(int i=1;i<=m;i++) printf("%d\n",답변[i]);
return 0;
}
COT2 - 트리에서의 개수 II
\(n\)개의 노드를 가진 트리가 주어지며, 각 노드에는 색상이 있습니다. \(m\)번의 질의가 주어지며, 각 질의에는 \(u,v\)가 주어지고, \(u,v\) 사이 경로에 있는 노드의 다른 색상 수를 답변합니다
이 문제는 방금 전 문제와 약간 다릅니다. 전 문제는 서브트리 내의 숫자를 질의하는 것이고, 이 문제는 임의의 두 숫자 사이의 색상 수입니다.
dfs 순서로는 이 문제를 처리할 수 없습니다. 두 점의 LCA 기여도를 처리할 수 없기 때문입니다. 하지만 오일러 순서로는 처리할 수 있습니다
오일러 순서의 핵심 개념은: 점 \(i\)에 접근할 때 시퀀스에 추가하고, \(i\)의 서브트리를 접근한 후, 완료했을 때 다시 \(i\)를 시퀀스에 추가하는 것입니다
따라서 \(i\) 점을 루트로 하는 서브트리의 오일러 순서의 양쪽 끝점은 반드시 \(i\) 점의 오일러 순서입니다
그렇다면 이 문제를 어떻게 처리할까요? 예를 들어보겠습니다
이 트리의 오일러 순서는 1 2 3 4 4 5 5 6 6 3 7 7 2 1입니다
여기서 \(st_i\)가 점 \(i\)에 접근할 때 시퀀스에 추가되는 시간을, \(ed_i\)가 역추적하여 점 \(i\)를 통과할 때 시퀀스에 추가되는 시간을 나타내도록 합니다
먼저 \(st_x<st_y\)라고 가정합니다
여기에는 두 가지 경우가 있습니다
- 만약 \(lca(x,y) = x\)라면, 이 경우 \(x,y\)는 동일한 체인에 있습니다. 그러면 \(st_x\)에서 \(st_y\)까지의 구간에서, 일부 점은 두 번 나타나고, 일부 점은 나타나지 않았습니다. 이 점들은 답변에 기여하지 않으므로, 한 번만 나타난 점만 세면 됩니다
- 만약 \(lca(x,y)≠x\)라면, 이 경우 \(x,y\)는 다른 서브트리에 있습니다. 위 방법대로 \(ed_x\)에서 \(st_y\) 구간 내의 점만 세면 됩니다
예를 들어
질의가 2,6일 때, \((st_2,st_6)=\) 2 3 4 4 5 5 6이며, 여기서 4,5라는 두 점은 모두 두 번 나타나므로 답변에 포함하지 않습니다
질의가 4,7일 때, \((ed_4,st_7)=\) 4 5 5 6 6 3 7이지만 LCA를 세지 않았으므로 LCA를 특별히 처리해야 합니다
그러면 문제가 해결됩니다. 나머지는 코드를 참조하세요
#include<queue>
#include<cmath>
#include<vector>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<iostream>
#include<algorithm>
#define 최대크기 1000100
#define 무한대 0x3f3f3f3f
//#define 정수 long long
using namespace std;
int n,m,블록크기,질의수,총개수,최종답변,전체,왼쪽=1,오른쪽;
int dfs순서[최대크기],크기[최대크기],사용[최대크기];
int 부모[최대크기],정렬배열[최대크기],오른쪽끝[최대크기],카운트[최대크기];
int 깊이[최대크기],상단[최대크기],자식[최대크기],st[최대크기];
int head[최대크기],pre[최대크기],배열[최대크기],답변[최대크기];
struct 간선{int 시작,끝,다음;}간선배열[최대크기];
struct 질의{int 왼쪽,오른쪽,현재,lca;}질의배열[최대크기];
vector<int> v[최대크기];
int 읽기(){
int s=0,w=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-') w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=(s<<1)+(s<<3)+ch-'0',ch=getchar();
return s*w;
}
bool 비교(질의 a,질의 b){
return st[a.왼쪽]^st[b.왼쪽]?st[a.왼쪽]<st[b.왼쪽]:a.오른쪽<b.오른쪽;
}
void 간선추가(int 시작,int 끝){
간선배열[++총개수].시작=시작;간선배열[총개수].끝=끝;
간선배열[총개수].다음=head[시작];head[시작]=총개수;
}
void dfs1(int u,int 부모){
깊이[u]=깊이[부모]+1;
크기[u]=1;this->부모[u]=부모;
dfs순서[u]=++총개수;pre[총개수]=u;
for(int i=head[u];i;i=간선배열[i].다음){
int 끝=간선배열[i].끝;
if(끝==부모) continue;
dfs1(끝,u);크기[u]+=크기[끝];
if(크기[자식[u]]<크기[끝]) 자식[u]=끝;
}
오른쪽끝[u]=++총개수;pre[총개수]=u;
}
void dfs2(int u,상단){
상단[u]=상단;
if(자식[u]) dfs2(자식[u],상단);
for(int i=head[u];i;i=간선배열[i].다음){
int 끝=간선배열[i].끝;
if(�음==부모[u]||끝==자식[u]) continue;
dfs2(끝,끝);
}
}
int LCA(int x,int y){
while(상단[x]!=상단[y]){
if(깊이[상단[x]] < 깊이[상단[y]]) swap(x,y);
x=부모[상단[x]];
}
return 깊이[x]<깊이[y]?x:y;
}
void 질의(){
for(int i=1,시작,끝;i<=m;i++){
시작=읽기();끝=읽기();
if(dfs순서[시작]>dfs순서[끝]) swap(시작,끝);
int lca=LCA(시작,끝);질의배열[i].현재=i;
if(시작==lca) 질의배열[i].왼쪽=dfs순서[시작],질의배열[i].오른쪽=dfs순서[끝];
else 질의배열[i].왼쪽=오른쪽끝[시작],질의배열[i].오른쪽=dfs순서[끝],질의배열[i].lca=lca;
}
}
void 구축(){
n=읽기();m=읽기();블록크기=sqrt(n+0.5);
for(int i=1;i<=n<<1;i++) st[i]=i/블록크기+1;
for(int i=1;i<=n;i++) 배열[i]=읽기(),정렬배열[i]=배열[i];
sort(정렬배열+1,정렬배열+n+1);전체=unique(정렬배열+1,정렬배열+n+1)-정렬배열-1;
for(int i=1;i<=n;i++)배열[i]=lower_bound(정렬배열+1,정렬배열+전체+1,배열[i])-정렬배열;
for(int i=1,시작,끝;i<=n-1;i++){
시작=읽기();끝=읽기();
간선추가(시작,끝);간선추가(끝,시작);
}
dfs1(1,0);dfs2(1,1);
질의();sort(질의배열+1,질의배열+m+1,비교);
}
void 추가(int x){최종답변+=(++카운트[x]==1);}
void 삭제(int x){최종답변-=(--카운트[x]==0);}
void 처리(int x){사용[x]?삭제(배열[x]):추가(배열[x]);사용[x]^=1;}
int main(){
구축();
for(int i=1;i<=m;i++){
while(왼쪽<질의배열[i].왼쪽) 처리(pre[왼쪽++]);
while(왼쪽>질의배열[i].왼쪽) 처리(pre[--왼쪽]);
while(오른쪽<질의배열[i].오른쪽) 처리(pre[++오른쪽]);
while(오른쪽>질의배열[i].오른쪽) 처리(pre[오른쪽--]);
if(질의배열[i].lca) 처리(질의배열[i].lca);
답변[질의배열[i].현재]=최종답변;
if(질의배열[i].lca) 처리(질의배열[i].lca);
}
for(int i=1;i<=m;i++) printf("%d\n",답변[i]);
return 0;
}
[]복잡도 증명
구간 정렬
구조체를 생성하고 sort를 한 번 실행하면 됩니다. 평균 복잡도는 \(O(n\log n)\)입니다.
왼쪽 포인터의 이동
각 블록 \(i\)에 \(x_i\)개의 왼쪽 끝점이 분포해 있다고 가정합니다 무 알고리즘의 추가 및 삭제 작업 복잡도는 \(O(1)\)이므로, 블록 \(i\)를 처리하는 최악의 시간 복잡도는 \(O(x_i\sqrt n)\)이며, 포인터가 전체 블록을 가로지르는 시간 복잡도는 \(O(\sqrt{n})\)입니다. 최악의 경우 \(n\)번 가로질러야 합니다 전체 복잡도는 \(O(\sum{x_in\sqrt n}+n\sqrt n)=O(n\sqrt n)\)입니다
오른쪽 포인터의 이동
각 블록 \(i\)에 \(x_i\)개의 왼쪽 끝점이 분포해 있다고 가정합니다. 왼쪽 끝점이 동일한 블록에 있는 구간들은 오른쪽 끝점이 정렬되어 있으므로, 이 \(x_i\)개의 구간에 대해 오른쪽 끝점은 최대 전체 시퀀스를 가로지르는 데 \(O(n)\)의 시간이 필요합니다 (최악의 경우). 총 \(n\sqrt n\)개의 블록이 있으므로 전체 복잡도는 \(O(n\sqrt n)\)입니다
여기서 무 알고리즘의 전체 시간 복잡도는 \(O(n\sqrt n)+O(n\sqrt n)+O(n\log n)=O(n\sqrt n)\)임을 알 수 있습니다
정렬 전과 비교하면 하나의 제곱근이 감소하여 복잡도가 크게 개선됩니다
[]최적화 방법
현재는 홀수/짝수성 최적화만 알고 있으며, 나중에 학습하면 보충하겠습니다
현재 블록의 모든 질의가 완료된 후, 일반적인 무 알고리즘 방법에 따라 다음 블록을 처리할 때 오른쪽 포인터를 다시 이동시킵니다
중간의 질의를 건너뛰어 불필요한 낭비를 초래합니다
만약 돌아오는 과정에서 이들을 처리하면 시간 복잡도가 훨씬 개선됩니다
구체적으로는 블록을 홀수와 짝수로 나누고, 홀수 블록은 왼쪽에서 오른쪽으로, 짝수 블록은 오른쪽에서 왼쪽으로 스캔합니다
bool 비교(노드 x, 노드 y){
return (x.왼쪽 / 블록크기) ^ (y.왼쪽 / 블록크기) ? x.왼쪽 < y.왼쪽 : ((x.왼쪽 / 블록크기) & 1) ? x.오른쪽 < y.오른쪽 : x.오른쪽 > y.오른쪽;
}
또한, 블록 크기를 지정하는 방법으로 최적화할 수 있지만, 이는 안정적이지 않습니다
일반적인 경우에는 \(\sqrt n\)개의 블록으로 나누는 것을 선호하지만, 질의 수 \(m\)와 구간 길이 \(n\)의 범위 차이가 너무 크면 이 효율은 떨어집니다. 범위 차이에 따라 블록 크기를 적절히 늘리거나 줄여야 합니다
추가: 각종 무 알고리즘의 시간 복잡도는 일관되지 않으며, 다소 추상적이므로 더 자세한 내용은 OI Wiki를 참조하세요
[]예제 문제
[국가 집단팀] 소Z의 양말 소B의 질의 시퀀스에서 다른 것 찾기 [CQOI2018] XOR 시퀀스 【템플릿】롤백 무 알고리즘 & 삭제하지 않는 무 알고리즘 [WC2013] 사탕 공원