正文
BZOJ_4756_[Usaco2017 Jan]Promotion Counting_树状数组
小程序：扫一扫查出行【扫一扫了解最新限行尾号】
复制小程序
BZOJ_4756_[Usaco2017 Jan]Promotion Counting_树状数组
Descriptionn只奶牛构成了一个树形的公司，每个奶牛有一个能力值pi，1号奶牛为树根。
问对于每个奶牛来说，它的子树中有几个能力值比它大的。Inputn，表示有几只奶牛 n<=100000
接下来n行为1-n号奶牛的能力值pi
接下来n-1行为2-n号奶牛的经理（树中的父亲）Output共n行，每行输出奶牛i的下属中有几个能力值比i大Sample Input5
804289384
846930887
681692778
714636916
957747794
1
1
2
3Sample Output2
0
1
0
0
这道题的思路比较巧妙。我们对整棵树进行DFS时每个点有两次处理的机会。一次是刚刚遍历到，一次是子树的回溯。分别求出两次能力值大于这个点的点的个数，用第二次的减去第一次的就是这个点的答案。然后离散用树状数组处理一下。 代码：#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define N 100050
struct A {
int num,id,v;
}a[N];
bool cmp1(const A &x,const A &y){return x.num>y.num; }
bool cmp2(const A &x,const A &y){return x.id<y.id; }
int n,head[N],to[N<<1],nxt[N<<1],cnt,ans[N],c[N];
inline void add(int u,int v) {
to[++cnt]=v;nxt[cnt]=head[u];head[u]=cnt;
}
void fix(int x,int v) {
for(;x<=n;x+=x&-x) c[x]+=v;
}
int inq(int x) {
int re=0;
for(;x;x-=x&-x) re+=c[x];
return re;
}
void dfs(int x,int y) {
int i;
fix(a[x].v,1);
int tmp=inq(a[x].v-1);
for(i=head[x];i;i=nxt[i]) {
if(to[i]!=y) {
dfs(to[i],x);
}
}
ans[x]=inq(a[x].v-1)-tmp;
}
int main() {
//freopen("tt.in","r",stdin);
scanf("%d",&n);
int i,x,j;
for(i=1;i<=n;i++) scanf("%d",&a[i].num),a[i].id=i;
sort(a+1,a+n+1,cmp1); a[0].num=-245345;
for(i=1,j=0;i<=n;i++) { if(a[i].num!=a[i-1].num) j++; a[i].v=j; }
sort(a+1,a+n+1,cmp2);
for(i=2;i<=n;i++) {
scanf("%d",&x);
add(i,x); add(x,i);
}
dfs(1,0);
for(i=1;i<=n;i++) printf("%d\n",ans[i]);
}
n只奶牛构成了一个树形的公司，每个奶牛有一个能力值pi，1号奶牛为树根。
问对于每个奶牛来说，它的子树中有几个能力值比它大的。
问对于每个奶牛来说，它的子树中有几个能力值比它大的。
n，表示有几只奶牛 n<=100000
接下来n行为1-n号奶牛的能力值pi
接下来n-1行为2-n号奶牛的经理（树中的父亲）
接下来n行为1-n号奶牛的能力值pi
接下来n-1行为2-n号奶牛的经理（树中的父亲）
Output共n行，每行输出奶牛i的下属中有几个能力值比i大Sample Input5
804289384
846930887
681692778
714636916
957747794
1
1
2
3Sample Output2
0
1
0
0
这道题的思路比较巧妙。我们对整棵树进行DFS时每个点有两次处理的机会。一次是刚刚遍历到，一次是子树的回溯。分别求出两次能力值大于这个点的点的个数，用第二次的减去第一次的就是这个点的答案。然后离散用树状数组处理一下。 代码：#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define N 100050
struct A {
int num,id,v;
}a[N];
bool cmp1(const A &x,const A &y){return x.num>y.num; }
bool cmp2(const A &x,const A &y){return x.id<y.id; }
int n,head[N],to[N<<1],nxt[N<<1],cnt,ans[N],c[N];
inline void add(int u,int v) {
to[++cnt]=v;nxt[cnt]=head[u];head[u]=cnt;
}
void fix(int x,int v) {
for(;x<=n;x+=x&-x) c[x]+=v;
}
int inq(int x) {
int re=0;
for(;x;x-=x&-x) re+=c[x];
return re;
}
void dfs(int x,int y) {
int i;
fix(a[x].v,1);
int tmp=inq(a[x].v-1);
for(i=head[x];i;i=nxt[i]) {
if(to[i]!=y) {
dfs(to[i],x);
}
}
ans[x]=inq(a[x].v-1)-tmp;
}
int main() {
//freopen("tt.in","r",stdin);
scanf("%d",&n);
int i,x,j;
for(i=1;i<=n;i++) scanf("%d",&a[i].num),a[i].id=i;
sort(a+1,a+n+1,cmp1); a[0].num=-245345;
for(i=1,j=0;i<=n;i++) { if(a[i].num!=a[i-1].num) j++; a[i].v=j; }
sort(a+1,a+n+1,cmp2);
for(i=2;i<=n;i++) {
scanf("%d",&x);
add(i,x); add(x,i);
}
dfs(1,0);
for(i=1;i<=n;i++) printf("%d\n",ans[i]);
}
共n行，每行输出奶牛i的下属中有几个能力值比i大
5
804289384
846930887
681692778
714636916
957747794
1
1
2
3
804289384
846930887
681692778
714636916
957747794
1
1
2
3
Sample Output2
0
1
0
0
这道题的思路比较巧妙。我们对整棵树进行DFS时每个点有两次处理的机会。一次是刚刚遍历到，一次是子树的回溯。分别求出两次能力值大于这个点的点的个数，用第二次的减去第一次的就是这个点的答案。然后离散用树状数组处理一下。 代码：#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define N 100050
struct A {
int num,id,v;
}a[N];
bool cmp1(const A &x,const A &y){return x.num>y.num; }
bool cmp2(const A &x,const A &y){return x.id<y.id; }
int n,head[N],to[N<<1],nxt[N<<1],cnt,ans[N],c[N];
inline void add(int u,int v) {
to[++cnt]=v;nxt[cnt]=head[u];head[u]=cnt;
}
void fix(int x,int v) {
for(;x<=n;x+=x&-x) c[x]+=v;
}
int inq(int x) {
int re=0;
for(;x;x-=x&-x) re+=c[x];
return re;
}
void dfs(int x,int y) {
int i;
fix(a[x].v,1);
int tmp=inq(a[x].v-1);
for(i=head[x];i;i=nxt[i]) {
if(to[i]!=y) {
dfs(to[i],x);
}
}
ans[x]=inq(a[x].v-1)-tmp;
}
int main() {
//freopen("tt.in","r",stdin);
scanf("%d",&n);
int i,x,j;
for(i=1;i<=n;i++) scanf("%d",&a[i].num),a[i].id=i;
sort(a+1,a+n+1,cmp1); a[0].num=-245345;
for(i=1,j=0;i<=n;i++) { if(a[i].num!=a[i-1].num) j++; a[i].v=j; }
sort(a+1,a+n+1,cmp2);
for(i=2;i<=n;i++) {
scanf("%d",&x);
add(i,x); add(x,i);
}
dfs(1,0);
for(i=1;i<=n;i++) printf("%d\n",ans[i]);
}
0
1
0
0
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define N 100050
struct A {
int num,id,v;
}a[N];
bool cmp1(const A &x,const A &y){return x.num>y.num; }
bool cmp2(const A &x,const A &y){return x.id<y.id; }
int n,head[N],to[N<<1],nxt[N<<1],cnt,ans[N],c[N];
inline void add(int u,int v) {
to[++cnt]=v;nxt[cnt]=head[u];head[u]=cnt;
}
void fix(int x,int v) {
for(;x<=n;x+=x&-x) c[x]+=v;
}
int inq(int x) {
int re=0;
for(;x;x-=x&-x) re+=c[x];
return re;
}
void dfs(int x,int y) {
int i;
fix(a[x].v,1);
int tmp=inq(a[x].v-1);
for(i=head[x];i;i=nxt[i]) {
if(to[i]!=y) {
dfs(to[i],x);
}
}
ans[x]=inq(a[x].v-1)-tmp;
}
int main() {
//freopen("tt.in","r",stdin);
scanf("%d",&n);
int i,x,j;
for(i=1;i<=n;i++) scanf("%d",&a[i].num),a[i].id=i;
sort(a+1,a+n+1,cmp1); a[0].num=-245345;
for(i=1,j=0;i<=n;i++) { if(a[i].num!=a[i-1].num) j++; a[i].v=j; }
sort(a+1,a+n+1,cmp2);
for(i=2;i<=n;i++) {
scanf("%d",&x);
add(i,x); add(x,i);
}
dfs(1,0);
for(i=1;i<=n;i++) printf("%d\n",ans[i]);
}
