思路

線段樹合并的板子。。
和子節(jié)點合并之后在值域線段樹上查詢即可

代碼

#include <cstdio> #include <algorithm> #include <cstring> using namespace std; const int MAXN = 1000100; int n,Nodecnt,root[MAXN],u[MAXN<<1],v[MAXN<<1],cnt,fir[MAXN],nxt[MAXN<<1],ans[MAXN],ax[MAXN],w_p[MAXN],nx; struct Node{int lson,rson,sz; }Seg[MAXN<<2]; int merge(int x,int y,int l,int r){if(x*y==0)return x+y;if(l==r){int t=++Nodecnt;Seg[t].sz=Seg[x].sz+Seg[y].sz;return Nodecnt;}int g=++Nodecnt;Seg[g].sz=Seg[x].sz+Seg[y].sz;int mid=(l+r)>>1;Seg[g].lson=merge(Seg[x].lson,Seg[y].lson,l,mid);Seg[g].rson=merge(Seg[x].rson,Seg[y].rson,mid+1,r); return g; } int query(int l,int r,int o,int val){if(l==r){return 0; }int mid=(l+r)>>1;if(val<=mid)return query(l,mid,Seg[o].lson,val)+Seg[Seg[o].rson].sz;elsereturn query(mid+1,r,Seg[o].rson,val); } void build(int l,int r,int &o,int val){if(!o)o=++Nodecnt;Seg[o].sz++;if(l==r)return;int mid=(l+r)>>1;if(val<=mid)build(l,mid,Seg[o].lson,val);elsebuild(mid+1,r,Seg[o].rson,val); } void addedge(int ui,int vi){++cnt;u[cnt]=ui;v[cnt]=vi;nxt[cnt]=fir[ui];fir[ui]=cnt; } void dfs(int u,int fa){for(int i=fir[u];i;i=nxt[i]){if(v[i]==fa)continue;dfs(v[i],u);root[u]=merge(root[v[i]],root[u],1,n);}ans[u]=query(1,n,root[u],w_p[u]); } void init(void){sort(ax+1,ax+n+1);nx=unique(ax+1,ax+n+1)-ax-1; // printf("%d\n",nx);for(int i=1;i<=n;i++){w_p[i]=lower_bound(ax+1,ax+nx+1,w_p[i])-ax; // printf("%d!\n",w_p[i]);} for(int i=1;i<=n;i++){build(1,n,root[i],w_p[i]);} } int main(){scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&w_p[i]),ax[i]=w_p[i];}for(int i=2;i<=n;i++){int x;scanf("%d",&x);addedge(i,x);addedge(x,i);}init();dfs(1,0);for(int i=1;i<=n;i++)printf("%d\n",ans[i]);return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/dreagonm/p/10555166.html

總結(jié)

以上是生活随笔為你收集整理的P3605 [USACO17JAN]Promotion Counting晋升者计数的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。