ZOJ - 1610 经典线段树染色问题
这个是一个经典线段树染色问题，不过题目给的是左右左右坐标，即[0,3]包含0-1这一段 1-2这一段 2-3这一段，和传统的染色不太一样，不过其实也不用太着急。
我们把左边的坐标+1，即可，那么[0,3]其实变成了[1,3]而线段树是按照点询问的，也就是每个点代表的颜色，我们就有了1,2,3,这个三个，并且避免了线段树编号不能到0的情况，然后代码就十分简单了，无需laze标记，因为每个节点的颜色就可以当成laze标记，然后不断往下pushdown既可以，当时还有一个问题就是线段树访问连续两个节点的颜色是相同的，那么它其实是一个连续的算一个，我们可以维护一个last，代表前一个区间的颜色，由于我们递归是按照左右儿子进行递归的，左儿子过了肯定是右儿子，实际上这是连续的，所以我们这需要判断这个区间颜色是不是和前面那个区间的颜色相同，从而判断这两个颜色是否相邻即可
#include<iostream> #include<string.h> #include<algorithm> #include<stdio.h> using namespace std; const int maxx = 8004; inline int L(int r){return r<<1;}; inline int R(int r){return r<<1|1;}; inline int MID(int l,int r){return (l+r)>>1;}; int n,last; struct node{ int l,r,col; }tree[maxx<<2]; int ans[maxx]; void pushdown(int root){ if(tree[root].col!=-1){ tree[L(root)].col=tree[root].col; tree[R(root)].col=tree[root].col; tree[root].col=-1; } } void buildtree(int root,int l,int r){ tree[root].l=l; tree[root].r=r; tree[root].col=-1; if (l==r){ return; } int mid=MID(l,r); buildtree(L(root),l,mid); buildtree(R(root),mid+1,r); } void update(int root,int ul,int ur,int c){ int l=tree[root].l; int r=tree[root].r; if(ul<=l && r<=ur){ tree[root].col=c; return; }; if (tree[root].col==c)return; pushdown(root); int mid=MID(l,r); if (ur<=mid){ update(L(root),ul,ur,c); }else if(ul>mid){ update(R(root),ul,ur,c); }else{ update(L(root),ul,mid,c); update(R(root),mid+1,ur,c); } } void query(int root,int ql,int qr){ if (ql==qr){ if(tree[root].col!=-1 && tree[root].col!=last){ ans[tree[root].col]++; } last=tree[root].col; return; } pushdown(root); if(ql==qr)return; int mid = (ql+qr)>>1; query(L(root),ql,mid); query(R(root),mid+1,qr); } int main(){ while(~scanf("%d",&n)){ int x,y,z; buildtree(1,1,8000); for (int i=1;i<=n;i++){ scanf("%d%d%d",&x,&y,&z); update(1,x+1,y,z); } last=-1; memset(ans,0,sizeof(ans)); query(1,1,8000); for (int i=0;i<=8000;i++){ if (ans[i]){ printf("%d %d\n",i,ans[i]); } } puts(""); } return 0; }
