Greedy Sequence（主席树-区间小于每个数的最大值）

You're given a permutation $10^51≤n≤105).$

For each $sis_isi by the following rules:$

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

Consider two sequences $[c_1, c_2, ... c_n]C=[c1,c2,...cn] and D=[d1,d2,...,dn]D=[d_1, d_2, ..., d_n]D=[d1,d2,...,dn], we say the weight of CCC is higher than that of DDD if and only if there exists an integer kkk such that 1≤k≤n1 le k le n1≤k≤n, ci=dic_i=d_ici=di for all 1≤i<k1 le i < k1≤i<k, and ck>dkc_k > d_kck>dk.$

If for each $ci=dic_i=d_ici=di, the weight of CCC is equal to the weight of DDD.$

For each $sis_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

Each test case contains two lines, the first line contains two integers $10^51≤n,k≤105), the second line contains nnn distinct integers a1,a2,...,ana_1, a_2, ..., a_na1,a2,...,an (1≤ai≤n1 le a_i le n1≤ai≤n) separated by a space, which is the permutation aaa.$

Output

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

$∣si∣|s_i|∣si∣ is the number of non-zero elements of sequence sis_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
解题思路: 题目意思找[x-k,x+k]区间里小于其的最大值,然后在用那个数去更新 位置一个单调递减的数列！

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int tot=0,t,n,k;
 4 const int maxn=1e5+5;
 5 struct Node{
 6     int l,r,sum;
 7 }A[maxn*32];
 8 int arr[maxn],root[maxn];
 9 int ma[maxn],res[maxn];
10 
11 void updata(int left,int right,int &now,int pre,int value){
12     A[++tot]=A[pre],now=tot,A[now].sum++;
13     if(left==right) return;
14     int mid=left+right>>1;
15     if(mid>=value) updata(left,mid,A[now].l,A[pre].l,value);
16     else updata(mid+1,right,A[now].r,A[pre].r,value);
17 }
18 
19 int query(int left,int right,int x,int y,int value){   //返回的小于某个数的最大值
20     if(A[y].sum-A[x].sum==0) return -1;   //当前区间的个数为0则减枝;
21     if(left==right){      //递归到叶子节点
22         return left<value?left:-1;
23     }
24     int mid=left+right>>1;
25     if(value<=mid+1||A[A[y].r].sum-A[A[x].r].sum==0){  //查找的数在左边或者右边没有shu
26         return query(left,mid,A[x].l,A[y].l,value);
27     }
28     int t=query(mid+1,right,A[x].r,A[y].r,value);  //先查找右边
29     if(t==-1) query(left,mid,A[x].l,A[y].l,value);
30     else return t;
31 
32 }
33 
34 int main(){
35     ios::sync_with_stdio(false);
36     cin>>t;
37     while(t--){
38         memset(root,0,sizeof(root)),tot=0,memset(A,0,sizeof(A));
39         cin>>n>>k;
40         for(int i=1;i<=n;i++) cin>>arr[i],ma[arr[i]]=i;
41         for(int i=1;i<=n;i++) updata(1,n,root[i],root[i-1],arr[i]);
42         res[1]=1;
43         for(int i=2;i<=n;i++){
44             int L=max(1,ma[i]-k);
45             int R=min(n,ma[i]+k);
46             int flag=query(1,n,root[L-1],root[R],i);
47             if(flag==-1) res[i]=1;
48             else res[i]=res[flag]+1;   //递推的公式
49         }
50         for(int i=1;i<=n;i++){
51             printf("%d%c",res[i],i==n?'
':' ');
52         }
53     }
54     return 0;
55 }

主席树

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int t,n,m;
 4 const int maxn=1e5+5;
 5 int sum[maxn<<2];
 6 int ma[maxn],res[maxn],arr[maxn];
 7 void updata(int rt) { sum[rt]=max(sum[rt<<1],sum[rt<<1|1]); }  //区间存的是最大值
 8 void build(int l,int r,int rt){
 9     sum[rt]=0;
10     if(l==r) {return;}
11     int mid=l+r>>1;
12     build(l,mid,rt<<1);
13     build(mid+1,r,rt<<1|1);
14     updata(rt);
15 }
16 void add(int l,int r,int rt,int pos,int value){
17     if(l==r) {sum[rt]=value;return;}
18     int mid=l+r>>1;
19     if(mid>=pos) add(l,mid,rt<<1,pos,value);
20     else add(mid+1,r,rt<<1|1,pos,value);
21     updata(rt);
22 }
23 int query(int l,int r,int rt,int L,int R,int value){
24     if(L<=l&&R>=r) return sum[rt];
25     int mid=l+r>>1;
26     int ans=0;
27     if(mid>=L) ans=max(ans,query(l,mid,rt<<1,L,R,value));
28     if(R>mid) ans=max(ans,query(mid+1,r,rt<<1|1,L,R,value));
29     return ans;
30 }
31 
32 int main(){
33     ios::sync_with_stdio(false);
34     cin>>t;
35     while(t--){
36         cin>>n>>m;
37         for(int i=1;i<=n;i++){
38             cin>>arr[i];
39             ma[arr[i]]=i;
40         }
41         build(1,n,1);
42         for(int i=1;i<=n;i++){
43             int L=max(1,ma[i]-m);
44             int R=min(n,ma[i]+m);
45             int x=query(1,n,1,L,R,i);   //小于这个数的最大值
46             add(1,n,1,ma[i],i);   //后添加必定保证是小于其的数
47             res[i]=res[x]+1;
48         }
49         for(int i=1;i<=n;i++)
50             printf("%d%c",res[i],i==n?'
':' ');
51     }
52     return 0;
53 }

线段树