社区讨论
有个问题
P3605[USACO17JAN] Promotion Counting P参与者 3已保存回复 2
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 2 条
- 当前快照
- 1 份
- 快照标识符
- @m2d5pacb
- 此快照首次捕获于
- 2024/10/17 18:26 去年
- 此快照最后确认于
- 2025/11/04 16:59 4 个月前
如果{pn}中有重复的数,那这题是否就不能用树状数组写
C#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,dfsn[100005],cnt,sz[100005],tree[100005],ans[100005];
int lowbit(int x){
return x&-x;
}
struct su{
int pos,val;
};
su a[100005];
vector<int>g[100005];
void dfs(int u){
dfsn[u]=++cnt;
sz[u]=1;
for(int i=0;i<(int)g[u].size();i++){
dfs(g[u][i]);
sz[u]+=sz[g[u][i]];
}
return;
}
void add(int x){
while(x<=n){
tree[x]++;
x+=lowbit(x);
}
}
int query(int x){
int sum=0;
while(x>0){
sum+=tree[x];
x-=lowbit(x);
}
return sum;
}
bool cmp(su x,su y){
return x.val<y.val;
}
signed main()
{
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i].val;
a[i].pos=i;
}
sort(a+1,a+n+1,cmp);
for(int i=2;i<=n;i++){
int u;
cin>>u;
g[u].push_back(i);
}
dfs(1);
for(int i=1;i<=n;i++){
ans[a[i].pos]=sz[a[i].pos]-1-(query(dfsn[a[i].pos]+sz[a[i].pos]-1)-query(dfsn[a[i].pos]-1));
add(dfsn[a[i].pos]);
}
for(int i=1;i<=n;i++){
cout<<ans[i]<<endl;
}
return 0;
}
CPP回复
共 2 条回复,欢迎继续交流。
正在加载回复...