BZOJ 2244 [SDOI2011]拦截导弹 (三维偏序CDQ+线段树)

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

题目大意：

洛谷传送门

不愧为SDOI的duliu题

第一问？二元组的最长不上升子序列长度？裸的三维偏序问题，直接上$CDQ$

由于是不上升，需要查询某一范围的最大值，并不是前缀最大值，建议用线段树实现

第二问是个什么玩意？？

画画图发现需要正反各做一次$CDQ$来统计

如果某个位置正反的答案$-1$就是最长长度

那么它被选择的次数就是正着统计作为末尾的次数*反着统计作为末尾的次数

概率就是这个值/总次数

又发现某个位置作为末尾的次数可能非常非常大！

比如$1\;1\;2\;2\;3\;3\;4\;4\;5\;5....$这个值甚至达到了$2^{n/2}$

而题目又是让我们求概率，所以这个次数必须要用$double$存

蒟蒻的代码写得比较恶心..

另外听一些神犇说$sort$中的$cmp$里不能写$<=$或$>=$，不然会$RE$

 #include <vector>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #define N1 50100

 #define ll long long

 #define dd double

 #define inf 0x3f3f3f3f3f3f3f3fll

 using namespace std;

 int gint()

 {

     int ret=,fh=;char c=getchar();

     while(c<''||c>''){if(c=='-')fh=-;c=getchar();}

     while(c>=''&&c<=''){ret=ret*+c-'';c=getchar();}

     return ret*fh;

 }

 int n,m,mh,mv,K;

 inline void chk(int &ma,dd &sum,int w,dd num)

 {

     if(w>ma) ma=w,sum=num;

     else if(w==ma) sum+=num;

 }

 struct SEG{

 int ma[N1<<]; dd sum[N1<<];

 void pushup(int rt)

 {

     ma[rt]=; sum[rt]=;

     chk(ma[rt],sum[rt],ma[rt<<],sum[rt<<]);

     chk(ma[rt],sum[rt],ma[rt<<|],sum[rt<<|]);

 }

 void update(int x,int l,int r,int rt,int w,dd num)

 {

     if(l==r) { chk(ma[rt],sum[rt],w,num); return; }

     int mid=(l+r)>>;

     if(x<=mid) update(x,l,mid,rt<<,w,num);

     else update(x,mid+,r,rt<<|,w,num);

     pushup(rt);

 }

 void query(int L,int R,int l,int r,int rt,int &w,dd &num)

 {

     if(L<=l&&r<=R) { chk(w,num,ma[rt],sum[rt]); return; }

     int mid=(l+r)>>;

     if(L<=mid) query(L,R,l,mid,rt<<,w,num);

     if(R>mid) query(L,R,mid+,r,rt<<|,w,num);

 }

 void clr(int x,int l,int r,int rt)

 {

     ma[rt]=; sum[rt]=;

     if(l==r) return; int mid=(l+r)>>;

     if(x<=mid) clr(x,l,mid,rt<<);

     else clr(x,mid+,r,rt<<|);

 }

 }s;

 struct node{int h,v,t,ans; dd sum;}a[N1],c[N1],tmp[N1];

 int h[N1],v[N1],que[N1],tl;

 int cmp1(node s1,node s2){ if(s1.h!=s2.h) return s1.h>s2.h; return s1.v>=s2.v; }

 int cmp2(node s1,node s2){ if(s1.h!=s2.h) return s1.h<s2.h; return s1.v<=s2.v; }

 int cmpp(node s1,node s2){ if(s1.h!=s2.h) return s1.h>s2.h; return s1.v>s2.v; }

 int cmpn(node s1,node s2){ if(s1.h!=s2.h) return s1.h<s2.h; return s1.v<s2.v; }

 void CDQ1(int L,int R)

 {

     if(R-L<=) return;

     int M=(L+R)>>,i,j,k,cnt;

     for(i=L,j=M,k=L;k<R;k++)

     {

         if(a[k].t<M) tmp[i++]=a[k];

         else tmp[j++]=a[k];

     }

     for(k=L;k<R;k++) a[k]=tmp[k];

     CDQ1(L,M);

     for(i=L,j=M;i<M&&j<R;)

     {

         if(cmp1(a[i],a[j])) { s.update(a[i].v,,mv,,a[i].ans+,a[i].sum); que[++tl]=i; i++; }

         else { s.query(a[j].v,mv,,mv,,a[j].ans,a[j].sum); j++; }

     }

     while(j<R) { s.query(a[j].v,mv,,mv,,a[j].ans,a[j].sum); j++;}

     while(tl) { s.clr(a[que[tl--]].v,,mv,); }

     CDQ1(M,R);

     for(i=L,j=M,cnt=;i<M&&j<R;)

     {

         if(cmp1(a[i],a[j])) { tmp[++cnt]=a[i]; i++; }

         else { tmp[++cnt]=a[j]; j++;}

     }

     while(i<M) tmp[++cnt]=a[i++];

     while(j<R) tmp[++cnt]=a[j++];

     for(k=L;k<R;k++) a[k]=tmp[k-L+];

 }

 void CDQ2(int L,int R)

 {

     if(R-L<=) return;

     int M=(L+R)>>,i,j,k,cnt;

     for(i=L,j=M,k=L;k<R;k++)

     {

         if(a[k].t<M) tmp[i++]=a[k];

         else tmp[j++]=a[k];

     }

     for(k=L;k<R;k++) a[k]=tmp[k];

     CDQ2(L,M);

     for(i=L,j=M;i<M&&j<R;)

     {

         if(cmp2(a[i],a[j])) { s.update(a[i].v,,mv,,a[i].ans+,a[i].sum); que[++tl]=i; i++; }

         else { s.query(,a[j].v,,mv,,a[j].ans,a[j].sum); j++; }

     }

     while(j<R) { s.query(,a[j].v,,mv,,a[j].ans,a[j].sum); j++;}

     while(tl) { s.clr(a[que[tl--]].v,,mv,); }

     CDQ2(M,R);

     for(i=L,j=M,cnt=;i<M&&j<R;)

     {

         if(cmp2(a[i],a[j])) { tmp[++cnt]=a[i]; i++; }

         else { tmp[++cnt]=a[j]; j++;}

     }

     while(i<M) tmp[++cnt]=a[i++];

     while(j<R) tmp[++cnt]=a[j++];

     for(k=L;k<R;k++) a[k]=tmp[k-L+];

 }

 dd ret[N1];

 int p[N1];

 int de;

 int main()

 {

     scanf("%d",&n);

     int i,j,x,y,ans=; dd sum=;

     for(i=;i<=n;i++) { h[i]=a[i].h=gint(); v[i]=a[i].v=gint(); a[i].t=i; a[i].ans=; a[i].sum=; }

     sort(h+,h+n+); mh=unique(h+,h+n+)-(h+); sort(v+,v+n+); mv=unique(v+,v+n+)-(v+);

     for(i=;i<=n;i++) { a[i].h=lower_bound(h+,h+mh+,a[i].h)-h; a[i].v=lower_bound(v+,v+mv+,a[i].v)-v;}

     sort(a+,a+n+,cmpp);

     CDQ1(,n+);

     for(i=;i<=n;i++) { c[i]=a[i]; p[a[i].t]=i; chk(ans,sum,a[i].ans,a[i].sum); }

     sort(a+,a+n+,cmpn); for(i=;i<=n;i++) { a[i].ans=; a[i].sum=; a[i].t=n-a[i].t+; }

     CDQ2(,n+);

     for(i=;i<=n;i++)

     {

         j=p[n-a[i].t+];

         if(a[i].ans+c[j].ans-<ans) ret[c[j].t]=;

         else ret[c[j].t]=1.0*c[j].sum*a[i].sum/sum;

     }

     printf("%d\n",ans);

     for(i=;i<=n;i++) printf("%.5lf ",ret[i]);

     puts(""); return ;

 }