description
analysis
从求联通块出发根本没做法，于是考虑连通块里面的边
对于一个询问
[
l
,
r
]
[l,r]
[l,r]，一条边的左端点
≥
l
≥l
≥l且右端点
≤
r
≤r
≤r才在这个区间的点之间
于是对于边和询问排序，依次把边加入树状数组，然后查询当前询问区间里的边条数就知道了联通块个数
code
#pragma GCC optimize("O3")
#pragma G++ optimize("O3")
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define MAXN 200005
#define ll long long
#define reg register ll
#define fo(i,a,b) for (reg i=a;i<=b;++i)
#define fd(i,a,b) for (reg i=a;i>=b;--i)
using namespace std
;
ll tr
[MAXN
];
ll n
,q
;
struct edge
{
ll x
,y
;
}a
[MAXN
];
struct inquiry
{
ll x
,y
,z
,ans
;
}b
[MAXN
];
inline ll
read()
{
ll x
=0,f
=1;char ch
=getchar();
while (ch
<'0' || '9'<ch
){if (ch
=='-')f
=-1;ch
=getchar();}
while ('0'<=ch
&& ch
<='9')x
=x
*10+ch
-'0',ch
=getchar();
return x
*f
;
}
inline ll
lowbit(ll x
){return x
&(-x
);}
inline bool cmp(edge a
,edge b
){return a
.y
<b
.y
;}
inline bool cmpp(inquiry a
,inquiry b
){return a
.y
<b
.y
;}
inline bool cmppp(inquiry a
,inquiry b
){return a
.z
<b
.z
;}
inline void modify(ll x
,ll y
){while (x
<=n
)tr
[x
]+=y
,x
+=lowbit(x
);}
inline ll
query(ll x
){ll y
=0;while (x
)y
+=tr
[x
],x
-=lowbit(x
);return y
;}
inline ll
get(ll x
,ll y
){return query(y
)-query(x
-1);}
int main()
{
freopen("icekingdom.in","r",stdin);
n
=read(),q
=read();
fo(i
,1,n
-1)
{
ll x
=read(),y
=read();
a
[i
].x
=min(x
,y
),a
[i
].y
=max(x
,y
);
}
sort(a
+1,a
+n
,cmp
);
fo(i
,1,q
)b
[i
].x
=read(),b
[i
].y
=read(),b
[i
].z
=i
;
sort(b
+1,b
+q
+1,cmpp
);ll j
=1;
fo(i
,1,q
)
{
while (j
<n
&& b
[i
].y
>=a
[j
].y
)modify(a
[j
++].x
,1);
b
[i
].ans
=b
[i
].y
-b
[i
].x
+1-get(b
[i
].x
,b
[i
].y
);
}
sort(b
+1,b
+q
+1,cmppp
);
fo(i
,1,q
)printf("%lld\n",b
[i
].ans
);
return 0;
}
