P2487 [SDOI2011] 拦截导弹

Sol

两个限制的导弹拦截。

设 \(f_i\) 表示以 \(i\) 结尾的最长 LIS 显然可以得到暴力转移方程 \(f_i=\displaystyle\max_{j=1,a_j\ge a_i,b_j \ge b_i}^{i-1}f_j+1\)，考虑到是三维偏序，所以用 CDQ 分治优化即可。

离散化不要忘记排序！

Code

#include <iostream>
#include <iomanip>
#include <cstdio>
#include <vector>
#include <stack>
#include <queue>
#include <bitset>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <cstring>
#include <sstream>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cassert>
#include <chrono>
#include <random>
#define x first
#define y second
#define pb push_back
#define eb emplace_back
#define pf push_front
#define desktop "C:\\Users\\MPC\\Desktop\\"
#define IOS ios :: sync_with_stdio (false),cin.tie (0),cout.tie (0)
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair <int,int> PII;
const int dx[] = {1,0,-1,0},dy[] = {0,-1,0,1};
template <typename T1,typename T2> bool tomax (T1 &x,T2 y) {
    if (y > x) return x = y,true;
    return false;
}
template <typename T1,typename T2> bool tomin (T1 &x,T2 y) {
    if (y < x) return x = y,true;
    return false;
}
LL power (LL a,LL b,LL p) {
    LL ans = 1;
    while (b) {
        if (b & 1) ans = ans * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return ans;
}
int fastio = (IOS,0);
#define endl '\n'
#define puts(s) cout << s << endl
const int N = 50010;
int n;
struct node {
	int a,b,id;
}a[N],_a[N];
struct ans_type {
	int v;
	double cnt;
	ans_type (int _v = 0,double _cnt = 0) {
		v = _v,cnt = _cnt;
	}
}f[N],g[N];
ans_type operator + (ans_type a,ans_type b) {return ans_type (a.v + b.v,a.cnt + b.cnt);}
ans_type max (ans_type a,ans_type b) {
	if (a.v != b.v) return a.v > b.v ? a : b;
	return ans_type (a.v,a.cnt + b.cnt);
}
int lowbit (int x) {return x & -x;}
struct BIT_suf {
	ans_type c[N];
	void clear (int x) {for (int i = x;i;i -= lowbit (i)) c[i] = ans_type (0,0);}
	void modify (int x,ans_type d) {for (int i = x;i;i -= lowbit (i)) c[i] = max (c[i],d);}
	ans_type query (int x) {
		ans_type ans;
		for (int i = x;i <= n;i += lowbit (i)) ans = max (ans,c[i]);
		return ans;
	}
}c1;
struct BIT_pre {
	ans_type c[N];
	void clear (int x) {for (int i = x;i <= n;i += lowbit (i)) c[i] = ans_type (0,0);}
	void modify (int x,ans_type d) {for (int i = x;i <= n;i += lowbit (i)) c[i] = max (c[i],d);}
	ans_type query (int x) {
		ans_type ans;
		for (int i = x;i;i -= lowbit (i)) ans = max (ans,c[i]);
		return ans;
	}
}c2;
bool cmp1 (node x,node y) {return x.a > y.a;}
bool cmp2 (node x,node y) {return x.a < y.a;}
void solve1 (int l,int r) {
	if (l == r) return ;
	int mid = l + r >> 1;
	solve1 (l,mid);
	for (int i = l;i <= r;i++) a[i] = _a[i];
	sort (a + l,a + mid + 1,cmp1),sort (a + mid + 1,a + r + 1,cmp1);
	for (int i = mid + 1,j = l;i <= r;i++) {
		while (j <= mid && a[j].a >= a[i].a) c1.modify (a[j].b,f[a[j].id]),j++;
		f[a[i].id] = max (f[a[i].id],c1.query (a[i].b) + ans_type (1,0));
	}
	for (int i = l;i <= mid;i++) c1.clear (a[i].b);
	solve1 (mid + 1,r);
}
void solve2 (int l,int r) {
	if (l == r) return ;
	int mid = l + r >> 1;
	solve2 (l,mid);
	for (int i = l;i <= r;i++) a[i] = _a[i];
	sort (a + l,a + mid + 1,cmp2),sort (a + mid + 1,a + r + 1,cmp2);
	for (int i = mid + 1,j = l;i <= r;i++) {
		while (j <= mid && a[j].a <= a[i].a) c2.modify (a[j].b,g[a[j].id]),j++;
		g[a[i].id] = max (g[a[i].id],c2.query (a[i].b) + ans_type (1,0));
	}
	for (int i = l;i <= mid;i++) c2.clear (a[i].b);
	solve2 (mid + 1,r);
}
int main () {
	cin >> n;
	for (int i = 1;i <= n;i++) cin >> a[i].a >> a[i].b,a[i].id = i;
	vector <int> all;
	auto find = [&](int x) {return lower_bound (all.begin (),all.end (),x) - all.begin () + 1;};
	for (int i = 1;i <= n;i++) all.pb (a[i].b);
	sort (all.begin (),all.end ());
	all.erase (unique (all.begin (),all.end ()),all.end ());
	for (int i = 1;i <= n;i++) a[i].b = find (a[i].b);
	for (int i = 1;i <= n;i++) _a[i] = a[i];
	for (int i = 1;i <= n;i++) f[i] = g[i] = ans_type (1,1);
	solve1 (1,n);
	reverse (_a + 1,_a + n + 1);
	solve2 (1,n);
	ans_type ans;
	for (int i = 1;i <= n;i++) ans = max (ans,f[i]);
	cout << ans.v << endl;
	// for (int i = 1;i <= n;i++) cout << 0 << ' ';
	// cout << endl;
	// return 0;
	for (int i = 1;i <= n;i++) {
		if (f[i].v + g[i].v - 1 == ans.v) cout << fixed << setprecision (5) << f[i].cnt * g[i].cnt / ans.cnt << ' ';
		else cout << 0 << ' ';
	}
	cout << endl;
	return 0;
}