《孟子 · 告子上》有名言：“鱼，我所欲也，熊掌，亦我所欲也；二者不可得兼，舍鱼而取熊掌者也。”但这世界上还是有一些人可以做到鱼与熊掌兼得的。 给定 n 个人对 m 种物品的拥有关系。对其中任意一对物品种类（例如“鱼与熊掌”），请你统计有多少人能够兼得？ 输入格式： 输入首先在第一行给出 2 个正整数，分别是：n（≤10 5 ）为总人数（所有人从 1 到 n 编号）、m（2≤m≤10 5 ）为物品种类的总数（所有物品种类从 1 到 m 编号）。 随后 n 行，第 i 行（1≤i≤n）给出编号为 i 的人所拥有的物品种类清单，格式为： K M[1] M[2] … M[K] 其中 K（≤10 3 ）是该人拥有的物品种类数量，后面的 M[*] 是物品种类的编号。题目保证每个人的物品种类清单中都没有重复给出的种类。 最后是查询信息：首先在一行中给出查询总量 Q（≤100），随后 Q 行，每行给出一对物品种类编号，其间以空格分隔。题目保证物品种类编号都是合法存在的。 输出格式： 对每一次查询，在一行中输出两种物品兼得的人数。 用C++

<think>好的，我现在得仔细看看这个问题。题目是说，给定n个人和m种物品，每个人的物品清单是已知的。然后有多个查询，每次给出两个物品的编号，问有多少人同时拥有这两个物品。这个问题需要高效处理，因为n和m都可能很大，达到1e5级别，而且每个人的物品数量可能到1e3。那怎么处理呢？ 首先，我得想到怎么快速查询两个人是否同时拥有某两个物品。直接想到的是，对于每个物品，维护一个拥有它的人的集合。然后当查询两个物品a和b时，只需要找出这两个集合的交集的大小。这样就能得到同时拥有这两个物品的人数。 但是这里的问题是，如何高效地计算两个集合的交集的大小。因为n很大，每个物品的拥有者可能很多，直接遍历两个集合的话，如果两个集合都很大，时间复杂度可能会很高。比如，如果每个物品有1e5人，那么交集操作的时间可能很高，尤其是当Q是100的时候，这样的操作可能无法在时间限制内完成。 那有没有更高效的方法呢？可能需要用到位运算或者哈希的方法。比如，可以用位图来表示每个物品的拥有者，但m和n都可能到1e5，这样位图的大小会是1e5位，也就是大约12KB每个物品。对于m=1e5来说，总内存会是1e5*12KB=1.2e6 KB，也就是1.2GB左右，这可能会超出内存限制，特别是在C++中，可能无法这样处理。 那有没有其他方法？比如，对于每个物品，将拥有它的人的编号存储在一个有序的数组中。这样，当求两个物品的交集时，可以使用双指针的方法来遍历两个有序数组，统计共同元素的数量。这种方法的时间复杂度是两个数组长度的总和，假设每个物品的平均拥有者数量是k的话，那么每次查询的时间是O(k)，但k可能很大，比如1e5。当Q是100时，总时间是1e7，这在C++中应该可以通过。 那这样的方法是否可行？比如，对于每个物品，维护一个有序的数组，保存拥有者的编号。然后，对于每个查询的两个物品，将它们对应的数组进行双指针遍历，计算交集的元素数目。这样，每次查询的时间是O(a + b)，其中a和b是两个数组的长度。 那现在的问题是如何存储这些数组。比如，可以用一个vector数组，其中每个元素对应一个物品的拥有者列表。然后，当输入每个人的物品列表时，将他的编号添加到对应物品的vector中。最后，每个vector排序一次，这样在查询时就可以用双指针法快速统计。 但是，每个人的物品清单可能有多个物品，例如，假设一个人有K个物品，那么需要将他的编号添加到这K个物品的vector中。因为每个人的K可以达到1e3，所以总共有n*K次操作，假设n是1e5，K是1e3，总次数是1e8次操作，这在C++中应该还是可以接受的，但需要优化输入输出。 另外，排序每个物品的拥有者列表的时间。假设每个物品的拥有者数量是平均k，那么总排序时间是m * k log k。例如，如果k平均是100，那么总时间大约是1e5 * 100 * log 100 ≈ 1e7 * 5 = 5e7次操作，这应该没问题。但是如果某个物品的拥有者特别多，比如n=1e5，那么排序时间可能很高。比如，某个物品被所有人拥有，那么排序时间是1e5 log 1e5 ≈ 5e5次操作，而总共有m=1e5这样的物品的话，总时间会是5e10，这显然不行。所以这种方法可能有问题？ 或者，是否可以在每次添加人的编号到物品的vector时，直接保持有序？比如，每次插入时都维护有序性。这样，插入的时间复杂度是O(k)，因为vector的插入需要移动元素。但对于每个物品来说，每次添加一个人的时候，可能都要线性时间。比如，一个人有K=1e3的物品，每个物品的vector中插入该人的编号时，假设每个插入需要O(k)的时间，那么总时间复杂度会是n*K*k的平均值。这可能变得很大。例如，假设每个物品平均有1e3人，那么每个人添加K=1e3次，每次插入的时间是O(1e3)，总时间会是n*K*avg_k = 1e5 * 1e3 * 1e3 = 1e11次操作，这显然远远超过时间限制。 所以，这种方法不可行。那必须换思路。 那有没有其他方法？比如，预先处理每个物品的拥有者列表，然后在每次处理的时候，保持列表有序？或者，先收集所有数据，然后对每个物品的列表进行排序一次？ 比如，当读取每个人的物品列表时，将他们的编号添加到对应的物品的列表中，在完成所有人的处理后，对每个物品的列表进行排序。这样，总时间是对每个物品的列表进行排序的总时间。假设每个物品的列表平均有k个元素，总排序时间是O(m * k log k)。如果每个物品平均k=100，那么总时间是1e5 * 100 * 10 ≈ 1e7，这应该没问题。但是如果某个物品的列表很大，比如k=1e5，那么排序时间是O(1e5 log 1e5)≈5e5次操作，总共有这样的物品的话，比如m=1e5，总时间可能不行。但题目中的n是1e5，每个物品最多被n个人拥有。假设m=1e5，那么每个物品的平均拥有者数是n/m=1。例如，当n=1e5，m=1e5时，每个物品可能平均被一个人拥有。那么每个物品的列表长度为1，排序时间为O(1)。这样总排序时间是O(m),即1e5次操作，没问题。因此，这样的处理方式是可行的。 那么，正确的做法是： 1. 为每个物品维护一个vector，保存拥有者的编号。当处理每个人的物品时，将他的编号添加到对应的物品的vector中。处理完所有人之后，对每个物品的vector进行排序。 2. 对于每个查询的两个物品a和b，取它们的拥有者列表，然后用双指针的方法计算两个有序数组的交集元素数目。 这样，每次查询的时间复杂度是O(a + b)，其中a和b是两个物品的拥有者列表的长度。 那这样的方法是否能通过时间限制？ 假设最坏情况下，每个查询的两个物品的列表长度都是1e5，那么每次查询需要遍历2e5次，而Q=100次的话，总时间2e7次操作，这在C++中应该可以通过。 因此，这样的方法是可行的。 那现在需要解决的问题是： 如何高效地存储每个物品的拥有者列表，并对其进行排序。 接下来，具体的步骤： 输入部分： 首先，读取n和m。 然后，读取n行，每行代表一个人的物品列表。对于每个物品，将当前人的编号添加到对应的vector中。 处理完后，对每个物品的vector进行排序。 然后处理Q个查询，每个查询给出两个物品a和b，计算它们的拥有者列表的交集大小。 那现在的问题是，如何高效计算两个有序数组的交集的大小。可以用双指针的方法： 例如，数组A和数组B都是有序的。初始指针i=0，j=0。count=0。 当i < len(A)且j < len(B): 如果A[i] == B[j]，则count++，i++, j++. 如果A[i] < B[j]，i++. 否则，j++. 这样，遍历结束后，count就是交集的大小。 这样的算法的时间复杂度是O(a + b)。 所以，对于每个查询，调用这个函数即可。 那现在的问题是，如何处理每个物品的vector的存储。可以用一个数组，每个元素对应一个物品的vector。例如，在C++中，可以用一个vector数组，数组的索引是物品的编号。注意，物品的编号从1到m，所以数组的大小应该是m+1，或者直接物品编号从0开始处理？要看题目中的输入是否从1开始。题目中给出的物品种类编号是从1到m，所以数组的大小应该是m+1，索引1到m。 例如，在C++中： vector<int> items[m+1]; // 索引从1到m。 然后，对于每个人i（从1到n），处理他的K个物品，每个物品M[j]，将i添加到items[M[j]]中。 处理完所有人之后，对每个items[x]（x从1到m）进行排序。 那么，在排序的时候，每个vector的元素是有序的，因为每个人的编号是按顺序添加的，但不同人的添加顺序会导致每个物品的拥有者列表是无序的。例如，人1添加物品5，人3添加物品5，人2添加物品5，那么items[5]中的顺序是1,3,2。所以必须进行排序。 所以，在处理完所有输入之后，必须对每个物品的列表进行排序。 这在C++中可以这样做： for (int i = 1; i <= m; i++) { sort(items[i].begin(), items[i].end()); } 然后，对于每个查询a和b，取出items[a]和items[b]的列表，然后用双指针的方法计算交集的元素数目。 这样的处理方式是正确的。 那现在，如何处理输入的效率？ 因为n可以达到1e5，每个人可能有1e3的物品，所以总共有n*K次插入操作，其中K是平均每个用户的物品数。假设K=1e3，n=1e5，总共有1e8次插入操作。这在C++中，使用vector的push_back是可以处理的，因为每次操作是O(1)的。 然后排序每个物品的列表。假设每个物品的列表的平均长度是n/m，当n=1e5，m=1e5时，每个物品的列表平均长度是1。那么排序的总时间是可接受的。 所以，这样的方法是可行的。 那现在，编写代码的大致步骤： 读取n和m。 初始化一个大小为m+1的vector数组。 然后读取n行，每行对应一个人的物品。对于第i人（编号i），读取K，然后K个物品编号，将i添加到每个对应的物品的vector中。 然后，对每个物品的vector进行排序。 处理Q个查询，每个查询给出两个物品a和b，取它们的vector，用双指针法计算交集的大小。 注意，在双指针法中，可能遇到两个列表的长度差异较大的情况。比如，a的列表长度是1e5，而b的列表长度是1。这时候，双指针法的时间是O(1e5 +1) = O(1e5)。这可能对于Q=100来说，总时间是1e7次操作，在C++中应该没问题。 另外，需要注意物品的编号是否是从1开始的。根据题目描述，是的。 那现在，编写代码的注意事项： 1. 输入的读取要高效。在C++中，使用scanf而不是cin，可以更快。 因为输入的数据量可能较大，尤其是每个人的物品可能有1e3个，总共有1e5人，总输入量是1e5*(1e3+1) ≈1e8个数。所以，必须使用快速的输入方式。 例如，对于每一行的人的数据： 读取K，然后读取K个物品编号。可以用scanf逐个读取。 或者，读取整行，然后按空格分割。这可能比较复杂，但在C++中，使用scanf循环读取更简单。 例如： for (int i = 1; i <= n; ++i) { int K; scanf("%d", &K); for (int j = 0; j < K; ++j) { int x; scanf("%d", &x); items[x].push_back(i); } } 这样处理每个人的数据。 2. 排序每个物品的vector： for (int i = 1; i <= m; ++i) { sort(items[i].begin(), items[i].end()); } 3. 处理每个查询： 读取a和b，取两个vector，计算它们的交集的大小。 编写一个函数来计算两个有序数组的交集元素数目： int count_common(const vector<int>& a, const vector<int>& b) { int i = 0, j = 0; int cnt = 0; while (i < a.size() && j < b.size()) { if (a[i] == b[j]) { cnt++; i++; j++; } else if (a[i] < b[j]) { i++; } else { j++; } } return cnt; } 然后，每个查询调用这个函数即可。 这样，整个算法的时间复杂度应该是可以接受的。 测试样例： 例如，假设输入： 3 2 1 1 2 1 2 1 2 1 1 2 那么，物品1的拥有者是1和2。物品2的拥有者是2和3。查询1和2的交集，也就是同时拥有1和2的人是2号。所以输出是1。 这样，这个代码可以正确处理。 那这样的方法应该可以解决问题。现在需要考虑可能的优化。 比如，当物品的拥有者列表非常长时，双指针法可能较慢。是否有更优的方法？ 比如，可以用二分查找。例如，对于一个较短的列表中的每个元素，在另一个较长的列表中进行二分查找，判断是否存在。这样的时间复杂度是O(s log l)，其中s是较短列表的长度，l是较长列表的长度。这在某些情况下可能更优。 例如，如果a的列表长度是1e5，b的列表长度是1e5，那么双指针法是O(2e5)。而如果a的列表长度是100，b的列表长度是1e5，那么二分查找的时间是O(100 log 1e5) ≈ 100*17=1700次操作，而双指针法是O(1e5+100)≈1e5次操作。此时，二分查找显然更优。 所以，为了优化，可以判断两个列表的长度，如果其中一个较短，则遍历较短的列表，并在较长的列表中二分查找是否存在该元素。 这样，可以优化查询的时间。 所以，如何选择双指针法和二分法？ 可以比较两个列表的长度，假设其中一个的长度是x，另一个是y。假设x < y。则遍历x中的每个元素，在y中进行二分查找。时间复杂度是x * log y。而双指针法的复杂度是x + y。当x * log y < x + y时，即 log y < 1 + y/x。例如，当x是较小的数，y是较大的数时，这可能成立。 例如，当x=100，y=1e5： log y = 17, y/x = 1000. 17 < 1+1000 →成立。所以二分法更优。 当x=1e4，y=1e5: log y=17, y/x=10 → 17 <11? 不成立。所以双指针法更优（1e4+1e5=1.1e5 <1e4 *17=1.7e5）。 所以，在这种情况下，需要判断哪种方法更好。 因此，可以在代码中进行优化，当两个列表的长度差异较大时，选择二分法。例如，当其中一个列表的长度比另一个小很多时，比如，当min(a.size(), b.size()) * log(max_size) < a.size() + b.size()，则使用二分法，否则使用双指针法。 但这样的判断可能在代码中难以实现，或者在大多数情况下，双指针法已经足够快，而无需复杂的优化。例如，在本题的测试数据中，可能不会有极端情况，所以双指针法可能已经足够。 但为了应对极端情况，例如一个列表很大而另一个很小，可以优化处理。例如，在count_common函数中，根据两个数组的长度选择不同的方法： int count_common(const vector<int>& a, const vector<int>& b) { // 选择较短的一个进行遍历 const vector<int>* pa = &a; const vector<int>* pb = &b; if (a.size() > b.size()) { swap(pa, pb); // 让pa指向较短的数组 } int cnt = 0; // 遍历pa的每个元素，在pb中查找是否存在 for (int x : *pa) { if (binary_search(pb->begin(), pb->end(), x)) { cnt++; } } return cnt; } 这样，当其中一个数组较短时，可以快速通过二分查找得到结果。例如，当a.size()=100，b.size()=1e5时，进行100次二分查找，每次log(1e5)≈17次操作，总次数是1700次，而双指针法需要1e5次操作。这明显更快。 那这样的方法是否更好？ 是的。例如，对于两个数组长度差距较大的情况，可以显著减少时间。而当两个数组长度相近时，比较两者的时间复杂度。例如，假设a和b的长度都是n。此时双指针的时间复杂度是2n，而二分查找的时间复杂度是n log n。显然，双指针法更好。所以，我们需要根据情况选择不同的方法。 那如何判断在什么情况下使用哪种方法？ 比如，当较短数组的长度是s，较长数组的长度是 l。则，如果 s * log l < s + l →使用二分法，否则使用双指针法。 例如，s=1000，l=1000 → s log l = 1000*10=1e4，而s + l=2000。此时，1e4>2000，所以双指针更好。 当s=100，l=1e5 → 100*17=1700 < 100 +1e5=100100 → 使用二分法。 因此，需要计算这两个时间，并选择较小的方式。 那在代码中，可以进行比较，根据情况选择使用双指针还是二分法。 但这样会增加代码的复杂度。例如，在C++中，如何实现？ 可以编写一个函数，根据两个数组的长度，选择最优的方式： int count_common_optimized(const vector<int>& a, const vector<int>& b) { if (a.empty() || b.empty()) return 0; const vector<int>* shorter = &a; const vector<int>* longer = &b; if (a.size() > b.size()) { swap(shorter, longer); } int s_len = shorter->size(); int l_len = longer->size(); // 计算两种方法的比较条件 bool use_binary = (s_len * log2(l_len) < s_len + l_len); if (use_binary) { int cnt = 0; for (int x : *shorter) { if (binary_search(longer->begin(), longer->end(), x)) { cnt++; } } return cnt; } else { // 使用双指针法 int i = 0, j = 0; int cnt = 0; while (i < s_len && j < l_len) { if ((*shorter)[i] == (*longer)[j]) { cnt++; i++; j++; } else if ((*shorter)[i] < (*longer)[j]) { i++; } else { j++; } } return cnt; } } 但这样的条件判断可能引入浮点运算，而log2的计算可能不够精确，或者影响效率。或者，可以预先设定一个阈值，比如，当较短的数组长度小于某个值时使用二分法，否则使用双指针法。 比如，当较短的数组长度小于 sqrt(longer数组长度)时，使用二分法。或者，设定当s_len < l_len / log2(l_len)时，使用二分法。 但这种条件可能难以准确设定。或者，可以基于经验，比如当较短的数组长度小于 1000时，使用二分法，否则使用双指针法。或者，直接选择在两种方法中选最优的。 但这样可能比较复杂。或许，在代码中，对于每次查询，自动选择较短的数组进行二分查找，不管长度如何。这样，在某些情况下会更快，而在某些情况下可能更慢。 例如，当两个数组长度都很大时，比如都是1e5，那么二分法的时间是1e5 * log(1e5) ≈1e5 *17=1.7e6，而双指针法的时间是2e5。此时，双指针法明显更优。所以，在这种情况下，选择双指针法更好。 因此，必须根据具体情况选择方法。这可能比较复杂。 有没有办法在代码中自动判断哪种方法更快？ 或者，可以对于每个查询，比较s * log l 和 s + l，如果前者较小，则使用二分法，否则使用双指针法。 例如，当s是较短的数组长度，l是较长的数组长度： if (s * log2(l) < s + l) → use binary search. 否则，使用双指针法。 但log2的计算可能会比较慢。或者，可以使用预先计算的log2值，或者用近似的方式判断。 例如，在代码中，可以这样计算： double log_l = log2(l); if (s * log_l < s + l) → use binary. 否则，双指针。 但这样在每次查询时都要进行一次浮点运算，但Q最多是100次，所以这应该是可以的。 例如，在代码中： const vector<int>& a = ...; const vector<int>& b = ...; if (a.empty() || b.empty()) return 0; int s, l; if (a.size() <= b.size()) { s = a.size(); l = b.size(); } else { s = b.size(); l = a.size(); } double log_l = log2(l); if (s * log_l < s + l) { // use binary search } else { // use two pointers } 这样，每次查询时都进行这样的判断。 但这样在代码中的实现可能比较复杂，但可能带来时间上的节省。 例如，假设两个数组长度都为1e5： s=1e5, l=1e5. s*log l =1e5 *17=1.7e6，而 s+l=2e5 → 1.7e6>2e5 →使用双指针法。 当s=100，l=1e5: s*log l=100*17=1700 < 100+1e5=100100 →使用二分法。 当s=1e4，l=1e5: s*log l=1e4*17=1.7e5，s+l=1.1e5 → 1.7e5>1.1e5 →使用双指针法。 这样，条件判断是正确的。 那如何在代码中实现这样的判断？ 在C++中，可以使用log2函数，但需要注意浮点数的精度问题。或者，可以使用近似的方法。 例如，在代码中： int s_len = shorter->size(); int l_len = longer->size(); double log_l = log2(l_len); if (s_len * log_l < s_len + l_len) { // binary search } else { // two pointers } 这在代码中是可行的。 所以，可以将count_common函数改写为： int count_common(const vector<int>& a, const vector<int>& b) { if (a.empty() || b.empty()) return 0; const vector<int> *s, *l; if (a.size() <= b.size()) { s = &a; l = &b; } else { s = &b; l = &a; } int s_len = s->size(); int l_len = l->size(); double log_l = log2(l_len); bool use_binary = (s_len * log_l < s_len + l_len); if (use_binary) { int cnt = 0; for (int x : *s) { if (binary_search(l->begin(), l->end(), x)) { cnt++; } } return cnt; } else { // two pointers int i = 0, j = 0; int cnt = 0; while (i < s_len && j < l_len) { if ((*s)[i] == (*l)[j]) { cnt++; i++; j++; } else if ((*s)[i] < (*l)[j]) { i++; } else { j++; } } return cnt; } } 这样，对于每个查询，自动选择更优的方法。 这可能带来时间上的优化，但需要编写更多的代码。但考虑到题目中的时间限制，这样的优化可能是必要的，尤其是在面对极端数据时。 综上，这样的处理方式是可行的。 现在，编写整个代码的结构： #include <cstdio> #include <vector> #include <algorithm> #include <cmath> using namespace std; vector<int> items[100001]; // 物品编号从1到m int main() { int n, m; scanf("%d %d", &n, &m); for (int i = 1; i <= n; ++i) { int K; scanf("%d", &K); for (int j = 0; j < K; ++j) { int x; scanf("%d", &x); items[x].push_back(i); } } // 对每个物品的列表进行排序 for (int i = 1; i <= m; ++i) { sort(items[i].begin(), items[i].end()); } int Q; scanf("%d", &Q); while (Q--) { int a, b; scanf("%d %d", &a, &b); const vector<int>& va = items[a]; const vector<int>& vb = items[b]; // 计算交集大小 if (va.empty() || vb.empty()) { printf("0\n"); continue; } const vector<int> *s, *l; if (va.size() <= vb.size()) { s = &va; l = &vb; } else { s = &vb; l = &va; } int s_len = s->size(); int l_len = l->size(); double log_l = log2(l_len); int cnt = 0; if (s_len * log_l < s_len + l_len) { for (int x : *s) { if (binary_search(l->begin(), l->end(), x)) { cnt++; } } } else { int i = 0, j = 0; while (i < s_len && j < l_len) { if ((*s)[i] == (*l)[j]) { cnt++; i++; j++; } else if ((*s)[i] < (*l)[j]) { i++; } else { j++; } } } printf("%d\n", cnt); } return 0; } 这样，代码就完成了。需要注意的是，物品的编号可能很大，所以数组items的大小必须足够，题目中给出m≤1e5，所以数组的大小应为1e5+1。在C++中，全局变量的数组如果定义在函数外，可能占用较多的静态存储空间。如果m最大是1e5，那么vector数组的大小为1e5+1，每个vector初始是空的，这在内存中是可行的。所以，这样的声明是正确的。 另外，要注意输入的物品编号是否可能为0？题目中明确说明物品种类编号是合法存在的，且从1到m。所以无需处理0的情况。 综上，这个代码应该能够正确解决问题，并且在时间限制内运行。</think>要解决这个问题，我们需要统计能够同时拥有两种特定物品的人数。通过高效的数据结构和算法，我们可以快速处理多次查询。 ### 方法思路 1. **数据存储**：使用数组存储每个物品的拥有者列表。每个物品对应一个数组，数组中的元素是拥有该物品的人的编号。 2. **排序**：在处理完所有输入后，对每个物品的拥有者列表进行排序，以便后续高效查询。 3. **查询处理**：对于每个查询，使用双指针法或二分查找法来计算两个有序数组的交集大小，根据数组长度的不同选择最优方法以提高效率。 ### 解决代码 ```cpp #include <cstdio> #include <vector> #include <algorithm> #include <cmath> using namespace std; vector<int> items[100001]; // 物品编号从1到m int main() { int n, m; scanf("%d %d", &n, &m); for (int i = 1; i <= n; ++i) { int K; scanf("%d", &K); for (int j = 0; j < K; ++j) { int x; scanf("%d", &x); items[x].push_back(i); } } // 对每个物品的拥有者列表进行排序 for (int i = 1; i <= m; ++i) { sort(items[i].begin(), items[i].end()); } int Q; scanf("%d", &Q); while (Q--) { int a, b; scanf("%d %d", &a, &b); const vector<int>& va = items[a]; const vector<int>& vb = items[b]; if (va.empty() || vb.empty()) { printf("0\n"); continue; } const vector<int> *s, *l; if (va.size() <= vb.size()) { s = &va; l = &vb; } else { s = &vb; l = &va; } int s_len = s->size(); int l_len = l->size(); double log_l = log2(l_len); int cnt = 0; if (s_len * log_l < s_len + l_len) { for (int x : *s) { if (binary_search(l->begin(), l->end(), x)) { cnt++; } } } else { int i = 0, j = 0; while (i < s_len && j < l_len) { if ((*s)[i] == (*l)[j]) { cnt++; i++; j++; } else if ((*s)[i] < (*l)[j]) { i++; } else { j++; } } } printf("%d\n", cnt); } return 0; } ``` ### 代码解释 1. **数据输入和存储**：首先读取人数和物品种类数。然后依次读取每个人拥有的物品，并将其编号添加到对应的物品列表中。 2. **排序处理**：对每个物品的拥有者列表进行排序，以便后续查询时能够高效计算交集。 3. **查询处理**：对于每个查询，根据两个物品的拥有者列表长度选择最优方法（双指针法或二分查找法）来计算交集的大小，确保处理高效。 通过这种方法，我们能够在合理的时间内处理大规模数据，并快速响应多次查询。