带权区间着色问题，与区间着色问题是一回事
着色时进行懒操作，如果访问区间与当前着色区间完全匹配，着色，或者当前访问区间的颜色与所着颜色一样时，然后返回
若不满足以上情况，需要对子区间进行着色，并且可以说明当前区间会变成多种颜色，由于进行懒操作，父区间的信息不一定传递给了子区间，此时我们需要判断，如果父区间为单色，说明对父区间着色后还没访问父区间的子区间，需要先将信息传递下去，然后访问子区间
另外，访问完子区间后，需要将子区间的信息向上递归更新父区间信息，因为懒操作只是将父区间的信息传递下来，而更新完对子区间后，子区间的改变信息会对父区间造成影响，需向上更新父区间
代码：
#include<iostream> #include<memory.h> #include<string> #include<cstdio> #include<algorithm> #include<math.h> #include<stack> #include<queue> #include<vector> #include<map> #include<ctime> using namespace std; const int MAX=100005; struct node { int l,r,col; bool flag; }t[MAX*4]; void build(int ll,int rr,int n) { t[n].l=ll; t[n].r=rr; t[n].col=1; t[n].flag=false; if(ll==rr) return; int mid=(ll+rr)>>1; build(ll,mid,n<<1); build(mid+1,rr,n<<1|1); } void update(int ll,int rr,int n,int val) { if(val==t[n].col&&!t[n].flag) return; if(t[n].l==ll&&t[n].r==rr) { t[n].col=val; t[n].flag=false; return; } int mid=(t[n].l+t[n].r)>>1; if(!t[n].flag) { t[n<<1].flag=t[n<<1|1].flag=false; t[n<<1].col=t[n<<1|1].col=t[n].col; } if(mid>=rr) update(ll,rr,n<<1,val); else if(mid<ll) update(ll,rr,n<<1|1,val); else { update(ll,mid,n<<1,val); update(mid+1,rr,n<<1|1,val); } if((t[n<<1].col!=t[n<<1|1].col)||t[n<<1].flag||t[n<<1|1].flag) t[n].flag=true; } int query(int n) { if(!t[n].flag) { return t[n].col*(t[n].r-t[n].l+1); } if(t[n].l==t[n].r) return t[n].col; return query(n<<1)+query(n<<1|1); } int main() { int i,j,k,T,ca,q,n; scanf("%d",&T); for(ca=1;ca<=T;ca++) { scanf("%d",&n); build(1,n,1); scanf("%d",&q); while(q--) { scanf("%d%d%d",&i,&j,&k); update(i,j,1,k); } printf("Case %d: The total value of the hook is %d.\n",ca,query(1)); } return 0; }
