题目[USACO17JAN]Promotion Counting P

从根节点dfs一遍，树状数组维护进入和出去时这个节点的贡献，一减就是答案

代码：

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <algorithm>

#include <vector>

#define lowbit(x) x&-x

const int N=1e5+5;

using namespace std;

struct pos

{

	int v,id;

	pos(int vv,int ii)

	{

		v=vv;id=ii;

	}

	pos(){

	}

	friend bool operator < (pos a,pos b)

	{

		return a.v<b.v;

	}

}nums[N];

int n,a[N],fs[N],fe[N],tot;

vector <int> g[N];

namespace fenwick

{

	struct fw

	{

		int c;

	}e[N];

	void modify(int x,int v)

	{

		for(int i=x;i<=n;i+=lowbit(i))

		    e[i].c+=v;

	}

	int query(int x)

	{

		int ret=0;

		for(int i=x;i;i-=lowbit(i))

		    ret+=e[i].c;

		return ret;

	}

}

using namespace fenwick;

void dfs(int u,int fa)

{

	++tot;

	modify(a[u],1);

	fs[u]=tot-query(a[u]);

	for(int i=0;i<g[u].size();i++)

	{

		int k=g[u][i];

		if(k==fa)

		    continue;

		dfs(k,u);

	}

	fe[u]=tot-query(a[u]);

}

int main()

{

	scanf("%d",&n);

	for(int i=1;i<=n;i++)

	{

		int v;

		scanf("%d",&v);

		nums[i]=pos(v,i);

	}

	for(int i=2;i<=n;i++)

	{

		int v;

		scanf("%d",&v);

		g[v].push_back(i);

		g[i].push_back(v);

	}

	sort(nums+1,nums+1+n);

	int last=-1,now=1;

	for(int i=1;i<=n;i++)

	{

		if(last!=nums[i].v)

		    last=nums[i].v,now=i;

		a[nums[i].id]=now;

	}

	dfs(1,0);

	for(int i=1;i<=n;i++)

	    printf("%d\n",fe[i]-fs[i]);

	return 0;

}

巴特西

2022春每日一题：Day 38

题目[USACO17JAN]Promotion Counting P

最新文章

热门文章