bzoj 2244[SDOI 2011]迎撃ミサイル(DP+CDQ分割+BIT)
21970 ワード
【テーマリンク】
http://www.lydsy.com/JudgeOnline/problem.php?id=2244
【題意】
n個の二元組を与えて、最長でサブシーケンスと各ミサイルがブロックされる確率を求めます.
【考え方】
DP+CDQ分割+BIT
まずシーケンスを反転して、lisを求めるのは便利です.
第一の質問に対して、私達が要求しているのは
f[i]=max｛f[j]｝、j＜i、x[j]＜x[i]、y[j]＜y[i]
満足すべき条件は三次元偏順であり,CDQで分割して解くことができることが分かった.
第二の問題を発見するのは簡単ではないです.一つのミサイルがあるlisの数/全部のlisの数です.つのミサイルのありかのlisは自分を含まなければならなくて、だから私達はg[i]を設定してiを最後のlisの総数にして、移動式があります:
g[i]=sigma{g[j]、j
似ているものはg’f’を求めることができます.全部g fの逆の定義です.つまりiで始まる…
奇術淫巧:反転してシーケンスに反対を取ってもいいです.このように関数を使って辛くてもいいです.離散化してから速く走って、一気にrk 3に上がります.
【コード】
1 #include<cstdio>
2 #include<cstring>
3 #include<iostream>
4 #include<algorithm>
5 #define FOR(a,b,c) for(int a=b;a<=c;a++)
6 using namespace std;
7
8 const int N = 1e5+10;
9
10 struct Node {
11 int id,x,y;
12 bool operator<(const Node& rhs)const {
13 return x<rhs.x||(x==rhs.x&&y<rhs.y);
14 }
15 }q[N],t[N];
16 bool cmp(const Node& a,const Node& b)
17 {
18 return a.id<b.id;
19 }
20
21 int f[2][N]; double g[2][N],ans[N];
22 int hash[N],tot,n;
23
24
25 int read()
26 {
27 char c=getchar(); int x=0; int f=1;
28 while(!isdigit(c)){if(c=='-')f=-1; c=getchar();}
29 while(isdigit(c)) x=x*10+c-'0',c=getchar();
30 return x*f;
31 }
32
33 int t_f[N],tag[N],T; double t_g[N];
34 void add(int x,int f,double g)
35 {
36 for(;x<=tot;x+=x&-x) {
37 if(tag[x]!=T) {tag[x]=T;t_f[x]=0;t_g[x]=0;}
38 if(f>t_f[x]){t_f[x]=f;t_g[x]=g;}
39 else if(f==t_f[x]) t_g[x]+=g;
40 }
41 }
42 void query(int x,int& mx,double& sum)
43 {
44 mx=0; sum=0.0;
45 for(;x;x-=x&-x) if(tag[x]==T){
46 if(t_f[x]>mx) {
47 mx=t_f[x]; sum=t_g[x];
48 } else if(t_f[x]==mx)
49 sum+=t_g[x];
50 }
51 }
52
53 void solve(int l,int r,int ty)
54 {
55 if(l==r) {
56 if(!f[ty][l]){
57 f[ty][l]=1; g[ty][l]=1;
58 }
59 return ;
60 }
61 int mid=(l+r)>>1;
62 int l1=l,l2=mid+1,i,j,cnt=0;
63 for(i=l;i<=r;i++) {
64 if(q[i].id<=mid) t[l1++]=q[i];
65 else t[l2++]=q[i];
66 }
67 memcpy(q+l,t+l,sizeof(Node)*(r-l+1));
68 solve(l,mid,ty);
69 T++;
70 sort(q+mid+1,q+r+1);
71 for(i=mid+1,j=l;i<=r;i++)
72 {
73 int id;
74 for(;j<=mid&&q[j].x<=q[i].x;j++) {
75 id=q[j].id; cnt++;
76 add(q[j].y,f[ty][id],g[ty][id]);
77 }
78 int mx; double sum;
79 query(q[i].y,mx,sum);
80 id=q[i].id;
81 if(mx>0) {
82 if(mx+1>f[ty][id]) {
83 f[ty][id]=mx+1; g[ty][id]=sum;
84 } else if(mx+1==f[ty][id]) {
85 g[ty][id]+=sum;
86 }
87 }
88 }
89 solve(mid+1,r,ty);
90 l1=l,l2=mid+1; int now=l;
91 while(l1<=mid||l2<=r) {
92 if(l2>r||l1<=mid&&q[l1]<q[l2]) t[now++]=q[l1++];
93 else t[now++]=q[l2++];
94 }
95 memcpy(q+l,t+l,sizeof(Node)*(r-l+1));
96 }
97
98 int main()
99 {
100 //freopen("in.in","r",stdin);
101 //freopen("out.out","w",stdout);
102 n=read();
103 int mxx=0;
104 FOR(i,1,n)
105 {
106 q[i].x=read(),q[i].y=read();
107 hash[i]=q[i].y;
108 mxx=max(mxx,q[i].x);
109 }
110 sort(hash+1,hash+n+1);
111 tot=unique(hash+1,hash+n+1)-hash-1;
112 FOR(i,1,n)
113 q[i].y=lower_bound(hash+1,hash+tot+1,q[i].y)-hash;
114 reverse(q+1,q+n+1);
115 FOR(i,1,n) q[i].id=i;
116 solve(1,n,0);
117
118 sort(q+1,q+n+1,cmp);
119 reverse(q+1,q+n+1);
120 FOR(i,1,n)
121 q[i].x=mxx-q[i].x+1,q[i].y=tot-q[i].y+1,
122 q[i].id=i;
123 solve(1,n,1);
124 int mx=0; double sum=0;
125 FOR(i,1,n) {
126 int tmp=f[0][i];
127 if(tmp>mx) {
128 mx=tmp; sum=g[0][i]*g[1][n-i+1];
129 } else if(tmp==mx)
130 sum+=g[0][i]*g[1][n-i+1];
131 }
132 printf("%d
",mx);
133 for(int i=n;i;i--) {
134 if(f[0][i]+f[1][n-i+1]-1==mx) {
135 ans[i]=(g[0][i]*g[1][n-i+1])/sum;
136 } else ans[i]=0;
137 }
138 for(int i=n;i>1;i--) printf("%.5lf ",ans[i]);
139 printf("%.5lf",ans[1]);
140 return 0;
141 }