주석 나무 매듭

정말 누 워 있 습 니 다. RE 가 가득 한 날 입 니 다. 목 표를 달성 하지 못 했 습 니 다. 어제 닦 은 주석 나 무 를 포함 하여 모두 다섯 개 입 니 다. 입문 한 셈 입 니 다.
주석 나 무 는 접두사 라 고 볼 수 있 습 니 다. 모든 숫자 가 나타 나 는 횟수 (당연히 이산 화 되 어야 합 니 다) 를 나타 내 는 것 입 니 다. 선분 나무 와 유사 한 건설 법 은 공간 을 절약 하기 위해 지속 가능 한 선분 나무 와 같 습 니 다. 이렇게 처음에 빈 나 무 를 만 들 었 는데 매번 에 지난 나 무 를 바탕 으로 수정 하 는 것 과 같 습 니 다. 공간 은 O (n log n) 입 니 다.(여전히 크 구나!!!) 접두사 와 아주 비슷 하 다.
이렇게 해서 우 리 는 구간 [l, r] 의 k 작은 값 을 조회 할 때 l - 1 과 r 에서 출발 하여 균형 트 리 와 유사 한 방법 을 찾 습 니 다. 코드 를 구체 적 으로 보면 좋 습 니 다. 복잡 도 O (log n) 의 것 입 니 다.
수정 작업 에 가입 하면 어 떡 하 죠?
접두사 와 수정 이 있 는 접두사 와 트 리 배열 을 사용 해 야 한 다 는 것 이 분명 하 다. 그러면 우리 가 수정 한 주석 트 리 도 트 리 배열 의 사상 으로 유지 할 수 있 을 까? 답 은 긍정 적 이다.
이렇게 되면 수정 할 때마다 O (log n) 주석 트 리 를 수정 해 야 합 니 다. 공간 복잡 도 는 O (n log ^ 2 n) 가 됩 니 다. 조회 할 때 조회 해 야 할 모든 하위 트 리 (log n 등급) 를 미리 처리 한 다음 에 같이 아래로 조회 하면 됩 니 다. 복잡 도 O (log ^ 2 n).
bzoj3524
의장 나무 누 드 문 제 를 풀 고 템 플 릿 을 연습 하 는 것 은 바로 k 소 수 를 조회 한 다음 에 횟수 를 판단 하면 된다.

#include
#include
#include
#include
#include
#include
#define maxn 500010
#define maxm 10000010

using namespace std;

struct yts
{
	int x,id;
}a[maxn];

int lch[maxm],rch[maxm],cnt[maxm],root[maxn];
int n,f[maxn],T,tot;

bool cmp(yts a,yts b)
{
	return a.xk) return query(lch[root1],lch[root2],l,mid,k);
	else if (cnt[rch[root2]]-cnt[rch[root1]]>k) return query(rch[root1],rch[root2],mid+1,r,k);
	else return 0;
}

int main()
{
	scanf("%d%d",&n,&T);
	for (int i=1;i<=n;i++) scanf("%d",&a[i].x);
	for (int i=1;i<=n;i++) a[i].id=i;
	sort(a+1,a+n+1,cmp);
	int num=1;f[a[1].id]=1;
	for (int i=2;i<=n;i++)
	{
	  if (a[i].x!=a[i-1].x) num++;
	  f[a[i].id]=num;
	}
	tot=0;root[0]=lch[0]=rch[0]=cnt[0]=0;
	for (int i=1;i<=n;i++)
	  root[i]=modify(root[i-1],1,num,f[i]);
	while (T--)
	{
		int l,r;
		scanf("%d%d",&l,&r);
		int ans=query(root[l-1],root[r],1,num,(r-l+1)/2);
		printf("%d
",ans);
	}
	return 0;
}

bzoj1901
수 정 된 구간 k 가 작 습 니 다. 트 리 세트 주석 트 리 가 해결 되 었 습 니 다. 주의 공간 은 O (n log ^ 2 n + m log ^ 2 n) 입 니 다. 처음에는 O (n log n) 가 n 개의 주석 트 리 를 만 들 고 트 리 배열 은 변화 만 유지 하면 됩 니 다. 이 문 제 는 이러한 알고리즘 을 쓰 지 않 았 지만 뒤에 응용 되 어 공간 복잡 도 는 O (n log n + m log ^ 2 n) 로 최적화 되 었 습 니 다.그리고 조회 할 때 조회 할 나 무 를 모두 꺼 내 서 함께 아래 를 찾 아 보 세 요.

#include
#include
#include
#include
#include
#include
#include

bzoj2588
이번 에는 수정 되 지 않 은 나무 위 에 k 가 작 아서 나무 모양 의 배열 을 사용 하지 않 아 도 됩 니 다. 사실은 이 문 제 는 주석 나 무 를 나무 위 에 직접 세 울 수 있 습 니 다. 제 가 쓴 것 은 주석 나 무 를 dfs 순서 에 세 우 는 것 입 니 다. 이렇게 완전히 선형 문제 로 바 꿀 수 있 습 니 다. 그러나 문제 가 발생 할 수 있 습 니 다. 주의: 매번 4 그루 의 나 무 를 뜯 는 조회, root [x], root [y], root [lca (x, y)], root [fa [lca (x, y)]] 라 고 썼 습 니 다. 처음에 root 로 썼 습 니 다.[lca (x, y) - 1], RE 를 발 견 했 습 니 다. 나중에 생각해 보 니 잘못된 것 입 니 다. 왜냐하면 앞의 스 택 노드 도 '복잡 도 O (n log n)' 라 고 할 수 있 기 때 문 입 니 다. 그리고 주석 트 리 를 만 들 때 스 택 순 서 를 처리 해 야 합 니 다. 그렇지 않 으 면 뒤의 주석 트 리 에 영향 을 줄 수 있 습 니 다.

#include
#include
#include
#include
#include
#include
#define maxn 8001000
#include

using namespace std;

struct yts
{
	int x,id;
}a[100010];

int cnt[maxn],lch[maxn],rch[maxn];
int root[100010],e[100010],f[100010];
int head[100010],next[200010],to[200010];
int fa[100010][21],dep[100010],in[100010],out[100010],w[100010],rank[100010];
int b[5];
vector c[100010];
int num,tot,n,T,mx,num1,z;

bool cmp(yts a,yts b)
{
	return a.x=0;i--)
	  if (d&(1<dep[y]) x=go_up(x,dep[x]-dep[y]);
	else y=go_up(y,dep[y]-dep[x]);
	if (x==y) return x;
	for (int i=19;i>=0;i--)
	  if (fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
	return fa[x][0];
}

int modify(int pre,int l,int r,int x,int f)
{
	int now=++tot;
	if (l==r)
	{
		cnt[now]=cnt[pre]+f;lch[now]=rch[now]=0;
	}
	else
	{
		int mid=(l+r)/2;
		if (x<=mid)
		{
			rch[now]=rch[pre];lch[now]=modify(lch[pre],l,mid,x,f);
		}
		else
		{
			lch[now]=lch[pre];rch[now]=modify(rch[pre],mid+1,r,x,f);
		}
		cnt[now]=cnt[lch[now]]+cnt[rch[now]];
	}
	return now;
}

int query(int l,int r,int k)
{
	if (l==r) return l;
	int sum=cnt[lch[b[1]]]+cnt[lch[b[2]]]-cnt[lch[b[3]]]-cnt[lch[b[4]]];
	int mid=(l+r)/2; 
	if (sum>=k)
	{
		for (int i=1;i<=4;i++) b[i]=lch[b[i]];
		return query(l,mid,k);
	}
	else
	{
		for (int i=1;i<=4;i++) b[i]=rch[b[i]];
		return query(mid+1,r,k-sum);
	}
}

int main()
{
	scanf("%d%d",&n,&T);
	for (int i=1;i<=n;i++) scanf("%d",&a[i].x);
	//    
	for (int i=1;i<=n;i++) a[i].id=i;
	sort(a+1,a+n+1,cmp);
	mx=1;f[a[1].id]=1;rank[1]=a[1].x;
	for (int i=2;i<=n;i++)
	{
	  if (a[i].x!=a[i-1].x) rank[++mx]=a[i].x;
	  f[a[i].id]=mx;
	}
	//      
	for (int i=1;i

bzoj1146
가장 병 에 걸 린 문 제 는 하나 도 없고 수정 나무 에 k 번 째 로 크 고 공간 도 걸린다.
먼저 카드 공간 을 관리 하지 않 고 dfs 순서에 따라 주석 나 무 를 만 들 고 나무 모양 의 배열 로 유지 한 다음 에 k 번 째 크기 를 k 번 째 로 작 게 만 듭 니 다. 이 단 계 는 이전 문제 와 유사 합 니 다. 카드 공간 에 대해 너무 병 이 났 습 니 다. 먼저 나무 에 주석 나 무 를 만 든 다음 에 나무 모양 의 배열 은 변 화 량 을 유지 한 다음 에 물 어 볼 때마다 원래 의 값 을 문의 나무 에 넣 어야 합 니 다.

#include
#include
#include
#include
#include
#include
#include

bzoj3932
좋 은 것 을 찾 은 셈 입 니 다. 이 문 제 는 접두사 와 접 두 사 를 유지 해 야 합 니 다. 그리고 어 려 운 것 이 없습니다. 앞 에 오래 조정 한 후에 야 접두사 와 접 두 사 를 유지 해 야 한 다 는 것 을 알 게 되 었 습 니 다. k 가 작은 것 을 직접 찾 는 것 이 아니 라 바로 하하 하 는 것 을 알 게 되 었 습 니 다.

#include
#include
#include
#include
#include
#include
#include
#include

선형 무 수정 에서 선형 유 수정, 나무 에 수정 이 없 는 것 부터 나무 에 수정 이 있 는 것 까지 특수 한 양 을 유지 하 는 것 까지 주석 나무 도 많이 배 운 셈 입 니 다. 주의사항 은 아래 에 쓰 여 있 습 니 다.
1. 문 제 를 풀 때 특히 공간 제한 에 주의해 야 한다. 수 정 된 문제 에 대해 처음에 나 무 를 만 들 때 공간 을 최적화 할 수 있다.
2. 구간 감법 을 만족 시 키 는 양 은 주석 나무 로 지 킬 수 있 을 것 같 지만 이런 문 제 를 본 적 이 없 는 것 같 습 니 다. 주석 나 무 는 모두 k 번 째 로 작 습 니 다.!
3. 트 리 배열 주석 트 리 를 설치 할 때 검색 할 트 리 를 모두 추출 한 다음 에 같이 아래로 조회 합 니 다.
4. 나무 에 주석 나 무 를 짓 는 것 과 dfs 순서 에 주석 나 무 를 짓 는 것 은 등가 이 며 가능 한 한 나무 에 짓 는 다.
5. dfs 순서 와 트 리 체인 분할 의 차 이 를 주의 하고 dfs 순 서 는 지원 구간 감법 의 양 을 유지 할 수 있 습 니 다.
6. 수 정 된 문제 에 대한 통 제 는 주로 트 리 배열 에 대한 이해 이 고 트 리 배열 이 유지 하 는 것 이 무엇 인지 알 아야 한다.
이렇게 하 자. 내일 배낭 9 강 을 배우 고 주석 나 무 를 몇 문제 풀 어 복습 하 자.