记录编号	531028	评测结果	AAAAAAAAAA
题目名称	飘雪圣域	最终得分	100
用户昵称	瑆の時間~無盡輪迴·林蔭	是否通过	通过
代码语言	C++	运行时间	0.811 s
提交时间	2019-05-07 22:25:31	内存使用	5.58 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int t[900001];
struct sd
{
	int l,r;
};
sd e[200001];
struct sdr
{
	int l,r,id;
};
sdr s[200001];
int ans[200001];
int n,m,a1,a2,now=1;
int cmp1(sd a,sd b)
{
	return a.r<b.r;
}
int cmp2(sdr a,sdr b)
{
	return a.r<b.r;
}
int ls(int x)
{
	return x<<1;
}
int rs(int x)
{
	return x<<1|1;
}
void pushup(int x)
{
	t[x]=t[ls(x)]+t[rs(x)];
}
void build(int x,int l,int r)
{
	if(l==r)
	{
		t[l]=0;
		return;
	}
	else
	{
		int mid=(l+r)>>1;
		build(ls(x),l,mid);
		build(rs(x),mid+1,r);
	}
}
void ADD(int x,int l,int r,int mb)
{
	if(l==r)
	{
		t[l]++;
		return;
	}
	int mid=(l+r)>>1;
	if(mb<=mid)
	{
		ADD(ls(x),l,mid,mb);
	}
	else
	{
		ADD(rs(x),mid+1,r,mb);
	}
	pushup(x);
}
int QJCX(int nl,int nr,int l,int r,int p)
{
	if(nl<=l&&nr>=r)
	{
		return t[p];
	}
	//pushdown(p,l,r);
	int mid=(l+r)>>1;
	if(nr<=mid)
	{
		return QJCX(nl,nr,l,mid,ls(p));
	}
	if(nl>mid)
	{
		return QJCX(nl,nr,mid+1,r,rs(p)); 
	}
	return QJCX(nl,mid,l,mid,ls(p))+QJCX(mid+1,nr,mid+1,r,rs(p)); 
} 
void jia(int k,int v){
    for(int i=k;i<=n;i+=i&-i)t[i]+=v;
}
int ask(int k){
    int sum=0;
    for(int i=k;i;i-=i&-i)sum+=t[i];
    return sum;
}
int LINYIN()
{
	freopen("icekingdom.in","r",stdin);
	freopen("icekingdom.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<n;i++)
	{
		scanf("%d%d",&a1,&a2);
		if(a1>a2)
		{
			swap(a1,a2);
		}
		e[i].l=a1;
		e[i].r=a2;
	}
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&a1,&a2);
		if(a1>a2)
		{
			swap(a1,a2);
		}
		s[i].id=i;
		s[i].l=a1;
		s[i].r=a2;
	}
	sort(e+1,e+n,cmp1);
	sort(s+1,s+1+m,cmp2);
	for(int i=1;i<=m;i++)
	{
		while(now<n&&s[i].r>=e[now].r)
		{
			//ADD(1,1,n,e[now].l);
			jia(e[now].l,1);
			now++;
		}
		int num=ask(s[i].r)-ask(s[i].l-1);
        ans[s[i].id]=s[i].r-s[i].l+1-num;
	}
	for(int i=1;i<=m;i++)
	{
		printf("%d",ans[i]);
	}
	return 0;
}
int sdd=LINYIN();
int main()
{
	;
}