PerfectPan
;

ZOJ 4008 Yet Another Tree Query Problem

March 12, 2018

题目链接http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=4008

题意:给定一棵树,若干询问,求节点编号在 [L,R][L,R] 里的点进行连边后形成的连通块数量。

思路:对于一棵树,你连一条边就相当于并查集进行了一次有效的合并操作,连通分量数减一,所以问题就转化为求 RL+1[L,R]R-L+1-[L,R] 中节点的连边数,后面那个我们把每条边小的编号看做 xx 轴上的值,大的编号看做 yy 轴上的值,这样一条边就看作了一个点,节点连边数就看成了一个二维数点的问题,扫描线配合树状数组就可以解了。我们将询问也看成一个点,本来应该是查 (L,L),(R,R)(L,L),(R,R) 这两个点围成的矩形内的点的数量,但是之前连边的特殊性,我们从 xx 轴大到小边插入边查询,就可以保证到 LL 的时候不会查到 (L(L,比 LL))((RR 大,R)R) 的点,直接树状数组查找小于 RR 的点的数量有多少个就可以了,时间复杂度 O(nlogn)O(nlogn)

#pragma comment(linker, "/STACK:102400000,102400000")
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <cmath>
#include <string>
#include <vector>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <sstream>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define lson root<<1,l,mid
#define rson root<<1|1,mid+1,r
#define Key_Value ch[ch[root][1]][0]
#define DBN1(a)           cerr<<#a<<"="<<(a)<<"\n"
#define DBN2(a,b)         cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<"\n"
#define DBN3(a,b,c)       cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<"\n"
#define DBN4(a,b,c,d)     cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<"\n"
#define DBN5(a,b,c,d,e)   cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<", "<<#e<<"="<<(e)<<"\n"
#define DBN6(a,b,c,d,e,f) cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<", "<<#e<<"="<<(e)<<", "<<#f<<"="<<(f)<<"\n"
#define clr(a,x) memset(a,x,sizeof(a))
#define pb push_back
#define mp make_pair
#define ALL(x) x.begin(),x.end()
#define F first
#define S second
using namespace std;
typedef long long ll;
const int maxn=500000+5;
const int INF=0x3f3f3f3f;
const int P=1000000007;
const double PI=acos(-1.0);
template<typename T>
inline T read(T&x){
    x=0;int _f=0;char ch=getchar();
    while(ch<'0'||ch>'9')_f|=(ch=='-'),ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x=_f?-x:x;
}
const int N=2e5+10;
int T,n,Q,u,v,i,l,r,cnt,ans[N],sum[N];
struct _{
	int x,y,t;
	bool operator <(const _&rhs)const{
		if (x^rhs.x) return x>rhs.x;
		return t<rhs.t;
	}
}q[N*2];
inline int lowbit(int x){return x&(-x);}
inline void add(int x){for(;x<=n;x+=lowbit(x))sum[x]++;}
inline int get(int x){
	int res=0;
	for (;x>0;x-=lowbit(x)) res+=sum[x];
	return res;
}
int main(){
	for (read(T);T--;){
		read(n),read(Q);
		memset(sum,0,sizeof(sum));
		for (cnt=0,i=1;i<n;i++){
			read(u),read(v);
			if (u>v) swap(u,v);
			q[++cnt]=(_){u,v,0};
		}
		for (i=1;i<=Q;i++){
			read(l),read(r);
			ans[i]=r-l+1;
			q[++cnt]=(_){l,r,i};
		}
		sort(q+1,q+1+cnt);
		for (i=1;i<=cnt;i++){
			if(q[i].t) ans[q[i].t]-=get(q[i].y);
			else add(q[i].y);
		}
		for (i=1;i<=Q;i++) printf("%d\n",ans[i]);
	}
	return 0;
}

Yiming Pan

Written by Yiming Pan who lives and works in Hangzhou China. Welcome follow me on Github

Cannot load comments. Please check you network.