题解 P3605 【[USACO17JAN]Promotion Counting晋升者计数】
teafrogsf
2018-06-13 22:01:04
题解里这么多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]);
}
```