subseq 牛客网多校

本文主要是介绍subseq 牛客网多校，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

https://www.nowcoder.com/acm/contest/143/H

首先数据有毒 不止1e5

题目要求下标字典序第k小的LIS 既然是以下标决定字典序 那就维护一个dp[i]代表以a[i]为首项的所有LIS个数 这个可以提前线段树之类的搞出来

为求第k小 故i从最小的下标1开始遍历 如果dp[i]<k 说明当前这个下标太小了不合要求 k减去dp[i] 如果以a[i]为首的LIS数量 否则说明字典序第k小的LIS就是以a[i]开头的 然后k-- 这个自减是为了减去只有a[i]自己的LIS 因为它肯定是最小的 要是自减以后k=0 那代表正好凑够 退出循环即可 否则就找除了独一个a[i]的第(k-1)小以a[i]开头的LIS 个人认为这个k--有些不太好理解(拙)

至于dp[i]爆longlong的情况 取个1e18即可 因为题目要求的k不超1e18 多了也用不上

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=1e18;struct node
{int l;int r;ll val;
};node tree[4000010];
ll dp[1000010];
ll k;
int a[1000010],tmp[1000010],ans[1000010];
int n,len;void pushup(int cur)
{tree[cur].val=min(N,tree[2*cur].val+tree[2*cur+1].val);
}void build(int l,int r,int cur)
{int m;tree[cur].l=l;tree[cur].r=r;tree[cur].val=0;if(l==r) return;m=(l+r)/2;build(l,m,2*cur);build(m+1,r,2*cur+1);
}ll query(int pl,int pr,int cur)
{ll res;if(pl<=tree[cur].l&&tree[cur].r<=pr){return tree[cur].val;}res=0;if(pl<=tree[2*cur].r) res=min(N,res+query(pl,pr,2*cur));if(pr>=tree[2*cur+1].l) res=min(N,res+query(pl,pr,2*cur+1));return res;
}void update(int tar,ll val,int cur)
{if(tree[cur].l==tree[cur].r){tree[cur].val=min(N,tree[cur].val+val);return;}if(tar<=tree[2*cur].r) update(tar,val,2*cur);else update(tar,val,2*cur+1);pushup(cur);
}int main()
{int i,p;scanf("%d%lld",&n,&k);for(i=1;i<=n;i++){scanf("%d",&a[i]);tmp[i]=a[i];}sort(tmp+1,tmp+n+1);len=unique(tmp+1,tmp+n+1)-tmp-1;build(1,len,1);for(i=n;i>=1;i--){p=lower_bound(tmp+1,tmp+len+1,a[i])-tmp;if(p+1<=len) dp[i]=query(p+1,len,1);dp[i]++;update(p,dp[i],1);}p=0;for(i=1;i<=n;i++){if(p==0||(p>0&&a[i]>a[ans[p]])){if(k>dp[i]) k-=dp[i];else{k--;ans[++p]=i;}if(k==0) break;}}if(p==0||k!=0) printf("-1\n");else{printf("%d\n",p);for(i=1;i<=p;i++){printf("%d",ans[i]);if(i<p) printf(" ");else printf("\n");}}return 0;
}

 

这篇关于subseq 牛客网多校的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---