QOJ.ac

QOJ

Time Limit: 3 s Memory Limit: 512 MB Total points: 100
Statistics

你最近学习了逆序数的 $O(n \log n)$ 算法。

给定长度为 $n$ 的排列 $P$,定义对 $P$ 的一次操作如下:

选择 $i$ 和 $j$ 满足 $1 \leq i < j \leq n$ 且 $P_i > P_j$,然后交换 $P_i$ 和 $P_j$。

对于排列 $A$ 和排列 $B$,如果排列 $A$ 经过一些操作变成了排列 $B$,则称 $B$ 是从 $A$ 可达的。

现在有 $m$ 个长度为 $n$ 的排列 $P_1, P_2, \cdots, P_m$,记 $f_i$ 为从 $P_j$ 可达 $P_i$ 的 $j$ 的个数,试求所有 $f_i$ 的值。

输入格式

第一行包含两个正整数,$n$ 和 $m$,分别表示排列长度和排列的个数。

接下来 $m$ 行,每行 $n$ 个数描述一个排列。

输出格式

共 $m$ 行,其中第 $i$ 行输出 $f_i$。

样例一

input

3 3
1 2 3
3 1 2
2 3 1

output

3
1
1

样例二

input

2 2
1 2
1 2

output

2
2

数据范围与提示

  • 子任务 $1$($10$ 分):$n \leq 7, m \leq 2000$。
  • 子任务 $2$($22$ 分):$n \leq 8$。
  • 子任务 $3$($19$ 分):$m \leq 2000$。
  • 子任务 $4$($49$ 分):无特殊限制。

对于 $100\%$ 的数据,$1 \leq n \leq 9$,$1 \leq m \leq 3 \times 10^5$。

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

空间限制:$\texttt{512MB}$