星星灰暗着。

星星灰暗着。

你所见的的确是一个NOIp退役OIer的博客。

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

posted on 2018-06-13 22:01:04 | under 题解 |

题解里这么多BIT的啊......其实我是因为找线段树合并裸题才来的orz那么为了增加代码长度就写一个线段树合并吧
建好动态开点线段树(原题解有误,故修正),每次dfs后就合并父子线段树,然后再查询权值线段树上大于它的。这样的复杂度仍然是 $O(n\log n)$ 。

#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]);
}