首页 > 代码库 > BZOJ 2244: [SDOI2011]拦截导弹 [CDQ分治 树状数组]
BZOJ 2244: [SDOI2011]拦截导弹 [CDQ分治 树状数组]
传送门
题意：三维最长不上升子序列以及每个元素出现在最长不上升子序列的概率
$1A$了好开心
首先需要从左右各求一遍，长度就是$F[0][i]+F[1][i]-1$，次数就是$G[0][i]*G[1][i]$
我们可以用一些转换来简化代码
反转之后变成$LIS$，然后再反转并且$x,y$取反还是$LIS$，写一遍就可以啦
然后本题的树状数组需要维护最大值以及最大值的数量，还有一个时间戳
#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>using namespace std;typedef long long ll;const int N=5e4+5,INF=1e9;inline int read(){ char c=getchar();int x=0,f=1; while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1;c=getchar();} while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘;c=getchar();} return x*f;}int n,m;int mp[N];void iniMP(){ sort(mp+1,mp+1+m); int p=0; mp[++p]=mp[1]; for(int i=2;i<=m;i++) if(mp[i]!=mp[i-1]) mp[++p]=mp[i]; m=p;}int Bin(int v){ int l=1,r=m; while(l<=r){ int mid=(l+r)>>1; if(v==mp[mid]) return mid; else if(v<mp[mid]) r=mid-1; else l=mid+1; } return 0;}int c[N],mark[N],CL;double cnt[N];inline int lowbit(int x){return x&-x;}inline void upd(int p,int f,double g){ for(;p<=m;p+=lowbit(p)){ if(mark[p]!=CL) mark[p]=CL,c[p]=f,cnt[p]=g; else if(c[p]<f) c[p]=f,cnt[p]=g; else if(c[p]==f) cnt[p]+=g; }}inline void que(int p,int &f,double &g){ for(;p;p-=lowbit(p)) if(mark[p]==CL){ if(c[p]>f) f=c[p],g=cnt[p]; else if(c[p]==f) g+=cnt[p]; }}struct Data{ int x,y,id;}a[N];int ref[N];inline bool cmpX(int p,int q){ return a[p].x==a[q].x ? a[p].id<a[q].id : a[p].x<a[q].x;}int F[2][N];double G[2][N];void CDQ(int l,int r,int tp){ if(l==r) return; int mid=(l+r)>>1; CDQ(l,mid,tp); for(int i=l;i<=r;i++) ref[i]=i; sort(ref+l,ref+r+1,cmpX); int *f=F[tp]; double *g=G[tp]; CL++; for(int i=l;i<=r;i++){ int _=i;i=ref[i]; if(a[i].id<=mid) upd(a[i].y,f[a[i].id],g[a[i].id]); else{ int v=0;double sum=0;que(a[i].y,v,sum); v++; if(v>f[a[i].id]) f[a[i].id]=v,g[a[i].id]=sum; else if(v==f[a[i].id]) g[a[i].id]+=sum; } i=_; } CDQ(mid+1,r,tp);}int main(){ freopen("in","r",stdin); n=read(); for(int i=1;i<=n;i++) a[i].x=read(),mp[++m]=a[i].y=read(); iniMP(); for(int i=1;i<=n;i++) a[i].y=Bin(a[i].y); for(int i=1;i<=n;i++) F[0][i]=F[1][i]=G[0][i]=G[1][i]=1; reverse(a+1,a+1+n); for(int i=1;i<=n;i++) a[i].id=i; CDQ(1,n,0); //for(int i=1;i<=n;i++) printf("F0 %d %d %d %d %lf\n",i,a[i].x,a[i].y,F[0][i],G[0][i]);//puts("---"); reverse(a+1,a+1+n); for(int i=1;i<=n;i++) a[i].y=m-a[i].y+1,a[i].x=INF-a[i].x,a[i].id=i; CDQ(1,n,1); //for(int i=1;i<=n;i++) printf("F1 %d %d %d %d %lf\n",i,a[i].x,a[i].y,F[1][i],G[1][i]); for(int i=1;i<=n/2;i++) swap(F[0][i],F[0][n-i+1]),swap(G[0][i],G[0][n-i+1]); int ans=0;double tot=0; for(int i=1;i<=n;i++) ans=max(ans,F[0][i]); for(int i=1;i<=n;i++) if(F[0][i]==ans) tot+=G[0][i];//printf("tot %lf\n",tot); printf("%d\n",ans); for(int i=1;i<=n;i++){ if(F[0][i]+F[1][i]-1!=ans) printf("%.5lf ",0.0); else printf("%.5lf ",G[0][i]*G[1][i]/tot); }}
BZOJ 2244: [SDOI2011]拦截导弹 [CDQ分治 树状数组]
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。