L2-049 鱼与熊掌

本题传送门

解题思路

这里提供两种思路：

1. 用个vector<set> 来放个邻接表，每个单位是一个集合，代表每个人拥有的物品数。然后查询的时候，遍历所有人，只要在他的集合里既存在l，又存在r
   就计数加一。最后输出

2. 使用vector 来放个邻接表，每个单位代表拥有这个物品的人有哪些，然后对于查询的物品，由于每个数组里面的数据已经是排好序的（因为输入的时候就是顺序输入的） ， 使用双指针a,b，如果两个索引对应的数相等，就计数加一，然后指针向后移动。如果a对应的小于b对应的，就让a++，如果b小，就b++

方法二的时间复杂度更低，方法一算是擦边球，不过由于天梯赛的数据小，也能过。方法一可以用count降低遍历的时间开销。

这里只给出思路一的代码

ac✅️代码

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

vector<int> who_has[100010];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
	int n,m;
	cin>>n>>m;
	for(int i = 1 ; i <= n ; i++)
	{
		int k;cin>>k;
		
		for(int j = 1 ; j <= k ; j ++)
		{
			int x;cin>>x;
			who_has[x].push_back(i);
			
		}
//		sort(who_has[i].begin() , who_has[i].end());
	}
	
	for(int i = 1 ; i <= m ; i ++)
	{
		sort(who_has[i].begin() , who_has[i].end());
	}
	
	int k;cin>>k;
	for(int i = 1 ; i <= k ; i++)
	{
		int l,r;cin>>l>>r;
		int a = 0 , b = 0 ;
		
		const vector<int>& listA = who_has[l];
		const vector<int>& listB = who_has[r];
		int count = 0;
		while(a < listA.size() && b < listB.size() )
		{
			if( listA[a] == listB[b])
			{
				count ++;
				a ++;
				b ++;
			}
			else
			{
				if(listA[a] < listB[b])
				{
					a ++;
				}
				else b ++;
			}
		}
		cout<<count<<"\n";
	}
	return 0;
}