cdq。。还真是。。

一开始自己写，设f[i]为以i结尾的最优方案，fn[i]为以i结尾的最优方案数，然后cdq完了第一问就出来了，还顺便把总最优方案数算了，

and then？ mengbier

然后各路%啊，一个下午+一晚上就交代了

怎么做呢？我们再cdq出另一个f和fn表示以i开头的最优方案和方案数

然后想一想i在这 l——————i——————r

然后 f[0][i]就是l~i的最优方案了，f[1][i]就是i~r的最优方案

那么两个一合并，再减去重复计算的i位置，假如等于最优方案，说明i出现了fn[0][i]*fn[1][i]（一一组合嘛）

完成。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;typedef long double LD;int n;int s[51000];LD g[51000];int lowbit(int x){ return x&-x;}void change(int x,int k,LD fan){ while(x<=50500) { if(s[x]
           
            =1) { if(s[x]>ret) { ret=s[x]; fan=g[x]; } else if(s[x]==ret)fan+=g[x]; x-=lowbit(x); } return ret;}struct node{ int x,y,z;}a[51000],b[51000];bool cmpx(node n1,node n2){ return n1.x
            
             n2.x;}bool cmpy(node n1,node n2){ return n1.y>n2.y;}bool cmpy2(node n1,node n2){ return n1.y
             
              =a[i].y)) change(a[tp].z,f[0][a[tp].x],fn[0][a[tp].x]), tp++; LD fan; int d=getmax(a[i].z,fan)+1; if(d>f[0][a[i].x]) { f[0][a[i].x]=d; fn[0][a[i].x]=fan; } else if(d==f[0][a[i].x])fn[0][a[i].x]+=fan; } for(int i=l;i<=mid;i++)clean(a[i].z); sort(a+mid+1,a+r+1,cmpx); cdq(mid+1,r); sort(a+l,a+r+1,cmpy);}void cdq2(int l,int r){ if(l==r)return ; int mid=(l+r)/2; cdq2(l,mid); sort(a+mid+1,a+r+1,cmpy2); int tp=l; for(int i=mid+1;i<=r;i++) { while(tp<=mid&&a[tp].y<=a[i].y) change(a[tp].z,f[1][a[tp].x],fn[1][a[tp].x]), tp++; LD fan; int d=getmax(a[i].z,fan)+1; if(d>f[1][a[i].x]) { f[1][a[i].x]=d; fn[1][a[i].x]=fan; } else if(d==f[1][a[i].x])fn[1][a[i].x]+=fan; } for(int i=l;i<=mid;i++)clean(a[i].z); sort(a+mid+1,a+r+1,cmpx2); cdq2(mid+1,r); sort(a+l,a+r+1,cmpy2);}LD cao[51000];int main(){ freopen("missile.in","r",stdin); freopen("missile.out","w",stdout); scanf("%d",&n); for(int i=1;i<=n;i++) a[i].x=i, scanf("%d%d",&a[i].y,&a[i].z); LSH(); for(int i=1;i<=n;i++)b[i]=a[i]; memset(f,0,sizeof(f)); for(int i=1;i<=n;i++)f[0][i]=1,fn[0][i]=1; cdq(1,n); int mmax=0;LD sum=0; for(int i=1;i<=n;i++) if(f[0][i]>mmax) { mmax=f[0][i]; sum=fn[0][i]; } else if(mmax==f[0][i])sum+=fn[0][i]; printf("%d\n",mmax); for(int i=1;i<=n;i++)a[i]=b[n-i+1]; for(int i=1;i<=n;i++)a[i].z=n-a[i].z+1; for(int i=1;i<=n;i++)f[1][i]=1,fn[1][i]=1; cdq2(1,n); for(int i=1;i<=n;i++) if(f[0][i]+f[1][i]-1==mmax) cao[i]=fn[0][i]*fn[1][i]; for(int i=1;i