이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define X first
#define Y second
int lowbit(int x){return x&-x;}
int bit[500005];
void upd(int pl,int x){
while(pl<=200000){
bit[pl]+=x;
pl+=lowbit(pl);
}
}
int qsum(int pl){
int ret=0;
while(pl){
ret+=bit[pl];
pl-=lowbit(pl);
}
return ret;
}
int n;int ar[500005];
int fa[200005];
int va[200005];int vb[200005];
vector<int>e[200005];
void lisanhua(){
vector<int>vc;
for(int i=1;i<=n;i++){
vc.push_back(ar[i]);
}
sort(vc.begin(),vc.end());
for(int i=1;i<=n;i++){
ar[i]=1+lower_bound(vc.begin(),vc.end(),ar[i])-vc.begin();
}
}
signed main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>ar[i];
}
lisanhua();
for(int i=1;i<=n-1;i++){
cin>>va[i]>>vb[i];
fa[vb[i]]=va[i];
int nw=va[i];
int ans=0;
while(nw!=0){
upd(ar[nw],1);
ans+=qsum(ar[nw]-1);
nw=fa[nw];
}
nw=va[i];
while(nw!=0){
upd(ar[nw],-1);
ar[nw]=ar[vb[i]];
nw=fa[nw];
}
cout<<ans<<"\n";
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |