记录编号 530908 评测结果 AAAAAAAAAA
题目名称 飘雪圣域 最终得分 100
用户昵称 Gravatar梦那边的美好ET 是否通过 通过
代码语言 C++ 运行时间 0.864 s
提交时间 2019-05-07 12:09:43 内存使用 9.26 MiB
显示代码纯文本
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#define maxn 200010
using namespace std;
struct hs1{int l,r,sum,p;}a[maxn];
struct hs2{int x,y;}b[maxn];
bool bk1(hs1 a1,hs1 a2){return a1.r<a2.r;}
bool bk2(hs2 a1,hs2 a2){return a1.y<a2.y;}
int n,m,ans[maxn],c[maxn];
void insert(int a1,int a2){for(int i=a1;i<=n;i+=(i&-i))c[i]+=a2;return;}
int getsum(int a1){int s=0;for(int i=a1;i;i-=(i&-i))s+=c[i];return s;}
int solve(int a1,int a2){return getsum(a2)-getsum(a1-1);}
int main(){
	freopen("icekingdom.in","r",stdin);
	freopen("icekingdom.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n-1;i++){
		scanf("%d%d",&b[i].x,&b[i].y);
		if(b[i].x>b[i].y)swap(b[i].x,b[i].y);
	}
	for(int i=1;i<=m;i++)scanf("%d%d",&a[i].l,&a[i].r),a[i].p=i;
	sort(a+1,a+1+m,bk1);sort(b+1,b+n,bk2);
	for(int i=1;i<=n-1;i++)insert(b[i].x,1);
	int ld=n-1;
	for(int i=m;i>=1;i--){
		while(b[ld].y>a[i].r&&ld>=1)insert(b[ld].x,-1),ld--;
		a[i].sum=solve(a[i].l,a[i].r);
	}
	for(int i=1;i<=m;i++)ans[a[i].p]=a[i].r-a[i].l+1-a[i].sum;
	for(int i=1;i<=m;i++)printf("%d\n",ans[i]);
	return 0;
}