[TIOJ] 1941. 直升機抓寶 (Helicopter)

題目連結:https://tioj.infor.org/problems/1941

---

這題應該可以輕鬆想到$O(N^2)$的DP方式，同時也會發現那樣子太慢。
仔細觀察DP的表格後，發現他是一個單調的表格，也就是由左至右遞增，同時由下至上遞增，接著研究一下每個轉移對DP表格的貢獻，發現他必定會將他自己那個區間的DP值+1，而後面則為了要維護單調的性質，會再跟他取max。
那這類題目，其實我們可以維護每一段的DP值，每次加入一個新的轉移來源後，也代表加入了一個斷點，但是同時也有可能把自身後面的斷點吃光光。
所以複雜度會是$O(N log N)$，因為每個斷點只會出現跟消失一次，而單次新增跟刪除了複雜度都是$O(log N)$

#include <bits/stdc++.h>
using namespace std;

class BIT{
	private:
		int n;
		vector<int> arr;
		inline int lowbit(int x){return x&(-x);}
		void modify(int p, int x){
			for(;p;p-=lowbit(p)) arr[p] += x;
		}
	public:
		void init(int n_){
			n = n_; arr.clear();
			arr.resize(n);
		}
		void modify(int l, int r, int v){
			modify(l, -v);
			modify(r, v);
		}
		int query(int x){
			int ret = 0;
			for(;x<n;x+=lowbit(x)) ret += arr[x];
			return ret;
		}
} bit;

set<int> st;

int main(){
	int n; scanf("%d", &n);
	bit.init(n+1); st.insert(n);
	for(int i=0;i<n;i++){
		int l, r; scanf("%d%d", &l, &r);	
		st.insert(l);
		auto it = st.upper_bound(r);
		bit.modify(l, *it, 1);
		int cur = bit.query(*it);
		for(;it!=prev(st.end());it=st.erase(it)){
			int nv = bit.query((*it)+1);
			if(nv > cur) break;
			bit.modify(*it, *next(it), cur-nv);
		}
	}
	printf("%d\n", bit.query(n));
	return 0;
}