4198: Maintain Multiple Sequences

# Maintain Multiple Sequences ### 内存 1024MB ### 时间 2S ## 题目描述 有$N$个整数序列。第$i$个序列$(1 ≤ i ≤ N)$有$L_i$个元素；第$i$个序列的第$j$个元素$(1 ≤ j ≤ L_i)$是$a_i,j$。 现在有$Q$个查询。对于第$k$个查询$(1 ≤ k ≤ Q)$，给定整数$s_k$和$t_k$，请找出第$s_k$个序列的第$t_k$个元素。 ## 输入格式 输入按以下格式从标准输入给出： $N$ $Q$ $L_1$ $a_{1,1}$ $\cdots$ $a_{1,L_1}$ $\vdots$ $L_N$ $a_{N,1}$ $\cdots$ $a_{N,L_N}$ $s_1$ $t_1$ $\vdots$ $s_Q$ $t_Q$ ## 输出格式 输出$Q$行。第$k$行$(1 ≤ k ≤ Q)$应包含第$k$个查询的答案。 ## 输入输出样例 ### 输入样例1 ``` 2 2 3 1 4 7 2 5 9 1 3 2 1 ``` ### 输出样例1 ``` 7 5 ``` ### 输入样例2 ``` 3 4 4 128 741 239 901 2 1 1 3 314 159 26535 1 1 2 2 3 3 1 4 ``` ### 输出样例2 ``` 128 1 26535 901 ``` ## 数据范围与提示 【样例1说明】 第$1$个序列是$(1, 4, 7)$，第$2$个序列是$(5, 9)$。 每个查询的答案如下： - 第$1$个序列的第$3$个元素是$7$。 - 第$2$个序列的第$1$个元素是$5$。 【数据范围】 $1 ≤ N, Q ≤ 2 × 10^5$ $L_i ≥ 1 (1 ≤ i ≤ N)$ $\sum_{i=1}^N L_i ≤ 2 × 10^5$ $1 ≤ a_{i,j} ≤ 10^9 (1 ≤ i ≤ N, 1 ≤ j ≤ L_i)$ $1 ≤ s_k ≤ N$ $1 ≤ t_k ≤ L_{s_k} (1 ≤ k ≤ Q)$ 所有输入值均为整数。 ## 题目来源 ABC271B