UOJ Logo Universal Online Judge

UOJ

#227. 【UR #15】奥林匹克数据结构

统计

各位观众,各位观众,您现在收看的是第 666 届跳蚤奥运会的比赛现场。在刚刚的环城马拉松比赛中,天才跳高小将“最强跳蚤”靠着“最强跳蚤跳跳跳”和经验丰富的伏特跳蚤国王大战了三天三夜,最后战成 $233:233$ 平。考虑到迟迟不能决出胜者,比赛组委会决定临时更换比赛项目,而被选中的则是在跳蚤大陆流行已久的运动项目——维护数据结构。

维护数据结构可是个大麻烦!首先我来介绍一下数据结构比赛的规则,你有一个长度为 $n$ 的排列 $a$,比赛分为 $q$ 轮,第 $i$ 轮选手将会得到长度为 $m_i$ 的排列 $b_i$,对于一个 $x$($1 \le x \le n - m_i + 1$),它被称为合法的仅当序列 $a_x, a_{x + 1}, \cdots, a_{x + m_i - 1}$ 与序列 $b$ 相似,现在你需要统计合法的 $x$ 的数量。

两个序列长度为 $m$ 的序列 $u$ 和 $v$ 被称为相似的,当且仅当对于任意 $1 \le i < j \le n$,要么 $u_i < u_j, v_i < v_j$,要么 $u_i > u_j, v_i > v_j$。

你看,现在所有的序列都已经给出了,选手们已经开始着手计算了。这看上去将会是一场非常激烈的比赛啊。

观众朋友们也可以和选手同台竞技,最早给出答案的观众可以获得小高铁一列哦。

输入格式

第一行一个只可能是 $0$ 或者 $1$ 的自然数 $\mathrm{type}$,含义在下面解释。

接下来一行一个正整数 $n, q$。

接下来一行 $n$ 个正整数,表示排列 $a$。

接下来 $q$ 行,其中第 $i$ 行的第一个整数为 $m_i$,接下来 $m_i$ 个正整数,表示排列 $b_i$。

注意给出的 $b_i$ 可能是经过加密的,如果 $\mathrm{type} = 1$,那么假设上一个询问的答案为 $\mathrm{ans}$(若为第一个询问则 $\mathrm{ans} = 0$),则应该进行变换 $c_{i, (j + \mathrm{ans} - 1) \bmod m_i + 1} = b_{i, j}$ 得到 $c_i$ 并将 $c_i$ 作为这次的询问序列。

输出格式

输出 $q$ 行,每行一个整数表示每个询问对应的合法的 $x$ 的数量。

样例一

input

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

output

5
2
2

explanation

实际上的三个询问序列分别是: \begin{equation} \{1\}, \{1, 2\}, \{1, 3, 2\} \end{equation}

对于第一个询问,由于长度为 $1$,所有长度为 $1$ 的区间都和询问序列相似。

对于后两个询问,$x$ 可以为 $1, 3$。

样例二

见样例数据下载。

样例三

见样例数据下载。

限制与约定

测试点编号 $n$ $q$ $\sum{m_i}$ 限制与约定
1$\le 2000$$\le 50$$\le 10000$$\mathrm{type} = 0$
2
3
4
5$\le 100000$$\le 500000$
6
7$\le 500000$
8
9
10
11
12
13$\le 100000$$\le 500000$$m_i \le 25$
14
15
16
17
18
19
20

在所有数据中,满足 $1 \le n \le 100000, \sum{m_i} \le 500000, 1 \le m_i \le n$, $a$ 和 $b_i$ 均为排列。

时间限制:$1\texttt{s}$

空间限制:$1\texttt{GB}$

下载

样例数据下载