[数据结构与算法][CF1602F]Difficult Mountain

题目

传送门 to CF

思路

动态规划

显然能爬山的人等价于
$$s_i?\underset{j=1}{\overset{i?1}{\max }}{a}_j\wedge s_i?d$$
既然前面的人的 $a$ 完全不重要，考虑直接记 $f(v)$ 为前缀 $\max a$ 等于 $v$ 时的最多爬山者。显然一个人不会对爬山难度产生影响时（即 $a_i?\max a$ 时）立刻爬山最优，所以如果从 $f(j)$ 转移过来，所有的 $a_i?j$ 都已经爬过山了（否则不优），于是
$$f(v)=f(j)+\sum _{j<a_i?v}[s_i?v](j<v)$$
于是很显然的，将所有人按照 $a_i$ 排序，此时 $d{p}_i=f(a_i)$，转移则是从 $d{p}_j$ 转移而来。用 $\mathrm{s}\mathrm{e}\mathrm{t}$ 维护一下，可以很轻松的得到 $s_j?a_i$ 的所有 $j$，毕竟 $a_i$ 是单增的。线段树实现转移，时间复杂度 $\mathcal{O}(n\log n)$ 。

贪心

我原本以为贪心是完全不可行的。结果它确实可行……

当只有 $a?s$ 的人时，按照 $a$ 或 $s$ 升序都可以。只有 $s<a$ 的人时，按照 $a$ 或 $s$ 升序都可以。问题在于当二者交错时，是否仍然具有顺序关系？

比如第一类 $a?s$ 的人。此时 交换 $s$ 的逆序对，不一定仍然是合法的方案。所以我就做不下去了。然而我没有注意到的是，将靠前的较大的 $s$ 移动 到较小的 $s$ 的后面就行了……

所以第一类人一定是按照 $s$ 升序进行的。第二类人则一定按照 $a$ 升序（为什么不用 $s$ 呢？因为你会发现最优策略是选择 $a$ 最小的一个）。

现在如何将二者穿插呢？我也不会了。但是「炎翼鸟」告诉我们：只需要优先选择第一类人。唯一需要选择第二类人的情况是 $s_j?a_i?s_i<a_j$，即二者选择其中之一，另一个就不能选了。然而我们上面说过了，选择 $a$ 最小的是最好的。所以就选第一类人就好了。

时间复杂度仍然是 $\mathcal{O}(n\log n)$ 。

代码

只给出动态规划的代码。

#include <cstdio>
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <set>
# define rep(i,a,b) for(int i=(a); i<=(b); ++i)
# define drep(i,a,b) for(int i=(a); i>=(b); --i)
typedef long long int_;
inline int readint(){
	int a = 0, c = getchar(), f = 1;
	for(; '0'>c||c>'9'; c=getchar())
		if(c == '-') f = -f;
	for(; '0'<=c&&c<='9'; c=getchar())
		a = (a<<3)+(a<<1)+(c^48);
	return a*f;
}
void writeint(int x){
	if(x > 9) writeint(x/10);
	putchar((x-x/10*10)^48);
}
namespace std{
	template < typename T >
	inline void getMax(T &a,const T &b){
		if(a < b) a = b;
	}
}

const int MAXN = 500005;
struct Node{
	int s, a;
	operator int() const { return a; }
};
Node node[MAXN];

namespace SgTree{
	void build(int n);
	void modify(int ql,int qr,int qv);
	int query(int ql,int qr);
}
std::set< std::pair<int,int> > pos;
int main(){
	int n = readint()+1, d = readint(), xyx = 0;
	rep(i,2,n){
		node[i].s = readint(), node[i].a = readint();
		if(node[i].a <= d){
			if(d <= node[i].s) ++ xyx;
			-- i; -- n; // remove this
		}
	}
	node[1].s = 0, node[1].a = d; // virtual
	std::sort(node+2,node+n+1); SgTree::build(n);
	int ans = 0; // max element of dp
	for(int i=2,dp,rnk; i<=n; ++i){
		while(!pos.empty() && (*pos.begin()).first < node[i].a){
			SgTree::modify(1,(*pos.begin()).second-1,-1);
			pos.erase(pos.begin()); // no more usable
		}

		rnk = int(std::lower_bound(node+1,node+i,node[i].s+1)-node);
		dp = std::max(SgTree::query(1,rnk-1)+1,SgTree::query(rnk,i-1));
		SgTree::modify(i,i,dp); // put into segment tree
		if(ans < dp) ans = dp; // get max

		pos.insert(std::make_pair(node[i].s,i));
		SgTree::modify(1,i-1,1);
	}
	printf("%d\n",xyx+ans);
	return 0;
}

namespace SgTree{
	int val[MAXN*3], tag[MAXN*3], ass;
	void build(int n){
		for(ass=1; ass<n+2; ass<<=1);
	}
	void pushUp(int o){
		val[o] = std::max(val[o<<1],val[o<<1|1])+tag[o];
	}
	void modify(int ql,int qr,int qv){
		int l = ql+ass-1, r = qr+ass+1;
		while((l^1) != r){
			if(!(l&1)) tag[l^1] += qv, val[l^1] += qv;
			if(r&1) tag[r^1] += qv, val[r^1] += qv;
			pushUp(l >>= 1), pushUp(r >>= 1);
		}
		while(l >>= 1) pushUp(l);
	}
	int query(int ql,int qr){
		if(ql > qr) return -MAXN; // empty set
		int l = ql+ass-1, r = qr+ass+1, lres = 0, rres = 0;
		while((l^1) != r){
			if(!(l&1)) std::getMax(lres,val[l^1]);
			if(r&1) std::getMax(rres,val[r^1]);
			lres += tag[l >>= 1], rres += tag[r >>= 1];
		}
		std::getMax(rres,lres);
		while(l >>= 1) rres += tag[l];
		return rres;
	}
}