bzoj 4756 [Usaco2017 Jan]Promotion Counting——线段树合并

题目：https://www.lydsy.com/JudgeOnline/problem.php?id=4756

线段树合并裸题。那种返回 int 的与传引用的 merge 都能过。不知别的题是不是这样。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int N=1e5+,M=N**;

int n,m,a[N],tp[N],rt[N],hd[N],xnt,to[N],nxt[N],ans[N];

int tot,ls[M],rs[M],siz[M];

int rdn()

{

  int ret=;bool fx=;char ch=getchar();

  while(ch>''||ch<''){if(ch=='-')fx=;ch=getchar();}

  while(ch>=''&&ch<='')ret=(ret<<)+(ret<<)+ch-'',ch=getchar();

  return fx?ret:-ret;

}

void add(int x,int y)

{

  to[++xnt]=y;nxt[xnt]=hd[x];hd[x]=xnt;

}

void merge(int &x,int y)

{

  if(!x){x=y;return;}

  siz[x]+=siz[y];

  if(ls[y])merge(ls[x],ls[y]);

  if(rs[y])merge(rs[x],rs[y]);

}

/*

int merge(int x,int y)

{

  if(!x||!y)return x+y;

  int d=++tot;

  siz[d]=siz[x]+siz[y];

  ls[d]=merge(ls[x],ls[y]);

  rs[d]=merge(rs[x],rs[y]);

  return d;

}

*/

int query(int l,int r,int cr,int L,int R)

{

  if(!cr)return ;if(l>=L&&r<=R)return siz[cr];

  int mid=l+r>>,ret=;

  if(mid>=L)ret=query(l,mid,ls[cr],L,R);

  if(mid<R)ret+=query(mid+,r,rs[cr],L,R);

  return ret;

}

void insert(int l,int r,int &cr,int p)

{

  if(!cr)cr=++tot; siz[cr]++;

  if(l==r)return; int mid=l+r>>;

  if(mid>=p) insert(l,mid,ls[cr],p);

  else insert(mid+,r,rs[cr],p);

}

void dfs(int cr)

{

  for(int i=hd[cr],v;i;i=nxt[i])

    dfs(v=to[i]),/*rt[cr]=*/merge(rt[cr],rt[v]);

  ans[cr]=query(,m,rt[cr],a[cr],m);

  insert(,m,rt[cr],a[cr]);

}

int main()

{

  n=rdn(); for(int i=;i<=n;i++)a[i]=tp[i]=rdn();

  sort(tp+,tp+n+); m=unique(tp+,tp+n+)-tp-;

  for(int i=;i<=n;i++)a[i]=lower_bound(tp+,tp+n+,a[i])-tp;

  for(int i=,d;i<=n;i++)

    {

      d=rdn(); add(d,i);

    }

  dfs();

  for(int i=;i<=n;i++)printf("%d\n",ans[i]);

  return ;

}