先把题意做一个等价转化。
设原数组为 a1,a2,…,an,一个子数组合法,当且仅当这个子数组中任意相邻元素的差的绝对值都不超过 k。
对于相邻的两个位置 i,i+1,定义一条“边权”:
给定一个由n个整数构成的数组{a1,a2...,an};对于每个整数k(1≤k≤n),当且仅当子数组中任意相邻元素的差值的绝对值不超过k时,该子数组被称为合法子数组:请计算对于每个k,数组中合法子数组的最大长度
【名词解释】得到的新数组。
子数组:从原数组中,连续的选择一段元素(可以全选、可以不选)
每个测试文件均包含多组测试数据:
第一行输入一个整数 T(1≤T≤104),表示测试数据组数;
接下来对于每组测试数据,依次输入:
此外,保证所有测试数据中 n的总和不超过2×105。
对于每组测试数据,输出一行包含 n 个整数,第 i 个整数表示当 k=i 时合法子数组的最大长度。
输入
1
5
1 3 5 2 4
输出
1 3 5 5 5