题解 P3605 【[USACO17JAN]Promotion Counting晋升者计数】

teafrogsf

2018-06-13 22:01:04

Solution

题解里这么多BIT的啊......其实我是因为找线段树合并裸题才来的orz~~那么为了增加代码长度就写一个线段树合并吧~~ 建好**动态开点线段树**(原题解有误,故修正),每次dfs后就合并父子线段树,然后再查询权值线段树上大于它的。这样的复杂度仍然是$O(n\log n)$。 ```cpp #include<cstdio> #include<iostream> #include<algorithm> #include<tr1/unordered_map> #define neko 100010 #define f(i,a,b) for(register int i=(a);i<=(b);i=-(~(i))) #define travel(i,u,v) for(register int i=head[u],v=e[i].v;i;i=e[i].nex,v=e[i].v) typedef int arr[neko]; arr in,out,dfn,head,ans; int L[neko*20],R[neko*20],Sum[neko*20],rt[neko*20]; int t,cnt,n; std::tr1::unordered_map<int,int>mp; struct OK {int val,id;}a[neko]; bool cmp(OK x,OK y) {return x.val<y.val;} bool cmp2(OK x,OK y) {return x.id<y.id;} struct node { int v,nex; }e[neko<<1]; void add(int x,int y) { e[++t].v=y; e[t].nex=head[x]; head[x]=t; } namespace Pst_Tree { #define mid ((l+r)>>1) #define lson L[root],l,mid #define rson R[root],mid+1,r void pushup(int root) {Sum[root]=Sum[L[root]]+Sum[R[root]];} void update(int &root,int l,int r,int x) { if(!root)root=++cnt; if(l==r){++Sum[root];return;} if(x<=mid)update(lson,x); else update(rson,x); pushup(root); } int query(int root,int l,int r,int tagl,int tagr) { if(l>=tagl&&r<=tagr)return Sum[root]; int tmp=0; if(tagl<=mid)tmp+=query(lson,tagl,tagr); if(tagr>mid)tmp+=query(rson,tagl,tagr); return tmp; } int merge(int x,int y) { if((!x)||(!y))return x+y; L[x]=merge(L[x],L[y]); R[x]=merge(R[x],R[y]); pushup(x); return x; } } using namespace Pst_Tree; void dfs(int u,int fa) { travel(i,u,v)if(v!=fa)dfs(v,u),rt[u]=merge(rt[u],rt[v]); ans[u]=query(rt[u],1,n,mp[a[u].val]+1,n); } int main() { using namespace std; int x; scanf("%d",&n); f(i,1,n)scanf("%d",&a[i].val),a[i].id=i; sort(a+1,a+n+1,cmp); f(i,1,n)if(!mp[a[i].val])mp[a[i].val]=i; sort(a+1,a+n+1,cmp2); f(i,2,n)scanf("%d",&x),add(x,i),add(i,x); f(i,1,n)update(rt[i],1,n,mp[a[i].val]); dfs(1,0); f(i,1,n)printf("%d\n",ans[i]); } ```