C++14(g++5.4) 解法, 执行用时: 244ms, 内存消耗: 6624K, 提交时间: 2019-08-20 21:57:43

#include<bits/stdc++.h>

#define FOG(x,y,z) for(register int x=y,x##_=z;x<=x##_;++x)
#define DOG(x,y,z) for(register int x=y,x##_=z;x>=x##_;--x)
#define FOR(x,y,z) for(int x=y,x##_=z;x<=x##_;++x)
#define DOR(x,y,z) for(int x=y,x##_=z;x>=x##_;--x)
#define FOR_(x,y,z,s) for(int x=y,x##_=z;x<=x##_;x+=s)
#define FOR__(x,y,z) for(int x=y,x##_=z;x<=x##_;x<<=1)
#define EOR(x,y) for(int x##_=head[x],y=edge[x##_].e;x##_;y=edge[x##_=edge[x##_].to].e)
#define EGOR(x,y,z) for(int x##_=head[x],y=edge[x##_].e,z=edge[x##_].c;x##_;y=edge[x##_=edge[x##_].to].e,z=edge[x##_].c)
#define EOD(x,y,z) for(int &x##_=head[x],y=edge[x##_].e,z=edge[x##_].c;x##_;y=edge[x##_=edge[x##_].to].e,z=edge[x##_].c)
#define While(x) for(;x;)
#define clr(x,y) memset(x,y,sizeof(x))
#define szf(x) sizeof(x)
#define min3(x,y,z) min(min(x,y),z)
#define max3(x,y,z) max(max(x,y),z)

#define read2(x,y) read(x),read(y)
#define read3(x,y,z) read(x),read(y),read(z)
#define read4(x,y,z,w) read3(x,y,z),read(w)
#define reads(str) sf("%s",str)

#define ts (*this)
#define sf scanf
#define pf printf

#define ll long long
#define ull unsigned long long
#define db long double
#define ct clock_t
#define ck() clock()
#define rd rand()
#define rmx RAND_MAX
#define RD T*(rd*2-rmx)


using namespace std;

template<class T>bool tomin(T &x,T y){return y<x?x=y,1:0;}
template<class T>bool tomax(T &x,T y){return x<y?x=y,1:0;}
template<class T>void read(T &x){
	char c;
	x=0;
	int f=1;
	while(c=getchar(),c<'0'||c>'9')if(c=='-')f=-1;
	do x=(x<<3)+(x<<1)+(c^48);
	while(c=getchar(),c>='0'&&c<='9');
	x*=f;
}

const db Pi=acos(-1);
const int maxn=5e4+5;
int n;
int Y[maxn],sy;
struct node{
	int x,y,id;
	void Rd(int i){
		id=i;
		read2(x,y);
		Y[++sy]=y;
	}
}A[maxn];
struct Node{
	int v;
	db c;
	void operator +=(const Node &A){
		if(v<A.v)v=A.v,c=A.c;
		else if(v==A.v)c+=A.c;
	}
}Zero,ans;
namespace P1{
	Node dp[maxn];
	node B[maxn];
	Node c[maxn];
	void Add(int x,Node y){
		while(x){
			c[x]+=y;
			x&=x-1;
		}
	}
	void Init(int x){
		while(x){
			c[x]=Zero;
			x&=x-1;
		}
	}
	Node query(int x){
		Node res=Zero;
		while(x<=sy){
			res+=c[x];
			x+=x&-x;
		}return res;
	}
	bool cmp(node A,node B){
		return A.x==B.x?(A.y==B.y?A.id<B.id:A.y>B.y):A.x>B.x;
	}
	void CDQ(int L,int R){
		if(L==R){
			if(dp[L].v==0)dp[L]=Zero;
			++dp[L].v;
			ans+=dp[L];
			return;
		}
		int mid=L+R>>1;
		CDQ(L,mid);
		FOR(i,L,R)B[i]=A[i];
		sort(B+L,B+R+1,cmp);
		FOR(i,L,R){
			if(B[i].id<=mid)Add(B[i].y,dp[B[i].id]);
			else dp[B[i].id]+=query(B[i].y);
		}
		FOR(i,L,R)if(B[i].id<=mid)Init(B[i].y);
		CDQ(mid+1,R);
	}
	void solve(){
		FOR(i,1,n)dp[i]=Zero;
		CDQ(1,n);
	}
}
namespace P2{
	Node dp[maxn];
	Node c[maxn];
	node B[maxn];
	void Add(int x,Node y){
		while(x<=sy){
			c[x]+=y;
			x+=x&-x;
		}
	}
	void Init(int x){
		while(x<=sy){
			c[x]=Zero;
			x+=x&-x;
		}
	}
	Node query(int x){
		Node res=Zero;
		while(x){
			res+=c[x];
			x&=x-1;
		}return res;
	}
	bool cmp(node A,node B){
		return A.x==B.x?(A.y==B.y?A.id>B.id:A.y<B.y):A.x<B.x;
	}
	void CDQ(int L,int R){
		if(L==R){
			if(dp[L].v==0)dp[L]=Zero;
			++dp[L].v;
			return;
		}
		int mid=L+R>>1;
		CDQ(mid+1,R);
		FOR(i,L,R)B[i]=A[i];
		sort(B+L,B+R+1,cmp);
		FOR(i,L,R){
			if(B[i].id>mid)Add(B[i].y,dp[B[i].id]);
			else dp[B[i].id]+=query(B[i].y);
		}
		FOR(i,L,R)if(B[i].id>mid)Init(B[i].y);
		CDQ(L,mid);
	}
	void solve(){
		FOR(i,1,n)dp[i]=Zero;
		CDQ(1,n);
	}
}
namespace P3{
	void solve(){
		pf("%d\n",ans.v);
		FOR(i,1,n){
			if(P1::dp[i].v+P2::dp[i].v-1==ans.v)pf("%.5Lf",(db)P1::dp[i].c*P2::dp[i].c/ans.c);
			else pf("%.5Lf",(db)0);
			putchar(i==n?'\n':' ');
		}
	}
}
int main(){
	Zero=(Node){0,(db)1};
	srand(time(NULL));
	read(n);
	FOR(i,1,n)A[i].Rd(i);
	sort(Y+1,Y+sy+1);
	sy=unique(Y+1,Y+sy+1)-Y-1;
	FOR(i,1,n)A[i].y=lower_bound(Y+1,Y+sy+1,A[i].y)-Y;
	P1::solve();
	P2::solve();
	P3::solve();
	return 0;
}

C++(g++ 7.5.0) 解法, 执行用时: 438ms, 内存消耗: 3924K, 提交时间: 2022-09-29 23:41:51

#include <algorithm>
#include <cstdio>

using namespace std;

typedef double db;

const int N = 1e6 + 10;

struct node {
  int h;
  int v;
  int p;
  int ma;
  db ca;
} a[2][N];

int n;
bool tr;

inline bool cmp1(const node a, const node b) {
  if (tr)
    return a.h > b.h;
  else
    return a.h < b.h;
}

inline bool cmp2(const node a, const node b) {
  if (tr)
    return a.v > b.v;
  else
    return a.v < b.v;
}

inline bool cmp3(const node a, const node b) {
  if (tr)
    return a.p < b.p;
  else
    return a.p > b.p;
}

inline bool cmp4(const node a, const node b) { return a.v == b.v; }

struct treearray {
  int ma[2 * N];
  db ca[2 * N];

  inline void c(int x, int t, db c) {
    for (; x <= n; x += x & (-x)) {
      if (ma[x] == t) {
        ca[x] += c;
      } else if (ma[x] < t) {
        ca[x] = c;
        ma[x] = t;
      }
    }
  }

  inline void d(int x) {
    for (; x <= n; x += x & (-x)) {
      ma[x] = 0;
      ca[x] = 0;
    }
  }

  inline void q(int x, int& m, db& c) {
    for (; x > 0; x -= x & (-x)) {
      if (ma[x] == m) {
        c += ca[x];
      } else if (m < ma[x]) {
        c = ca[x];
        m = ma[x];
      }
    }
  }
} ta;

int rk[2][N];

inline void solve(int l, int r, int t) {
  if (r - l == 1) {
    return;
  }
  int mid = (l + r) / 2;
  solve(l, mid, t);
  sort(a[t] + mid + 1, a[t] + r + 1, cmp1);
  int p = l + 1;
  for (int i = mid + 1; i <= r; i++) {
    for (; (cmp1(a[t][p], a[t][i]) || a[t][p].h == a[t][i].h) && p <= mid;
         p++) {
      ta.c(a[t][p].v, a[t][p].ma, a[t][p].ca);
    }
    db c = 0;
    int m = 0;
    ta.q(a[t][i].v, m, c);
    if (a[t][i].ma < m + 1) {
      a[t][i].ma = m + 1;
      a[t][i].ca = c;
    } else if (a[t][i].ma == m + 1) {
      a[t][i].ca += c;
    }
  }
  for (int i = l + 1; i <= mid; i++) {
    ta.d(a[t][i].v);
  }
  sort(a[t] + mid, a[t] + r + 1, cmp3);
  solve(mid, r, t);
  sort(a[t] + l + 1, a[t] + r + 1, cmp1);
}

inline void ih(int t) {
  sort(a[t] + 1, a[t] + n + 1, cmp2);
  rk[t][1] = 1;
  for (int i = 2; i <= n; i++) {
    rk[t][i] = (cmp4(a[t][i], a[t][i - 1])) ? rk[t][i - 1] : i;
  }
  for (int i = 1; i <= n; i++) {
    a[t][i].v = rk[t][i];
  }
  sort(a[t] + 1, a[t] + n + 1, cmp3);
  for (int i = 1; i <= n; i++) {
    a[t][i].ma = 1;
    a[t][i].ca = 1;
  }
}

int len;
db ans;

int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d%d", &a[0][i].h, &a[0][i].v);
    a[0][i].p = i;
    a[1][i].h = a[0][i].h;
    a[1][i].v = a[0][i].v;
    a[1][i].p = i;
  }
  ih(0);
  solve(0, n, 0);
  tr = 1;
  ih(1);
  solve(0, n, 1);
  tr = 1;
  sort(a[0] + 1, a[0] + n + 1, cmp3);
  sort(a[1] + 1, a[1] + n + 1, cmp3);
  for (int i = 1; i <= n; i++) {
    len = max(len, a[0][i].ma);
  }
  printf("%d\n", len);
  for (int i = 1; i <= n; i++) {
    if (a[0][i].ma == len) {
      ans += a[0][i].ca;
    }
  }
  for (int i = 1; i <= n; i++) {
    if (a[0][i].ma + a[1][i].ma - 1 == len) {
      printf("%.5lf ", (a[0][i].ca * a[1][i].ca) / ans);
    } else {
      printf("0.00000 ");
    }
  }
  return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 368ms, 内存消耗: 3824K, 提交时间: 2020-10-20 09:18:02

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define int long long
using namespace std;

const int N=5e4+5;

int n;

struct pp
{
	int h,v;
	int f[2],pos;
	double w[2];
}a[N];

int c[N],b[N];
double sum[N];

int tot;

int read()
{
	int res,f=1;
	char ch;
	while((ch=getchar())<'0'||ch>'9') if(ch=='-') f=-1;
	res=ch-'0';
	while((ch=getchar())>='0'&&ch<='9') res=(res<<1)+(res<<3)+ch-'0';
	return f*res;
}

void init()
{
	sort(b+1,b+1+n);
	tot=unique(b+1,b+1+n)-b-1;
	for(int i=1;i<=n;i++) a[i].v=lower_bound(b+1,b+1+tot,a[i].v)-b;
}

int cnt[N];

bool cmp(pp x,pp y) {return x.h>y.h;}
bool cmp2(pp x,pp y) {return x.pos<y.pos;}
bool cmp3(pp x,pp y) {return x.pos>y.pos;}

void update(int x,int l,double v)
{
	while(x)
	{
		if(c[x]<l) c[x]=l,sum[x]=v;
		else if(c[x]==l) sum[x]+=v;
		x-=x&(-x);
	}
	return;
}

int getsum(int x,double &cn)
{
	int res=0;
	while(x<=tot+1)
	{
		if(c[x]>res) res=c[x],cn=sum[x];
		else if(c[x]==res) cn+=sum[x];
		x+=x&(-x);
	}
	return res;
}

void clear(int x)
{
	while(x)
	{
		c[x]=0,sum[x]=0;
		x-=(-x)&x;
	}
	return ;
}

void solve1(int l,int r,int k)
{
	if(l==r) return ;
	int mid=(l+r)>>1;
	solve1(l,mid,k);
	sort(a+mid+1,a+r+1,cmp);
	int i=l,j=mid+1;
	while(j<=r)
	{
		while(i<=mid&&a[i].h>=a[j].h)
		{
			update(a[i].v,a[i].f[k],a[i].w[k]);
			i++;
		}
		int t=0;
		double way=0;
		t=getsum(a[j].v,way);
		if(t+1>a[j].f[k])
		{
			a[j].f[k]=t+1;
			a[j].w[k]=way;
		}
		else if(t+1==a[j].f[k]) a[j].w[k]+=way;
		j++;
	}
	i=l,j=mid+1;
	while(j<=r)
	{
		while(i<=mid&&a[i].h>=a[j].h)
		{
			clear(a[i].v);
			i++;
		}
		j++;
	}
	sort(a+mid+1,a+r+1,cmp2);
	solve1(mid+1,r,k);
	sort(a+l,a+r+1,cmp);
}

signed main()
{
#ifndef ONLINE_JUDGE
	freopen("17.in","r",stdin);
	freopen("ddlj.out","w",stdout);
#endif
	n=read();
	int max_h=0;
	for(int i=1;i<=n;i++)
	{
		a[i].h=read(),a[i].v=read();	
		b[i]=a[i].v;
		a[i].pos=i;
		max_h=max(max_h,a[i].h);
	}
	for(int i=1;i<=n;i++) a[i].f[1]=a[i].f[0]=1,a[i].w[1]=a[i].w[0]=1;
	init();
	solve1(1,n,0);
	for(int i=1;i<=n;i++) a[i].pos=n-a[i].pos+1,a[i].h=max_h+1-a[i].h,a[i].v=tot+1-a[i].v;
	sort(a+1,a+1+n,cmp2);
	solve1(1,n,1);
	int ans=0;
	double s=0;
	sort(a+1,a+1+n,cmp3);
	for(int i=1;i<=n;i++) ans=max(ans,a[i].f[0]);
	printf("%lld\n",ans);
	for(int i=1;i<=n;i++) if(a[i].f[0]==ans) s+=a[i].w[0];
	for(int i=1;i<=n;i++)
	{
		if(a[i].f[1]+a[i].f[0]-1==ans) printf("%.5lf ",a[i].w[1]*a[i].w[0]/s);
		else printf("%.5lf ",0.0);
	}
	return 0;
}