QOJ.ac

QOJ

Time Limit: 3 s Memory Limit: 512 MB Total points: 100
[0]

# 8364. permutation

Statistics

你最近学习了逆序数的 O(nlogn) 算法。

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

选择 ij 满足 1i<jnPi>Pj,然后交换 PiPj

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

现在有 m 个长度为 n 的排列 P1,P2,,Pm,记 fi 为从 Pj 可达 Pij 的个数,试求所有 fi 的值。

输入格式

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

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

输出格式

m 行,其中第 i 行输出 fi

样例一

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

数据范围与提示

  • 子任务 110 分):n7,m2000
  • 子任务 222 分):n8
  • 子任务 319 分):m2000
  • 子任务 449 分):无特殊限制。

对于 100% 的数据,1n91m3×105

时间限制:3s

空间限制:512MB