都是老套路了,如果n=5,要把区间[1,4]染色,可以递归去染区间[1,3]和区间[4,4],如果区间相等就自加,不相等继续递归寻找对应区间。
打印结果时,把所有到达叶节点包含i的区间值相加,就是最后答案。
AC代码:
#include<cstdio> #include<algorithm> #include<cstring> using namespace std; const int maxn=8e5; int tree[maxn]; void Build_tree(int l,int r,int ll,int rr,int cur){ if(l==ll&&r==rr){ tree[cur]++; return; } int mid=(ll+rr)/2; if(r<=mid) Build_tree(l,r,ll,mid,cur<<1); else if(l>=mid+1) Build_tree(l,r,mid+1,rr,(cur<<1)+1); else { Build_tree(l,mid,ll,mid,cur<<1); Build_tree(mid+1,r,mid+1,rr,(cur<<1)+1); } } int u,n; void print(int l,int r,int cur,int cnt){ cnt+=tree[cur]; if(l==r) { ++u; if(u==n) printf("%d\n",cnt); else printf("%d ",cnt); return; } print(l,(l+r)/2,cur<<1,cnt); print((l+r)/2+1,r,(cur<<1)+1,cnt); } int main(){ while(scanf("%d",&n)==1&&n){ memset(tree,0,sizeof(tree)); u=0; int l,r; for(int i=0;i<n;++i){ scanf("%d%d",&l,&r); Build_tree(l,r,1,n,1); } print(1,n,1,0); } return 0; }
如有不当之处欢迎指出!