Scoring Subsequences

标签：Scoring sequence int maximum score Subsequences test subsequences

Scoring Subsequences time limit per test 2.5 seconds memory limit per test 256 megabytes input standard input output standard output

The score of a sequence [s1,s2,…,sd][1,2,…,] is defined as s1⋅s2⋅…⋅sdd!1⋅2⋅…⋅!, where d!=1⋅2⋅…⋅d!=1⋅2⋅…⋅. In particular, the score of an empty sequence is 11.

For a sequence [s1,s2,…,sd][1,2,…,], let m be the maximum score among all its subsequences. Its cost is defined as the maximum length of a subsequence with a score of m.

You are given a non-decreasing sequence [a1,a2,…,an][1,2,…,] of integers of length n. In other words, the condition a1≤a2≤…≤an1≤2≤…≤ is satisfied. For each k=1,2,…,n=1,2,…,, find the cost of the sequence [a1,a2,…,ak][1,2,…,].

A sequence x is a subsequence of a sequence y if x can be obtained from y by deletion of several (possibly, zero or all) elements.

Input

Each test contains multiple test cases. The first line contains the number of test cases t (1≤t≤1041≤≤104). The description of the test cases follows.

The first line of each test case contains an integer n (1≤n≤1051≤≤105) — the length of the given sequence.

The second line of each test case contains n integers a1,a2,…,an1,2,…, (1≤ai≤n1≤≤) — the given sequence. It is guaranteed that its elements are in non-decreasing order.

It is guaranteed that the sum of n over all test cases does not exceed 5⋅1055⋅105.

Output

For each test case, output n integers — the costs of sequences [a1,a2,…,ak][1,2,…,] in ascending order of k.

Example input Copy 3 3 1 2 3 2 1 1 5 5 5 5 5 5 output Copy

1 1 2 
1 1 
1 2 3 4 5 

Note

In the first test case:

• The maximum score among the subsequences of [1][1] is 11. The subsequences [1][1] and [][] (the empty sequence) are the only ones with this score. Thus, the cost of [1][1] is 11.
• The maximum score among the subsequences of [1,2][1,2] is 22. The only subsequence with this score is [2][2]. Thus, the cost of [1,2][1,2] is 11.
• The maximum score among the subsequences of [1,2,3][1,2,3] is 33. The subsequences [2,3][2,3] and [3][3] are the only ones with this score. Thus, the cost of [1,2,3][1,2,3] is 22.

Therefore, the answer to this case is 112112, which are the costs of [1],[1,2][1],[1,2] and [1,2,3][1,2,3] in this order.

#include <bits/stdc++.h>
//#define int long long
using namespace std;
const int N=1e5+10,mod=1e9+7;
string s;
int n,t,a[N],f[N],res,num,ans;
bool vis[N];
int op(int u)
{
    if(u==1||u==0) return 1;
    return u*op(u-1);
}
int main()
{
    std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>t;
    while(t--){
        cin>>n;
        res=0;
        for(int i=1;i<=n;i++){
            cin>>a[i];
            int l=1,r=i;
        //如果当前的数小于长度,那就肯定到不了最大值,所以求最小的当前值能让序列价值达到最大
        //二分即可
            while(l<r){
                int mid=l+r>>1;
                if(a[mid]>=i-mid+1) r=mid;
                else l=mid+1;
            }
            cout<<i-l+1<<" ";
        }
        cout<<endl;
    }
    return 0;
}

 

标签：Scoring,sequence,int,maximum,score,Subsequences,test,subsequences
From： https://www.cnblogs.com/o-Sakurajimamai-o/p/17500718.html