[POJ] 1769. Minimizing maximizer

題目連結:http://poj.org/problem?id=1769

---

一開始用cin有把連結斷開還是吃了個TLE QQ。
回到正題，本題我個人的一開始的想法其實是看看某個線段插到線段樹後可以幹嘛，後來想一想後發現有點DP的fu，狀態大概就是$dp[i]$為最遠轉移到i時的最小值，那新增一條線段的時候其實就是查$[l,r]$之間的最小值，然後把$r$那個點設成先前查到的最小值+1，因為$\displaystyle dp[i] = \min_{l \leq j \leq r}dp[j]+1 $，不過實際在寫的時候要再跟原值取個min，因為有可能r被覆蓋很多次之類的。

#include <cstdio>
#include <algorithm>
using std::min;

const int N = 50000 + 10;
const int INF = 1<<30;

class SegTree{
	private:
		int nodes[N<<2], size;
		inline int lc(int x){return (x<<1)+1;}
		inline int rc(int x){return (x<<1)+2;}
		void build(int l, int r, int id){
			nodes[id] = INF;
			if(r-l>1){
				int mid=(l+r)>>1;
				build(l, mid, lc(id));
				build(mid, r, rc(id));
			}
		}
		void modify(int ql, int qr, int v, int l, int r, int id){
			if(qr <= l or r <= ql) return;
			if(ql <= l and r <= qr){
				nodes[id] = min(nodes[id], v);
				return;
			}
			int mid = (l+r)>>1;
			modify(ql, qr, v, l, mid, lc(id));
			modify(ql, qr, v, mid, r, rc(id));
			nodes[id] = min(nodes[lc(id)], nodes[rc(id)]);
		}
		int query(int ql, int qr, int l, int r, int id){
			if(qr <= l or r <= ql) return INF;
			if(ql <= l and r <= qr) return nodes[id];
			int mid=(l+r)>>1;
			int ll = query(ql, qr, l, mid, lc(id));
			int rr = query(ql, qr, mid, r, rc(id));
			return min(ll, rr);
		}
	public:
		void build(int n){
			size=n;
			build(0, n, 0);
		}
		void modify(int pos, int v){
			modify(pos, pos+1, v, 0, size, 0);
		}
		int query(int l, int r){
			return query(l, r, 0, size, 0);
		}
} seg;

int main(){
	int n, m;
	scanf("%d%d",&n,&m);
	seg.build(n+5);
	seg.modify(1,0);
	for(int i=0;i<m;i++){
		int l, r;
		scanf("%d%d",&l,&r);
		int k = seg.query(l, r);
		seg.modify(r, k+1);
	}
	printf("%d\n", seg.query(n, n+1));
	return 0;
}