考察线段树的区间最小和单点修改.因为树状数组还没学完,所以还是用线段树来写..其实线段树还没系统的学...但是这种题只是个模板而已.
考虑我到了第i个,我包含的区间是(s[i],t[i]).这里面的区间都是可取的,我要做的就是问这个区间的最小值在哪里,然后我假如找到了这个区间的最小值,那么我只要更新右端点即可,因为下次询问假如它是要用这个区间,那么肯定是包含这个区间的右端点的,如此这个题就完美的解决了.
代码如下:
#include <stdio.h> const int N=2e6+4; int s[N],t[N],tmin[N]; int min(int a,int b) { if(a<b) return a; else return b; } int query(int u,int L,int R,int l,int r)//从第u个节点开始,在区间L,R范围内查询l,r的min { if(R<l||L>r) return 2e9; if(L>=l&&R<=r) return tmin[u]; int mid=(L+R)>>1; return min(query(u<<1,L,mid,l,r),query(u<<1|1,mid+1,R,l,r)); } void modify(int u,int L,int R,int pos,int val) { if(L==R) {tmin[u]=min(tmin[u],val);return;} int mid=(L+R)>>1; if(pos<=mid) modify(u<<1,L,mid,pos,val); else modify(u<<1|1,mid+1,R,pos,val); tmin[u]=min(tmin[u<<1],tmin[u<<1|1]); } int main() { int n,m; scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) scanf("%d%d",&s[i],&t[i]); for(int i=1;i<=4*n;i++) tmin[i]=2e9; modify(1,1,n,1,0); for(int i=1;i<=m;i++) { int cnt=query(1,1,n,s[i],t[i]); modify(1,1,n,t[i],cnt+1); } printf("%d\n",query(1,1,n,n,n)); return 0; }