luogu#B3665. 小清新数据结构题

小清新数据结构题

题目描述

给定 nn 条数据,第 ii 条数据有 sis_i 个数,依次记为 ai,1,ai,2,ai,sia_{i, 1}, a_{i, 2}, \dots a_{i, s_i}

现在有 qq 次询问,每次询问第 xx 条数据的第 yy 个数,即 ax,ya_{x,y} 是多少。

为了避免输出过大,你只需要输出所有询问的答案的按位异或和。

按位异或指的是 C++ 中的「^」运算符。你可以参考「说明/提示」中的代码求出若干个数的按位异或和。

输入格式

第一行是两个整数,表示数据条数 nn 和询问次数 qq

接下来 nn 行,每行依次表示一条数据,每行首先是一个整数,表示本条数据的数字个数 sis_i,接下来 sis_i 个整数,依次表示本条数据的每个数字。

接下来 qq 行,每行两个整数 x,yx, y,表示一次查询。

输出格式

输出一行一个整数表示所有询问的答案的按位异或之和。

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

提示

样例 1 解释

第一次询问的结果为 55,第二次询问的结果为 22。他们做按位异或的结果为 77

数据规模与约定

对于全部的测试点,保证 1n,q,si3×1061 \leq n, q, s_i \leq 3 \times 10^60ai<2320 \leq a_i \lt 2^{32}1xn1 \leq x \leq n1ysx1 \leq y \leq s_x,且 i=1nsi5×106\sum\limits_{i = 1}^n s_i \leq 5 \times 10^6,即 s1+s2++sn5×106s_1 + s_2 + \dots + s_n \leq 5 \times 10^6

提示

对于使用 C++ 的选手,你可以用如下的函数返回若干个数的按位异或和。

#include <vector>
unsigned int getXorSum(const std::vector<unsigned int>& rec) {
  unsigned ret = 0;
  for (int i = 0; i < rec.size(); ++i) ret ^= rec[i];
  return ret;
} // 将需要求按位异或和的数放在 vector 中传参。

请注意大量数据读入对程序效率造成的影响。