一个区间，都种上树，m次操作，每次拔掉一个区间的树，
区间可能重叠
（1）当 1≤L≤10000 且 1≤M≤100 时，直接模拟，可以a掉
#include<cstdio> #include<cstdlib> using namespace std; int sum,n; bool tr[10003]; int main() { scanf("%d%d",&sum,&n); sum++; for(int i=0;i<=sum;i++) tr[i]=true; int l,r; while(n--) { scanf("%d%d",&l,&r); for(int i=l;i<=r;i++) if(tr[i]) sum--,tr[i]=false; } printf("%d ",sum); return 0; }
（2）当 1≤L≤1亿 且1≤M≤2万时
【对区间操作】
离散 + 离线快排 区间合并
#include<cstdio> #include<cstdlib> #include<algorithm> using namespace std; int l,n,sum; const int N=2e4+3; struct node { int l,r; bool operator < (const node & o) const { return l!=o.l ?l<o.l :r<o.r; } }d[N]; int main() { scanf("%d%d",&l,&n); for(int i=1;i<=n;i++) scanf("%d%d",&d[i].l ,&d[i].r ); sort(d+1,d+n+1); int ll=0,rr=-1; for(int i=1;i<=n;i++) { if(d[i].l >rr) sum+=rr-ll+1,ll=d[i].l ,rr=d[i].r ; else rr=max(rr,d[i].r ); } sum+=rr-ll+1; printf("%d ",l+1-sum); return 0; }
（3）
n,m<=50000
在线砍树+询问区间中 有多少不同时间种的树
【括号序列】
每次种树，在l上‘（’，r上‘）’
然后询问的时候，统计0-r上‘（’的个数，减去0-（l-1）上‘）’的个数
神奇的括号序列...
#include<cstdio> #include<cstdlib> using namespace std; int n,m; const int N=50003; int tr[N][2];//'(' ')' int lowbit(int x) { return x&(-x); } void add(int p,int k) { while(p<=n) tr[p][k]++,p+=lowbit(p); } int query(int p,int k) { int ans=0; while(p) ans+=tr[p][k],p-=lowbit(p); return ans; } int main() { scanf("%d%d",&n,&m); int op,l,r; for(int i=1;i<=m;i++) { scanf("%d%d%d",&op,&l,&r); if(op==1) add(l,0),add(r,1); else printf("%d ",query(r,0) -query(l-1,1)); } return 0; }
over