[SDOI2011]拦截导弹

第一问：求一个需满足三个条件的最长不上升子序列的长度。

第二问：（求长度满足第一问的）每个点被包含的概率

解：

对每个点建len[2] fa[2]数组分别记录以该点开始/结束(后边会说)的LIS长度，fa表示这种len对应的方案数

第一问：dp方程 $ dp[i]=max(dp[j])+1 time_j<time_i ,h_j ge h_i ,v_j ge v_i $ 然后二维树状数组啊（空间不够）

三个条件->三维偏序->CDQ分治

定义h为第一维，time为第二维，v为第三维。

但是不同与以往的CDQ模板的套路。

由于我们要得到完整且正确的dp[i]，由方程知更新dp[i]时要用完整且正确的dp[j]，但不是一次就更新过来的（dp[i]多次被不同的dp[j]更新）。一句话就是转移要满足DAG的拓扑序。

为了保证完整且正确，我们采取以下CDQ顺序

递归解决左区间
用左区间更新右区间
递归解决右区间

就能保证在更新右区间时左区间的dp[j]完整且正确（子问题解决）了，同时不难发现dp[mid+1]一定是完整且正确的了，因为他的入边都被转移，已经没有j能作为左区间来更新它了。

首先sort保证第一维单调，开始CDQ。

然后递归解决左区间。

接下来转移跨mid的部分，分别对左右区间以time为关键字sort，保证time的分别有序（以前都是用归并来递归解决，于是同样能保证左右区间分别有序，但由于这题CDQ的递归顺序，无法完成归并），然后对于[mid+1,r]用单调指针类似归并扫描[l,mid]，用树状数组维护第三维。

题目求的是最长不上升，但由于树状数组的特性不好维护，所以把h v全部倒序，这样h time v的单调性就统一了，转化为求最长不下降子序列。

正着一遍CDQ得到的len最大值是第一问的解。

第二问：

统计的前提条件是len[0]+len[1]-1==第一问答案，-1是除去重复计算的自己。不满足条件的点直接输出0.0......。

$某点的概率=frac {经过该点的LIS方案数} {总LIS方案数}$

$经过该点的LIS方案数=fa[0]*fa[1]$

总方案数用上一行的统计方式会算重，所以直接累加起始/结束点即可。

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<algorithm>
  4 #define db double
  5 #define ll long long
  6 #define reg register
  7 #define F(i,a,b) for(register int (i)=(a);(i)<=(b);++(i))
  8 using namespace std;
  9 const int N=500100;
 10 inline int read();
 11 int mx,my;
 12 int n,T;
 13 int h_lsh[N],v_lsh[N],h_cnt,v_cnt;
 14 bool mark[N];
 15 struct BOOM{
 16     int tm,h,v;
 17     int len[2];
 18     db fa[2];
 19 }f[N];//,q[N];
 20 struct TR{
 21     int len;
 22     db fa;
 23     int _time;
 24     TR(){clear();}
 25     void clear(){len=0,fa=0.0,_time=0;}
 26 }t[N];
 27 inline bool cmp(BOOM a,BOOM b)
 28 {
 29     if(a.h!=b.h) return a.h<b.h;
 30     if(a.tm!=b.tm) return a.tm<b.tm;
 31     return a.v<b.v;
 32 }
 33 inline bool cmp1(BOOM a,BOOM b)
 34 {
 35     return a.tm<b.tm;
 36 }
 37 inline bool cmp2(BOOM a,BOOM b)
 38 {
 39     return a.tm>b.tm;
 40 }
 41 void add(int v,int len,db fa)
 42 {
 43     while(v<=v_cnt+23)
 44     {
 45         if(t[v]._time<T) t[v].clear(),t[v]._time=T;
 46         if(t[v].len==len) t[v].fa+=fa;
 47         else if(t[v].len<len)
 48         {
 49             t[v].len=len;
 50             t[v].fa=fa;
 51         }
 52         v+=(v&-v);
 53     }
 54 }
 55 void clear(int v)
 56 {
 57     while(v<=v_cnt+23)
 58     {
 59         t[v].clear();
 60         v+=(v&-v);
 61     }
 62 }
 63 TR ask(int v)
 64 {
 65     TR s;
 66     while(v)
 67     {
 68         if(t[v]._time<T) t[v].clear(),t[v]._time=T;
 69         if(s.len==t[v].len) s.fa+=t[v].fa;
 70         else if(s.len<t[v].len)
 71         {
 72             s.len=t[v].len;
 73             s.fa=t[v].fa;
 74         }
 75         v-=(v&-v);
 76     }
 77     return s;
 78 }
 79 void cdq(int l,int r,int o)
 80 {
 81 //    printf("L=%d R=%d
",l,r);
 82     if(l==r)
 83     {
 84     //    f[l].len[o]=f[l].fa[o]=1;
 85         return;
 86     }
 87     int mid=(l+r)>>1;
 88     cdq(l,mid,o);
 89     sort(f+l,f+mid+1,cmp1);
 90     sort(f+mid+1,f+r+1,cmp1);
 91     ++T;
 92     int p=l,pl=l,pr=mid+1;
 93     F(i,mid+1,r)
 94     {
 95         while(p<=mid&&f[p].tm<=f[i].tm)
 96         {
 97             add(f[p].v,f[p].len[o],f[p].fa[o]);
 98             ++p;
 99         }
100         TR s=ask(f[i].v);
101         ++s.len;
102         if(s.len>f[i].len[o])
103         {
104             f[i].len[o]=s.len;
105             f[i].fa[o]=s.fa;
106         }
107            else if(s.len==f[i].len[o])
108            {
109             f[i].fa[o]+=s.fa;
110         }
111     }
112     sort(f+l,f+r+1,cmp);
113     cdq(mid+1,r,o);
114 }
115 int main()
116 {
117 //    freopen("data.in","r",stdin);
118     n=read();
119     F(i,1,n)
120     {
121         f[i].h=h_lsh[i]=read();
122         f[i].v=v_lsh[i]=read();
123         f[i].len[0]=f[i].len[1]=f[i].fa[0]=f[i].fa[1]=1;
124         f[i].tm=i;
125     }
126     sort(h_lsh+1,h_lsh+n+1);
127     sort(v_lsh+1,v_lsh+n+1);
128     h_cnt=unique(h_lsh+1,h_lsh+n+1)-h_lsh-1;
129     v_cnt=unique(v_lsh+1,v_lsh+n+1)-v_lsh-1;
130     F(i,1,n)
131     {
132         f[i].h=h_cnt+1-(lower_bound(h_lsh+1,h_lsh+h_cnt+1,f[i].h)-h_lsh);
133         f[i].v=v_cnt+1-(lower_bound(v_lsh+1,v_lsh+v_cnt+1,f[i].v)-v_lsh);
134 //        printf("i=%d f[i].v=%d
",i,f[i].v);
135     }
136     sort(f+1,f+n+1,cmp);
137 //    F(i,1,n)
138  //   {
139 //         printf("i=%d f[i].h=%d f[i].tm=%d f[i].v=%d
",i,f[i].h,f[i].tm,f[i].v);
140 //    }
141     cdq(1,n,0);
142     F(i,1,n)
143     {
144         f[i].h=h_cnt-f[i].h+1;
145         f[i].v=v_cnt-f[i].v+1;
146         f[i].tm=n-f[i].tm+1;
147     }
148     sort(f+1,f+n+1,cmp);
149 //    reverse(f+1,f+n+1);
150     cdq(1,n,1);
151     int pt_len=0;
152     db tot=0.0;
153     sort(f+1,f+n+1,cmp2);
154     F(i,1,n)
155     {
156         pt_len=max(pt_len,f[i].len[0]);
157  //       printf("%d
",f[i].len[0]);
158     }
159     F(i,1,n) if(f[i].len[0]==pt_len) tot+=f[i].fa[0];
160     printf("%d
",pt_len);
161     F(i,1,n)
162     {
163 //        printf("i=%d 正：len=%d fa=%d 反：len=%d fa=%d bj=%d
",i,f[i].len[0],f[i].fa[0],f[i].len[1],f[i].fa[1],f[i].v);
164         if(f[i].len[0]+f[i].len[1]-1==pt_len) printf("%.5lf ",f[i].fa[0]*f[i].fa[1]/(double)tot);
165         else printf("%.5lf ",0.0);
166     }
167     return 0;
168 }
169 inline int read()
170 {
171     int x=0;
172     char tc=getchar();
173     while(tc<'0'||tc>'9') tc=getchar();
174     while(tc>='0'&&tc<='9') x=x*10+tc-48,tc=getchar();
175     return x;
176 }

View Code