#P16152. [2022国家队训练南京站]permutation

[2022国家队训练南京站]permutation

permutation

题目描述

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

给定一个长度为 nn 的排列 PP,定义一次操作如下:

选择两个下标 i,ji,j,满足

1≤i<j≤n,Pi>Pj,1\le i<j\le n,\qquad P_i>P_j,

然后交换 PiP_i 和 PjP_j。

对于排列 AA 和排列 BB,如果排列 AA 经过若干次上述操作可以变成排列 BB,则称 BB 是从 AA 可达的。这里“若干次”可以为 00 次,因此每个排列都可以到达自身。

现在给定 mm 个长度为 nn 的排列 P1,P2,…,PmP_1,P_2,\ldots,P_m。记 fif_i 为满足“PiP_i 可以从 PjP_j 可达”的下标 jj 的个数。请计算所有 fif_i。

注意:输入中的排列可以重复出现,计数时每个出现位置都要单独计算。

输入格式

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

接下来 mm 行,每行 nn 个整数,描述一个 1∼n1\sim n 的排列。

输出格式

输出 mm 行,其中第 ii 行输出一个整数 fif_i。

样例一

输入

3 3
1 2 3
3 1 2
2 3 1

输出

3
1
1

样例二

输入

2 2
1 2
1 2

输出

2
2

数据范围与提示

  • 子任务 11(1010 分):n≤7, m≤2000n\le 7,\ m\le 2000。
  • 子任务 22(2222 分):n≤8n\le 8。
  • 子任务 33(1919 分):m≤2000m\le 2000。
  • 子任务 44(4949 分):无特殊限制。

对于 100%100\% 的数据:

1≤n≤9,1≤m≤3×105.1\le n\le 9,\qquad 1\le m\le 3\times 10^5.