2019 ICPC 南京网络赛 F Greedy Sequence

You're given a permutation aa of length nn (1 \le n \le 10^51≤n≤105).

For each i \in [1,n]i∈[1,n], construct a sequence s_isi by the following rules:

s_i[1]=isi[1]=i;
The length of s_isi is nn, and for each j \in [2, n]j∈[2,n], s_i[j] \le s_i[j-1]si[j]≤si[j−1];
First, we must choose all the possible elements of s_isi from permutation aa. If the index of s_i[j]si[j] in permutation aa is pos[j]pos[j], for each j \ge 2j≥2, |pos[j]-pos[j-1]|\le k∣pos[j]−pos[j−1]∣≤k (1 \le k \le 10^51≤k≤105). And for each s_isi, every element of s_isi must occur in aa at most once.
After we choose all possible elements for s_isi, if the length of s_isi is smaller than nn, the value of every undetermined element of s_isi is 00;
For each s_isi, we must make its weight high enough.

Consider two sequences C = [c_1, c_2, ... c_n]C=[c1,c2,...cn] and D=[d_1, d_2, ..., d_n]D=[d1,d2,...,dn], we say the weight of CC is higher thanthat of DD if and only if there exists an integer kk such that 1 \le k \le n1≤k≤n, c_i=d_ici=di for all 1 \le i < k1≤i<k, and c_k > d_kck>dk.

If for each i \in [1,n]i∈[1,n], c_i=d_ici=di, the weight of CC is equal to the weight of DD.

For each i \in [1,n]i∈[1,n], print the number of non-zero elements of s_isi separated by a space.

It's guaranteed that there is only one possible answer.

Input

There are multiple test cases.

The first line contains one integer T(1 \le T \le 20)T(1≤T≤20), denoting the number of test cases.

Each test case contains two lines, the first line contains two integers nn and kk (1 \le n,k \le 10^51≤n,k≤105), the second line contains nn distinct integers a_1, a_2, ..., a_na1,a2,...,an (1 \le a_i \le n1≤ai≤n) separated by a space, which is the permutation aa.

Output

For each test case, print one line consists of nn integers |s_1|, |s_2|, ..., |s_n|∣s1∣,∣s2∣,...,∣sn∣ separated by a space.

|s_i|∣si∣ is the number of non-zero elements of sequence s_isi.

There is no space at the end of the line.

样例输入复制

2

3 1

3 2 1

7 2

3 1 4 6 2 5 7

样例输出复制

1 2 3

1 1 2 3 2 3 3

这题是队友出的，这个题好像线段树能做，但是我们是暴力加贪心做的，前几遍是枚举的区间位置纯暴力，后来是枚举左右区间长度，对于每个元素的下一个元素都是唯一固定的。之后记忆化搜索就可以求出每个序列。

#include<stdio.h>

#include<algorithm>

#include<iostream>

#include<string.h>

#include<math.h>

#include<vector>

#include<queue>

#include<map>

using namespace std;

#define LL long long

#define MAXN 100100

int a[MAXN],pos[MAXN];

int s[MAXN],oo[MAXN];

int main()

{

    int t;

    scanf("%d",&t);

    int n,k,l,r,maxx;

    while(t--){

        scanf("%d%d",&n,&k);

    for(int i=1;i<=n;i++){

        scanf("%d",a+i);

        pos[a[i]]=i;

        s[i]=1;

    }

    s[0]=0;

    for(int i=2;i<=n;i++){

        int j=i-1;

        while(j>0){

            if(abs(pos[i]-pos[j])<=k){

                s[i]+=s[j];

                break;

            }

            j--;

        }

    }

    for(int i=1;i<=n;i++){printf("%d",s[i]);if(i<n)printf(" ");}

    printf("\n");

    }

}

巴特西

2019 ICPC 南京网络赛 F Greedy Sequence

Input

Output

最新文章

热门文章