题意：
给c1~c2的区间涂色。询问最后有几段颜色区域。初始无色。
思路：
lazy标记，区间逐渐更新。
自己最初写了一个从后往前的仅仅带标记的线段树，竟然WA了。很迷。只好规规矩矩来一遍，终于过了
#include <stdio.h> #include <algorithm> #include <cstring> using namespace std; const int maxn=8050; struct node { int left,right,val,lazy ; }tree[4*maxn]; int n; int color[maxn*4]; int ans[maxn*4]; int l[maxn],r[maxn],c[maxn]; int cnt=0; void Build(int i,int left,int right) { tree[i].lazy=0; tree[i].val=-1; tree[i].left=left; tree[i].right=right; if(left==right) { return ; } int mid=(tree[i].left+tree[i].right)>>1; Build(i<<1,left,mid); Build(i<<1|1,mid+1,right); return ; } void update(int i,int left,int right,int w) { if(tree[i].left==left&&tree[i].right==right) { tree[i].lazy=1; tree[i].val=w; return ; } if(tree[i].lazy) { tree[i].lazy=0; tree[i<<1].lazy=1,tree[i<<1|1].lazy=1; tree[i<<1].val=tree[i].val,tree[i<<1|1].val=tree[i].val; } int mid=(tree[i].left+tree[i].right)>>1; if(left>mid) { update(i<<1|1,left,right,w); } else if(right<=mid) { update(i<<1,left,right ,w); } else { update(i<<1,left,mid,w); update(i<<1|1,mid+1,right,w); } return ; } void query(int i) { if(tree[i].lazy) { for(int j=tree[i].left;j<=tree[i].right;j++) color[j]=tree[i].val; return ; } if(tree[i].left==tree[i].right) return ; int mid=(tree[i].left+tree[i].right)>>1; query(i<<1); query(i<<1|1); } int main() { while(~scanf("%d",&n)) { cnt=0; memset(color,-1,sizeof(color)); memset(tree,0,sizeof(tree)); memset(ans,0,sizeof(ans)); Build(1,1,maxn); int num=0; for(int i=1;i<=n;i++) { int u,v,w; scanf("%d%d%d",&u,&v,&w); update(1,u+1,v,w); } query(1); for(int i=1;i<=maxn;i++) { if(color[i]!=color[i-1]&&color[i]!=-1) { ans[color[i]]++; } } for(int i=0;i< maxn;i++) if(ans[i]!=0) printf("%d %d\n",i,ans[i]); printf("\n"); } } /* 3 1 2 0 0 1 0 2 3 0 */下面的代码Wa了。求帮助
#include <stdio.h> #include <algorithm> #include <cstring> using namespace std; const int maxn=8050; struct node { int left,right,val,col; }tree[4*maxn]; int n; int color[maxn*4]; int ans[maxn*4]; int l[maxn],r[maxn],c[maxn]; int cnt=0; void Build(int i,int left,int right) { tree[i].left=left; tree[i].right=right; if(left==right) { tree[i].col=-1; tree[i].val=0; return ; } int mid=(tree[i].left+tree[i].right)>>1; Build(i<<1,left,mid); Build(i<<1|1,mid+1,right); tree[i].val=tree[i<<1].val&&tree[i<<1|1].val; return ; } void update(int i,int left,int right,int w) { if(tree[i].val==1 ) { return ; } if(tree[i].left==left&&tree[i].right==right) { tree[i].val=1; tree[i].col=w; for(int j=tree[i].left;j<=tree[i].right;j++) color[j]=w; return ; } int mid=(tree[i].left+tree[i].right)>>1; if(left>mid) { update(i<<1|1,left,right,w); } else if(right<=mid) { update(i<<1,left,right ,w); } else { update(i<<1,left,mid,w); update(i<<1|1,mid+1,right,w); } tree[i].val=tree[i<<1].val&&tree[i<<1|1].val; return ; } int main() { while(~scanf("%d",&n)) { cnt=0; memset(color,-1,sizeof(color)); memset(tree,0,sizeof(tree)); memset(ans,0,sizeof(ans)); Build(1,1,maxn); int num=0; for(int i=1;i<=n;i++) { int u,v,w; scanf("%d%d%d",&u,&v,&w); if(u>=v) continue; l[++num]=++u,r[num]=v,c[num]=w; } for(int i=num;i>=1;i--) { update(1,l[i],r[i],c[i]); } for(int i=1;i<=maxn;i++) { if(color[i]!=color[i-1]&&color[i]!=-1) { ans[color[i]]++; } } for(int i=0;i<=maxn;i++) if(ans[i]!=0) printf("%d %d\n",i,ans[i]); printf("\n"); } } /* 3 1 2 0 0 1 0 2 3 0 */
