題意：給出n個整數，構造s1，s2，s3…sn s1，s2，s3…sns1，s2，s3…sn，si sisi滿足五個條件
1、s1[i]=i s1[i]=is1[i]=i
2、對于1<j<=n 對于1<j<=n對于1<j<=n，si[j]<si[j?1] si[j]<si[j-1]si[j]<si[j?1]
3、對于任意的si[j] si[j]si[j]在a串中的位置pos[j] pos[j]pos[j]，滿足∣pos[j]?pos[j?1]∣<=k |pos[j]-pos[j-1]|<=k∣pos[j]?pos[j?1]∣<=k，且si sisi中的每一個數字只能a aa中出現一次
4、如果選擇的si sisi長度小于n nn，其余位置就填0
5、盡量使bi bibi足夠大(能得到的最大字典序)
輸出每個bi bibi的非0數字的個數。
主席樹求區間小于k的最大值。。。卡了好久都沒有寫出來，結果是函數傳參傳錯了。。
代碼如下：

#include<bits/stdc++.h> #define ll long long #define inf 0x3f3f3f3f using namespace std;const int maxx=1e5+100; struct node{int l;int r;int sum; }p[maxx<<5]; int a[maxx],root[maxx],vis[maxx],cnt[maxx]; int n,k,tot;inline void pushup(int cur) {p[cur].sum=p[p[cur].l].sum+p[p[cur].r].sum; } inline int build(int l,int r) {int cur=++tot;p[cur].sum=0;if(l==r) return cur;int mid=l+r>>1; p[cur].l=build(l,mid);p[cur].r=build(mid+1,r);return cur; } inline int update(int rot,int pos,int l,int r) {int cur=++tot;p[cur]=p[rot];if(l==r) {p[cur].sum++;return cur;}int mid=l+r>>1;if(pos<=mid) p[cur].l=update(p[rot].l,pos,l,mid);else p[cur].r=update(p[rot].r,pos,mid+1,r);pushup(cur);return cur; } inline int query(int pos,int l,int r,int lrot,int rrot) {if(l==r){if(p[rrot].sum-p[lrot].sum>0) return l;else return 0;}int mid=l+r>>1;if(pos>mid){ int ans=0;if(pos>=r){if(p[p[rrot].r].sum-p[p[lrot].r].sum>0) ans=max(ans,query(pos,mid+1,r,p[lrot].r,p[rrot].r));else if(p[p[rrot].l].sum-p[p[lrot].l].sum>0&&ans==0) ans=max(ans,query(pos,l,mid,p[lrot].l,p[rrot].l));return ans;}if(p[p[rrot].r].sum-p[p[lrot].r].sum>0) ans=max(ans,query(pos,mid+1,r,p[lrot].r,p[rrot].r));if(ans==0&&p[p[rrot].l].sum-p[p[lrot].l].sum>0) ans=max(ans,query(pos,l,mid,p[lrot].l,p[rrot].l));return ans;}else{int ans=0;if(p[p[rrot].l].sum-p[p[lrot].l].sum>0) ans=max(ans,query(pos,l,mid,p[lrot].l,p[rrot].l));return ans;} }int main() {int t;scanf("%d",&t);while(t--){tot=0;memset(cnt,0,sizeof(cnt));scanf("%d%d",&n,&k);for(int i=1;i<=n;i++) scanf("%d",&a[i]),vis[a[i]]=i;root[0]=build(1,n);for(int i=1;i<=n;i++) root[i]=update(root[i-1],a[i],1,n);cnt[1]=1;for(int i=2;i<=n;i++){int num1,num2,num;int pos1=max(vis[i]-k,1),pos2=max(vis[i]-1,1);int pos3=min(vis[i]+1,n),pos4=min(vis[i]+k,n);if(pos1!=pos2) num1=query(i,1,n,root[pos1-1],root[pos2]);else num1=a[pos1]<i?a[pos1]:0;if(pos3!=pos4) num2=query(i,1,n,root[pos3-1],root[pos4]);else num2=a[pos4]<i?a[pos4]:0;num=max(num1,num2);cnt[i]=cnt[num]+1;}for(int i=1;i<=n;i++) printf("%d%c",cnt[i],i==n?'\n':' ');}return 0; }

同樣類似的還有一段區間求大于k的最小的。。2019ccpc網絡預選賽
線段樹做法，各種優勢勝過主席樹

#include<bits/stdc++.h> #define ll long long using namespace std;const int maxx=1e5+100; struct node{int l;int r;int sum; }p[maxx<<2]; int a[maxx],vis[maxx],cnt[maxx]; int n,k;inline void pushup(int cur) {p[cur].sum=max(p[cur<<1].sum,p[cur<<1|1].sum); } inline void build(int l,int r,int cur) {p[cur].l=l;p[cur].r=r;p[cur].sum=0;if(l==r) return ;int mid=l+r>>1;build(l,mid,cur<<1);build(mid+1,r,cur<<1|1); } inline void update(int pos,int cur,int v) {int L=p[cur].l;int R=p[cur].r;if(L==R){p[cur].sum=v;return ;}int mid=L+R>>1;if(pos<=mid) update(pos,cur<<1,v);else update(pos,cur<<1|1,v);pushup(cur); } inline int query(int l,int r,int cur) {int L=p[cur].l;int R=p[cur].r;if(l<=L&&R<=r) return p[cur].sum;int mid=L+R>>1;if(r<=mid) return query(l,r,cur<<1);else if(l>mid) return query(l,r,cur<<1|1);else return max(query(l,mid,cur<<1),query(mid+1,r,cur<<1|1)); } int main() {int t;scanf("%d",&t);while(t--){memset(cnt,0,sizeof(cnt));scanf("%d%d",&n,&k);for(int i=1;i<=n;i++) scanf("%d",&a[i]),vis[a[i]]=i;build(1,n,1);update(vis[1],1,1);cnt[1]=1;for(int i=2;i<=n;i++){int num=query(max(vis[i]-k,1),min(vis[i]+k,n),1);cnt[i]=cnt[num]+1;update(vis[i],1,i);}for(int i=1;i<=n;i++) printf("%d%c",cnt[i],i==n?'\n':' ');} }

努力加油a啊，(^o)/~

總結

以上是生活随笔為你收集整理的Greedy Sequence（2019南京icpc网络预选赛）主席树求区间小于k的最大值的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。