#2195. permutation

    ID: 2195 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>TEAM赛事:contest1648来源:qoj.ac数据:公开样例线段树树状数组

permutation

permutation

题目描述

标题: permutation - Problem - QOJ.ac

#8364. permutation

Statistics

The problem was used in the following contests:

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

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

选择 i 和 j 满足 1≤i<j≤n 且 Pi>Pj,然后交换 Pi 和 Pj。

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

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

输入格式

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

接下来 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

数据范围与提示

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

对于 100% 的数据,1≤n≤9,1≤m≤3×105。

时间限制:3s

空间限制:512MB

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

3 3
1 2 3
3 1 2
2 3 1
3
1
1

样例 2

2 2
1 2
1 2
2
2