Yet Another Tree Query Problem

【题目大意】给你一棵树,和Q组询问,问你在点[L,R]中有多少个联通块。

【题解】显然联通块的数量等于区间内点的数量减去区间内边的数量。我们可以把询问离线排个序,然后先把所有的边加进去,从左往右扫,依次删除以i为左端点的边,用树状数组可以解决。(谭队说可以怒上主席树太强了%%%)

/********************************************

	Title		ZOJ4008.cpp
	Author 		TomatoLoveCoconut
	Time		2018-3-31
	History		Created 2018-3-31
	
	Version		1.0.0
	
	Tags:


	while(true) RP++;
	
		 QAQ

*********************************************/


#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
#define base 311
#define mod 19270817
#define maxlongint 2147483647
#define maxint 32767
#define pi (double)acos(-1.0)
#define eps 1e-
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define mp make_pair
//SGT
#define MID (l+r)>>1
#define lson o<<1
#define rson o<<1|1
//clear the array
#define cla(a) memset(a,0,sizeof(a))
#define clb(a) memset(a,INF,sizeof(a));
#define clc(a) memset(a,-1,sizeof(a));
#define maxn 200005


using namespace std;


//complex
struct Complex{
    double x,y;
    Complex(double xx=0,double yy=0){x=xx,y=yy;}
};
inline Complex operator + (Complex a,Complex b){return Complex(a.x+b.x,a.y+b.y);}
inline Complex operator - (Complex a,Complex b){return Complex(a.x-b.x,a.y-b.y);}
inline Complex operator * (Complex a,Complex b){return Complex(a.x*b.x-a.y*b.y,a.y*b.x+b.y*a.x);}
//BIT
inline int lowbit(int x){return x&(-x);}




//var
int tree[maxn];
int n,m,Q;
inline void add(int x,int val)
{
	while (x<=n)
	{
		tree[x]+=val;
		x+=lowbit(x);
	}
}
inline int query(int x)
{
	int ans=0;
	while (x)
	{
		ans+=tree[x];
		x-=lowbit(x);
	}
	return ans;
}


vector<int> G[maxn];
struct Query{
	int l,r,id;
	bool operator < (const Query& x) const{
		if (l==x.l) return r<x.r;
		else return l<x.l;
	}
}q[maxn];
int ans[maxn];
int main()
{
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	int T;
	scanf("%d",&T);
	while (T--)
	{
		cla(tree);
		cla(q);
		scanf("%d%d",&n,&Q);
		for (int i=1;i<=n;i++)
			G[i].clear();
		for (int i=1;i<n;i++)
		{
			int u,v;
			scanf("%d%d",&u,&v);
			G[min(u,v)].push_back(max(u,v));
			add(max(u,v),1);
		}
		for (int i=1;i<=Q;i++)
		{
			scanf("%d%d",&q[i].l,&q[i].r);
			q[i].id=i;
		}
		sort(q+1,q+1+Q);
		int now=1;
		for (int i=1;i<=n;i++)
		{
			while (q[now].l==i && now<=Q)
			{
				ans[q[now].id]=q[now].r-q[now].l+1-query(q[now].r);
				now++;
			}
			
			for (int j=0;j<G[i].size();j++)
			{
				int r=G[i][j];
				add(r,-1);
			}
		}
		for (int i=1;i<=Q;i++)
			printf("%d\n",ans[i]);
	}
	return 0;
}
分类: 树状数组

发表评论

电子邮件地址不会被公开。 必填项已用*标注