本文共 2271 字，大约阅读时间需要 7 分钟。

题目链接：

#include
   
    #define ll long longusing namespace std;const int maxx=1e5+100;struct node{
   	int l;	int r;	int sum;}p[maxx*20];int head[maxx<<1];int dp[maxx][22];int val[maxx];int deep[maxx];int root[maxx];struct edge{
   	int to,next,w;}e[maxx<<1];int tot,n,m,len,ror;/*-------------事前准备--------------*/inline int getid(int w){
   	return lower_bound(val+1,val+len+1,w)-val;}inline void init(){
   	for(int i=0;i<=n;i++)	for(int j=0;j<=20;j++) dp[i][j]=0;	memset(head,-1,sizeof(head));	tot=0;ror=0;}inline void add(int u,int v,int w){
   	e[tot].to=v,e[tot].next=head[u],e[tot].w=w,head[u]=tot++;}/*-------------主席树--------------*/inline void pushup(int cur){
   	p[cur].sum=p[p[cur].l].sum+p[p[cur].r].sum;}inline int build(int l,int r){
   	int cur=++ror;	p[cur].sum=0;	if(l==r) return cur;	int mid=l+r>>1;	p[cur].l=build(l,mid);	p[cur].r=build(mid+1,r);	return cur;}inline int update(int pos,int rot,int l,int r){
   	int cur=++ror;	p[cur]=p[rot];	if(l==r) 	{
   		p[cur].sum++;		return cur;	}	int mid=l+r>>1;	if(pos<=mid) p[cur].l=update(pos,p[rot].l,l,mid);	else p[cur].r=update(pos,p[rot].r,mid+1,r);	pushup(cur);	return cur;}inline int query(int lrot,int rrot,int frot,int l,int r,int sum){
   	if(r<=sum) return p[lrot].sum+p[rrot].sum-p[frot].sum*2;	int mid=l+r>>1;	int ret=p[p[lrot].l].sum+p[p[rrot].l].sum-p[p[frot].l].sum*2;	if(sum<=mid) return query(p[lrot].l,p[rrot].l,p[frot].l,l,mid,sum);	else return ret+query(p[lrot].r,p[rrot].r,p[frot].r,mid+1,r,sum);}/*-------------dfs---------------*/inline void dfs(int u,int f){
   	deep[u]=deep[f]+1;	dp[u][0]=f;	for(int i=1;i<=20;i++)	{
   		if(dp[u][i-1]) dp[u][i]=dp[dp[u][i-1]][i-1];		else break;	}	for(int i=head[u];i!=-1;i=e[i].next)	{
   		int to=e[i].to,w=e[i].w;		if(to==f) continue;		root[to]=update(getid(w),root[u],1,len);		dfs(to,u);	}}/*-----------lca-----------*/inline int get_lca(int x,int y){
   	if(deep[x]
    
     =0;i--)	{
   		if(dp[x][i]!=dp[y][i])		{
   			x=dp[x][i];			y=dp[y][i];		}	}	return dp[x][0];}int main(){
   	int x,y,w;	while(~scanf("%d%d",&n,&m))	{
   		init();		for(int i=1;i
    
   

努力加油a啊，(^o)/~

转载地址：http://lztvi.baihongyu.com/