bzoj 2244

没有正确分析路径可能的条数，它是指数增长的，会爆long long。
然后就是正反两次时间分治。
另一个就是max with count，即带计数的最值，即除了记录最值，还要记录最值取得的次数。
  1 /**************************************************************
  2     Problem: 2244
  3     User: idy002
  4     Language: C++
  5     Result: Accepted
  6     Time:4108 ms
  7     Memory:4520 kb
  8 ****************************************************************/
  9  
 10 #include <cstdio>
 11 #include <algorithm>
 12 #define oo 0x3f3f3f3f
 13 #define N 50010
 14 using namespace std;
 15  
 16 typedef bool (*Cmp)( int a, int b );
 17  
 18 struct Point {
 19     int x, y;
 20     Point(){}
 21     Point( int x, int y ):x(x),y(y){}
 22 };
 23 struct Info {
 24     int v; 
 25     long double c;
 26     Info(){}
 27     Info( int v, long double c ):v(v),c(c){}
 28     void add( Info o ) {
 29         if( o.v>v ) 
 30             *this = o;
 31         else if( o.v==v )
 32             c += o.c;
 33     }
 34 };
 35  
 36 int n;
 37 Point pts[N];
 38 Info dp[2][N];
 39 Info bit[N];
 40 int q[N];
 41 Cmp cmp;
 42 int disc[N], dtot;
 43 long double ans[N];
 44  
 45 bool cmpa( int a, int b ) {
 46     if( pts[a].x!=pts[b].x ) return pts[a].x<pts[b].x;
 47     if( pts[a].y!=pts[b].y ) return pts[a].y<pts[b].y;
 48     return a<b;
 49 }
 50 bool cmpb( int a, int b ) {
 51     if( pts[a].x!=pts[b].x ) return pts[a].x>pts[b].x;
 52     if( pts[a].y!=pts[b].y ) return pts[a].y>pts[b].y;
 53     return a<b;
 54 }
 55 void modify( int pos, Info o ) {
 56     if( cmp==cmpb ) pos = dtot+1-pos;
 57     for( int i=pos; i<=dtot; i+=i&-i )
 58         bit[i].add(o);
 59 }
 60 void clear( int pos ) {
 61     if( cmp==cmpb ) pos = dtot+1-pos;
 62     for( int i=pos; i<=dtot; i+=i&-i )
 63         bit[i] = Info(-oo,0);
 64 }
 65 Info query( int pos ) {
 66     if( cmp==cmpb ) pos = dtot+1-pos;
 67     Info o(-oo,0);
 68     for( int i=pos; i; i-=i&-i )
 69         o.add(bit[i]);
 70     return o;
 71 }
 72 void cdq( Info dp[], int lf, int rg ) {
 73     if( lf==rg ) {
 74         dp[lf].add( Info(1,1) );
 75         return;
 76     }
 77     int mid=(lf+rg)>>1;
 78     cdq( dp, lf, mid );
 79     for( int i=lf; i<=rg; i++ ) 
 80         q[i] = i;
 81     sort( q+lf, q+rg+1, cmp );
 82     for( int t=lf; t<=rg; t++ ) {
 83         int i=q[t];
 84         if( i<=mid ) {
 85             modify( pts[i].y, dp[i] );
 86         } else {
 87             Info o = query(pts[i].y);
 88             o.v++;
 89             dp[i].add( o );
 90         }
 91     }
 92     for( int t=lf; t<=rg; t++ ) {
 93         int i=q[t];
 94         if( i<=mid )
 95             clear( pts[i].y );
 96     }
 97     cdq( dp, mid+1, rg );
 98 }
 99 int main() {
100     scanf( "%d", &n );
101     for( int i=1,x,y; i<=n; i++ ) {
102         scanf( "%d%d", &x, &y );
103         pts[i] = Point(x,y);
104         disc[++dtot] = y;
105     }
106     reverse( pts+1, pts+1+n );
107     sort( disc+1, disc+1+dtot );
108     dtot = unique( disc+1, disc+1+dtot ) - disc - 1;
109     for( int i=1; i<=n; i++ ) 
110         pts[i].y = lower_bound( disc+1, disc+1+dtot, pts[i].y ) - disc;
111  
112     cmp = cmpa;
113     cdq( dp[0], 1, n );
114     cmp = cmpb;
115     reverse( pts+1, pts+1+n );
116     cdq( dp[1], 1, n );
117     reverse( dp[1]+1, dp[1]+1+n );
118      
119     Info info(-oo,0);
120     for( int i=1; i<=n; i++ ) 
121         info.add( dp[0][i] );
122     printf( "%d
", info.v );
123     for( int i=1; i<=n; i++ ) {
124         if( dp[0][i].v+dp[1][i].v-1 == info.v ) {
125             ans[i] = dp[0][i].c*dp[1][i].c/info.c; 
126         } else
127             ans[i] = 0.0;
128     }
129     reverse( ans+1, ans+1+n );
130     for( int i=1; i<=n; i++ )
131         printf( "%.5Lf
", ans[i] );
132 }
View Code