联合省选 R6

https://cplusoj.com/d/senior/contest/69a595501363e1a0769508ec

T1

水题，考虑一个数是怎么扩展的，注意到可以拆成是左、右边距离 \(>d\) 和中间距离 \(<=d\) 的，所以左右边可以分开考虑。注意到越小能扩展越远，所以说一个数往左能扩展最远的地方可以从左边距离 \(<=d\) 且值 \(>=a_i\) 的最小值转移过来，这个东西直接从大到小扫描线+线段树单点修改区间查 \(\min\) 维护，然后中间的顺便用线段树单点加+区间求和就行了。

Code

#include<bits/stdc++.h>
#define ls (k<<1)
#define rs (ls|1)
#define lm ((l+r)>>1)
#define rm (lm+1)
using namespace std;
namespace IO{#define gc getchar#define pc putchar#define ps putsinline int in(){int x=0,f=1;char c=gc();for(;!isdigit(c);c=gc())if(c=='-')f=-1;for(;isdigit(c);c=gc())x=x*10+(c-'0');return x*f;}inline void out(int x){if(x<0)pc('-'),x=-x;if(x>=10)out(x/10);pc(x%10+'0');}inline void outsp(int x){out(x),pc(' ');}inline void outln(int x){out(x),ps("");}
}
using namespace IO;
const int N=500005;
int n,d,a[N],p[N],f[N],g[N],ans[N];
namespace SGT{const int M=N<<2;int mn[M],cnt[M];int Min(int x,int y){return a[x]<a[y]?x:y;}void pushup(int k){mn[k]=Min(mn[ls],mn[rs]),cnt[k]=cnt[ls]+cnt[rs];}void update(int k,int l,int r,int x){if(l>x||r<x)return;if(l==r){mn[k]=x,cnt[k]=1;return;}update(ls,l,lm,x),update(rs,rm,r,x);pushup(k);}int query(int k,int l,int r,int s,int t){if(l>t||r<s)return 0;if(l>=s&&r<=t)return mn[k];return Min(query(ls,l,lm,s,t),query(rs,rm,r,s,t));}int count(int k,int l,int r,int s,int t){if(l>t||r<s)return 0;if(l>=s&&r<=t)return cnt[k];return count(ls,l,lm,s,t)+count(rs,rm,r,s,t);}
}
using namespace SGT;
int main(){freopen("set.in","r",stdin);freopen("set.out","w",stdout);n=in(),d=in();a[0]=N;for(int i=1;i<=n;i++)a[i]=in(),p[a[i]]=i;for(int i=n;i>=1;i--){int x=p[i],y;y=query(1,1,n,x-d,x-1);if(y)f[x]+=f[y]+count(1,1,n,y,x);y=query(1,1,n,x+1,x+d);if(y)g[x]+=g[y]+count(1,1,n,x,y);ans[x]=f[x]+g[x]+1;update(1,1,n,x);}for(int i=1;i<=n;i++)i<n?outsp(ans[i]):out(ans[i]);return 0;
}