题意
题意不明,队友告诉我对于每个\(i\),所在下标\(p[i]\),在\([p[i]-k,p[i]+k]\)中找到小于\(i\)的最大数\(x\),然后\(ans[i]=ans[x]+1\)即可。
分析
- 第一种方法无脑主席树,求区间小于某个值的最大数。
- 第二种方法是线段树,因为对于每个数\(i\),只有比他小的数才有用,所以从小到大枚举,在线段树中(此时所有值都小于\(i\)),查询区间最大值即可。
代码
code1
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+50;
struct CT{
#define mid (l+r)/2
int tot,sum[N*30],ls[N*30],rs[N*30];
void init(){
tot=0;
}
int build(int l,int r){
int rt=++tot;
sum[rt]=ls[rt]=rs[rt]=0;
if(l<r){
ls[rt]=build(l,mid);
rs[rt]=build(mid+1,r);
}
return rt;
}
int update(int pre,int l,int r,int x){
int rt=++tot;
ls[rt]=ls[pre];
rs[rt]=rs[pre];
sum[rt]=sum[pre]+1;
if(l<r){
if(x<=mid){
ls[rt]=update(ls[pre],l,mid,x);
}else{
rs[rt]=update(rs[pre],mid+1,r,x);
}
}
return rt;
}
int query(int u,int v,int l,int r,int k){
if(l>=r){
if(l<k && sum[v]-sum[u]){
return l;
}else{
return 0;
}
}
if(k<=mid+1 || sum[rs[v]]-sum[rs[u]]==0){
return query(ls[u],ls[v],l,mid,k);
}
int t=query(rs[u],rs[v],mid+1,r,k);
if(t){
return t;
}else{
return query(ls[u],ls[v],l,mid,k);
}
}
void debug(int rt,int l,int r){
printf("%d %d %d\n",l,r,sum[rt]);
if(l==r){
return;
}
debug(ls[rt],l,mid);
debug(rs[rt],mid+1,r);
}
}ac;
int tr[N];
int T,n,k,a[N],p[N],ans[N];
int main(){
// freopen("in.txt","r",stdin);
scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
p[a[i]]=i;
}
ac.init();
tr[0]=ac.build(1,n);
for(int i=1;i<=n;i++){
tr[i]=ac.update(tr[i-1],1,n,a[i]);
}
ans[1]=1;
for(int i=2;i<=n;i++){
int L=max(1,p[i]-k);
int R=min(n,p[i]+k);
int x=ac.query(tr[L-1],tr[R],1,n,i);
ans[i]=ans[x]+1;
}
for(int i=1;i<=n;i++){
printf("%d%c",ans[i],i==n?'\n':' ');
}
}
return 0;
}
code2
#include <bits/stdc++.h>
using namespace std;
#define ls i<<1
#define rs i<<1|1
#define mid (l+r)/2
const int N=1e5+50;
int ans[N];
int T,n,k,a[N],p[N];
int mx[N*4];
void pushup(int i){
mx[i]=max(mx[ls],mx[rs]);
}
void build(int i,int l,int r){
mx[i]=0;
if(l==r){
return;
}
build(ls,l,mid);
build(rs,mid+1,r);
pushup(i);
}
int query(int i,int l,int r,int ql,int qr){
if(ql<=l && qr>=r){
return mx[i];
}
int ans=0;
if(ql<=mid){
ans=max(ans,query(ls,l,mid,ql,qr));
}
if(qr>mid){
ans=max(ans,query(rs,mid+1,r,ql,qr));
}
return ans;
}
void update(int i,int l,int r,int p,int v){
if(l==r){
mx[i]=v;
return;
}
if(p<=mid){
update(ls,l,mid,p,v);
}else{
update(rs,mid+1,r,p,v);
}
pushup(i);
}
int main(){
// freopen("in.txt","r",stdin);
scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
p[a[i]]=i;
}
build(1,1,n);
for(int i=1;i<=n;i++){
int L=max(1,p[i]-k);
int R=min(n,p[i]+k);
int x=query(1,1,n,L,R);
update(1,1,n,p[i],i);
ans[i]=ans[x]+1;
}
for(int i=1;i<=n;i++){
printf("%d%c",ans[i],i==n?'\n':' ');
}
}
return 0;
}