낙 곡 P3605 [USACO17JAN] Promotion Counting 승진 자 계수 - 트 리 배열, 가중치 선분 트 리

이 문제 n ^ 2 의 알고리즘 역시 usaco 의 테스트 수가 너무 기 똥 차 서 폭력 이 70 점 을 주 었 다 고 생각 합 니 다.이 문 제 는 실제 적 으로 이전 문제 와 유사 하 며, 실제 적 으로 나무의 역 서 를 구하 기 때문에 dfs 순서 와 나무 모양 배열 을 결합 합 니 다.먼저 데 이 터 를 이산 화하 다.먼저 값 을 한 번 구하 고, 검색 한 후에 다시 한 번 값 을 구하 면, 양자 의 차 이 는 바로 이 하위 나무의 역순 이다.

#include 
#include 
#include
using namespace  std;

const int maxn = 1e5+10;

int n,m,b[maxn],head[maxn],cur=1,ans[maxn],t[maxn];
struct EDGE {
	int to,next;
} edge[maxn];
void add(int u,int v) {
	edge[cur].to=v;
	edge[cur].next=head[u];
	head[u]=cur++;
}
struct COW {
	int v,id;
} a[maxn];
bool cmp(COW x,COW y) {
	return x.v>y.v;
};
int lowbit(int x) {
	return x&-x;
}
void update(int x,int v) {
	for(; x0; i=edge[i].next)
		dfs(edge[i].to);
	ans[x]+=query(b[x]-1);

}

int main() {
	scanf("%d",&n);
	for(int i=1; i<=n; i++)scanf("%d",&a[i].v),a[i].id=i; //        
	sort(a+1,a+1+n,cmp);
	for(int i=1; i<=n; i++)b[a[i].id]=i;
	for(int i=2; i<=n; i++) {
		int f;
		scanf("%d",&f);
		add(f,i);
	}
	dfs(1);

	for(int i=1; i<=n; i++)printf("%d
",ans[i]);
}

인터넷 에서 당신 이 선분 트 리 로 쓴 것 을 보 았 는데, 사실은 가중치 선분 트 리 입 니 다.가중치 선분 의 템 플 릿 에 따라 다시 한 번 썼 다.나무 모양 으로 배열 할 수 있 으 면 쓰 세 요.
가중치 선분 트 리 의 구축 과 유사 한 트 리 배열 은 데 이 터 를 이산 화 한 후에 데이터 i 가 나 타 났 는 지, 나 타 났 는 지, i 의 위치 표지 에 1.

#include 
#include 
#include
using namespace  std;

const int maxn = 1e5+10;

struct Node {
	int l,r,tot;
} tree[maxn*3];
int n,m,b[maxn],head[maxn],cur=1,ans[maxn];
struct EDGE {
	int to,next;
} edge[maxn];
void add(int u,int v) {
	edge[cur].to=v;
	edge[cur].next=head[u];
	head[u]=cur++;
}
struct COW {
	int v,id;
} a[maxn];
bool cmp(COW x,COW y) {
	return x.v>1;
	build(l,mid,o<<1);
	build(mid+1,r,o<<1|1);
}

void push_up(int o) {
	tree[o].tot=tree[o<<1].tot+tree[o<<1|1].tot;
}

void update(int o,int x) {
	if(tree[o].l==x && tree[o].l==tree[o].r) {
		tree[o].tot++;
		return ;
	}
	int mid=(tree[o].l+tree[o].r)>>1;
	if(x<=mid) update(o<<1,x);
	if(x>mid) update(o<<1|1,x);
	push_up(o);
}

int query(int o,int l,int r) { //  >=l     ,        l-1       
	if(tree[o].l>r || tree[o].r>1;
	if(r<=mid) return query(o<<1,l,r);
	if(l>mid) return query(o<<1|1,l,r);
	return query(o<<1,l,mid)+query(o<<1|1,mid+1,r);
}

void dfs(int x) {
	update(1,b[x]);
	ans[x]-=query(1,b[x]+1,n) ;
	for(int i=head[x]; i>0; i=edge[i].next)
		dfs(edge[i].to);
	ans[x]+=query(1,b[x]+1,n);
}

int main() {
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
	scanf("%d",&n);
	for(int i=1; i<=n; i++)scanf("%d",&a[i].v),a[i].id=i;
	sort(a+1,a+1+n,cmp);
	for(int i=1; i<=n; i++)b[a[i].id]=i;
	build(1,n,1);
	for(int i=2; i<=n; i++) {
		int f;
		scanf("%d",&f);
		add(f,i);
	}
	dfs(1);
	for(int i=1; i<=n; i++)printf("%d
",ans[i]);
}