#P17898. One Permutation

One Permutation

题目描述

给定一个长度为 nn 的排列 pp。

定义一个连续子段的代价,为该子段的最长严格递增子序列的长度。子序列可以删除元素,但剩余元素必须保持原来的相对顺序,不要求位置连续。

将整个排列划分为 kk 个非空、互不相交的连续子段,划分的代价为这些子段的代价之和。

记 aka_k 为所有这样的划分中,代价的最大值。请计算 a1,a2,…,ana_1,a_2,\ldots,a_n。

输入格式

第一行包含整数 tt,表示测试用例数。

每个测试用例第一行包含整数 nn,第二行包含排列 p1,p2,…,pnp_1,p_2,\ldots,p_n。

输出格式

对每个测试用例输出一行 nn 个整数,依次表示 a1,a2,…,ana_1,a_2,\ldots,a_n。

数据范围

  • 1≤t≤100001\le t\le10000;
  • 1≤n≤1000001\le n\le100000;
  • pp 是 11 到 nn 的排列;
  • 一个输入文件内所有测试用例的 nn 之和不超过 100000100000。

样例输入

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

样例输出

3 3 3
1 2 3
2 3 4 4

样例解释

第三个测试用例中,划分成两个子段 [2][2] 与 [1,4,3][1,4,3],其最长递增子序列长度分别为 11 和 22,总和为 33。