列表

详情

NC15534. Dragon Ball Super

描述

Dragon Ball Super has finished. As a fan of Dragon Ball, Ctr couldn’t forget any plot of it, especially the fighting scene of Tournament of Power(力量大会). People who participate in the Tournament of Power will become the teammate with those who come from the same universe, even Son Goku and Frieza.
There are n people who may participate in the Tournament of Power, these people are numbered from 1 to n. Also there are m relations (ai,bi) which means person ai and person bi are come from the same universe.
Ctr defines the interest value of the Tournament of Power is the number of different universes people, participate in Tournament of Power, come from.
Now, Ctr has q queries to ask you, each of which contains two integers: l,r. For each query you are required to tell him the interest value when people ( l,l+1,...,r ) participate in the Tournament of Power.

输入描述

The first line contains an integer number T, the number of test cases.
For each test case : 
The first line contains two integer numbers n,m(1 ≤ n,m ≤ 105), the number of test cases.
The following m lines, each contains two integers ai,bi(1 ≤ ai,bi ≤ n), which means aith person and bith person are come from the same universe.
The next line contains an integer number q(1 ≤ q ≤ 105), the number of query.
The following q lines, each contains two integers l,r(1 ≤ l ≤ r ≤ n).

输出描述

For each query print the answer.

示例1

输入: 

1
6 3
1 2
3 4
5 6
2
2 5
2 4

输出: 

3
2

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++11(clang++ 3.9) 解法, 执行用时: 759ms, 内存消耗: 4964K, 提交时间: 2020-04-10 20:45:57 

#include<bits/stdc++.h>
using namespace std;

const int N=1e5+100;

int f[N];
int find(int x)
{
	return x==f[x]?x:f[x]=find(f[x]);
};
struct node
{
	int l,r,id;
	bool operator<(const node &M) const
	{
		return r<M.r;
	}
}Q[N];
int vis[N];

int c[N];
void add(int x,int v)
{
	while(x<N)
	{
		c[x]+=v;
		x+=x&-x;
	}
}
int query(int x)
{
	int ans=0;
	while(x)
	{
		ans+=c[x];
		x-=x&-x;
	}
	return ans;
}

int ans[N];
int main()
{
	ios::sync_with_stdio(false);
	int T;
	cin>>T;
	while(T--)
	{
		int n,m;
		cin>>n>>m;
		for(int i=1;i<=n;i++) f[i]=i;
		memset(vis,0,sizeof vis);
		memset(c,0,sizeof c);
		for(int i=1;i<=m;i++)
		{
			int x,y;
			cin>>x>>y;
			f[find(x)]=find(y); 
		}
		for(int i=1;i<=n;i++) f[i]=find(i);
		int q;cin>>q;
		for(int i=1;i<=q;i++)
		{
			cin>>Q[i].l>>Q[i].r;
			Q[i].id=i;
			ans[i]=0;
		}
		sort(Q+1,Q+1+q);
		int pre=1;
		for(int i=1;i<=q;i++)
		{
			for(int j=pre;j<=Q[i].r;j++)
			{
				if(vis[f[j]]) add(vis[f[j]],-1);
				add(j,1);
				vis[f[j]]=j;
			} 
			ans[Q[i].id]=query(Q[i].r)-query(Q[i].l-1);
			pre=Q[i].r+1;
		}
		for(int i=1;i<=q;i++) cout<<ans[i]<<endl; 
	}
	return 0;
}

上一题

© 2025 nowcoder.com