CF751D Difficult Mountain

Problem - D - Codeforces

一座山初始高为d，每个人有两个权值s和a， s大于等于当前山高的人可以爬过，但同时山高会和这个人的a值取max。求最优能过几个人。

貌似可以直接按最大值排序，依次取就可以...但这种做法正确性感觉很难证明，同时比赛场上一般难以想到。

下面是貌似是题解的做法：

首先扔掉连初始山高都爬不过的人，并且离散化权值。

然后把人分为两类，一类s权值大于等于a，另一类s权值小于a。

容易发现第一类人只要按s权值排序后，是可以全都一起取的。

此时又能发现，第一类人一定全取最优，不会存在第二类人顶替掉某个第一类人的情况。（简单证明：若有一个第二类人顶替掉第一类人，那么记第一类人权值(s1,a1), s1>=a1,第二类人权值(s2,a2), s2 <= a2,因为顶替，所以有:s1 < a2, s2 < a1 即 s2 < a1 <= s1 < a2,那么发现顶替后的第二类人爬山能力更辣鸡，而且还会把山变得更高，显然不优，因此不会替换）

那么现在要考虑的就是往所有第一类人的集合中插入尽可能多的第二类人。

首先，假设把一个第二类人(s*, a*)插入到第i个和第i +1 个第一类人之间（第一类人已按照s排序），那么要满足：s* >= max{a1,a2, ..., ai}且a* <= si + 1

容易发现这个第二类人可插入位置是一段区间（可能不存在，直接跳过），区间的右边界由s*决定，左边界由a*决定,且右边界随s*增大而增大，左边界随a*增大而增大。

但是插入一个第二类人后， 后续的第二类人插入还会受到两个额外限制

（1）当前插入的s* >=所有之前插入在当前位置左边的bf_a*的最大值

（2）当前插入的a* <=所有之前插入在当前位置右边的bf_s*的最小值

其实本质上就是插入的人两两之间的限制,考虑下列情况：

s1 < a1 , s2 < a2

若s2 > s1

s2插入在s1后面，s1与s2都可能满足（若只能满足一个，可以dp保留哪个更优；能同时满足也能dp到）

s2插入在s1前面，s1一定不能满足，只有s2可能满足（此时即使dp，也dp不到两个同时满足的状态）

因此可以发现s越大的第二类人插在越右边越好，而根据之前又有s越大的人越能够插在越右边。故把第二类人按照s权值从大到小依次插入，插入的位置都选在最右端，那么此时只需考虑（2）， 可维护dp, dp(x)表示上一次插入的s值为x时，最多已插入人数，每次就考虑(s*, a*)时就要查询max{dp(a*),dp(a* + 1), ...},然后加一，更新dp(s*)，显然可以用一棵线段树搞。

#include <bits/stdc++.h>
#define pii pair<int,int>
#define fi first
#define sc second
#define pb push_back
#define ll long long
#define trav(v, x) for(auto v:x)
#define VI vector<int>
#define VLL vector<ll>
//define double long double
#define all(x) (x).begin(),(x).end()
using namespace std;
const double eps = 1e-10;//1e-12
const int N = 1e6 + 100;
const ll mod = 998244353;//1e9 + 7;
const int inf = 1e9;

int n, m;

vector<int>buk;
vector<pii>a, b;

int seg[N * 4];

#define mid ((l + r) >> 1)
#define ls (k << 1)
#define rs (k << 1 | 1)

void push_up(int k)
{
	seg[k] = max(seg[ls], seg[rs]);
}

void upd(int to, int val, int l = 1, int r = m, int k = 1)
{
	if(l == r)
	{
		seg[k] = max(seg[k], val);
		return;
	}
	if(to <= mid)
		upd(to, val, l, mid, ls);
	else
		upd(to, val, mid + 1, r, rs);
	push_up(k);
}

int ask(int L, int R, int l = 1, int r = m, int k = 1)
{
	if(l > R || r < L)
		return 0;
	if(L <= l && r <= R)
	{
		return seg[k];
	}
	return max(ask(L, R, l, mid, ls), ask(L, R, mid + 1, r, rs));
}

void sol()
{
	int cur;
	cin >> n >> cur;
	for(int i = 1; i <= n; i++)
	{
		int x, y;
		cin >> x >> y;
		if(x < cur)
			continue;
		if(x >= y)
			a.pb(pii(x, y));
		else
			b.pb(pii(x, y));
		buk.pb(x);
		buk.pb(y);
	}
	sort(all(buk));
	buk.erase(unique(all(buk)), buk.end());
	m = buk.size();
	for(int i = 0; i < a.size(); i++)
	{
		a[i].fi = lower_bound(all(buk), a[i].fi) - buk.begin() + 1;
		a[i].sc = lower_bound(all(buk), a[i].sc) - buk.begin() + 1;		
	}
	for(int i = 0; i < b.size(); i++)
	{
		b[i].fi = lower_bound(all(buk), b[i].fi) - buk.begin() + 1;
		b[i].sc = lower_bound(all(buk), b[i].sc) - buk.begin() + 1;		
	}
	int ans = a.size();
	a.pb(pii(inf, inf));
	sort(all(a));
	sort(all(b));
	vector<int> mx;
	mx.resize(a.size());
	for(int i = 0; i < mx.size(); i++)
	{
		mx[i] = a[i].sc;
		if(i > 0)
			mx[i] = max(mx[i], mx[i - 1]);
	}
	int res = 0;
	for(int i = b.size() - 1; i >= 0; i--)
	{
		int s, t;
		s = b[i].fi, t = b[i].sc;
		int lp = lower_bound(all(a), pii(t, -1)) - a.begin();//between lp - 1,lp
		int rp = upper_bound(all(mx), s) - mx.begin();// between rp - 1,rp
	//	cerr << s << ' ' << t << ' ' << lp << ' ' << rp << '\n';
		if(lp > rp)
			continue;
		//put in rp - 1, rp
		int val = ask(t, m) + 1;
		res = max(res, val);
	//	cerr << s << ' ' << m << ' ' << val << '\n';
		upd(s, val);
	}
	cout << ans + res << '\n';
}

signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	sol();
}

upd：忽然发现插入时，貌似把第二类人按照a*排序，然后依次从小到大能插入就插入，可以不需要dp。

#include <bits/stdc++.h>
#define pii pair<int,int>
#define fi first
#define sc second
#define pb push_back
#define ll long long
#define trav(v, x) for(auto v:x)
#define VI vector<int>
#define VLL vector<ll>
//define double long double
#define all(x) (x).begin(),(x).end()
using namespace std;
const double eps = 1e-10;//1e-12
const int N = 1e6 + 100;
const ll mod = 998244353;//1e9 + 7;
const int inf = 1e9;

int n, m;

vector<int>buk;
vector<pii>a, b;

void sol()
{
	int cur;
	cin >> n >> cur;
	for(int i = 1; i <= n; i++)
	{
		int x, y;
		cin >> x >> y;
		if(x < cur)
			continue;
		if(x >= y)
			a.pb(pii(x, y));
		else
			b.pb(pii(x, y));
		buk.pb(x);
		buk.pb(y);
	}
	sort(all(buk));
	buk.erase(unique(all(buk)), buk.end());
	m = buk.size();
	for(int i = 0; i < a.size(); i++)
	{
		a[i].fi = lower_bound(all(buk), a[i].fi) - buk.begin() + 1;
		a[i].sc = lower_bound(all(buk), a[i].sc) - buk.begin() + 1;		
	}
	for(int i = 0; i < b.size(); i++)
	{
		b[i].fi = lower_bound(all(buk), b[i].fi) - buk.begin() + 1;
		b[i].sc = lower_bound(all(buk), b[i].sc) - buk.begin() + 1;		
	}
	int ans = a.size();
	a.pb(pii(inf, inf));
	sort(all(a));
	sort(all(b));
	vector<int> mx;
	mx.resize(a.size());
	for(int i = 0; i < mx.size(); i++)
	{
		mx[i] = a[i].sc;
		if(i > 0)
			mx[i] = max(mx[i], mx[i - 1]);
	}
	int res = 0;
	sort(all(b), [](pii x, pii y){
		return x.sc < y.sc;
	});
	int cur_a = 0;
	for(int i = 0; i < b.size(); i++)
	{
		int s, t;
		s = b[i].fi, t = b[i].sc;
		if(s < cur_a)continue;
		int lp = lower_bound(all(a), pii(t, -1)) - a.begin();//between lp - 1,lp
		int rp = upper_bound(all(mx), s) - mx.begin();// between rp - 1,rp
		if(lp > rp)
			continue;
		++ans;
		cur_a = t;
	}
	cout << ans + res << '\n';
}

signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	sol();
}