| Time Limit: 1000MS | Memory Limit: 65536K | |
| Total Submissions: 40116 | Accepted: 12103 |
Description
Input
Output
Sample Input
2 2 4 C 1 1 2 P 1 2 C 2 2 2 P 1 2
Sample Output
2 1
题意：一段长度材料需要涂色，找一定区间内的颜色种类；
第一行输入三个非负整数，Ｌ Ｔ Ｏ 分别代表长度，颜色种类和下面再输入几行；
下面Ｏ行：＇Ｃ＇ Ａ Ｂ Ｃ：表示在Ａ Ｂ 区间图一种颜色 Ｃ；
＇Ｐ＇ Ａ Ｂ：让你输出Ａ Ｂ区间内有多少种颜色；
思路：1.延迟覆盖的操作。2.位操作，用 | 来合并颜色种类。3.updata操作时递归回来，两个子节点的信息对父节点的更新。
经典的线段树。
#include <iostream> #include <stdio.h> using namespace std; struct T { int l,r,add,color; }tree[100010*4]; int color1; void pushup(int k) { tree[k].color=tree[k<<1].color|tree[k<<1|1].color; } void creat(int l,int r,int k) { tree[k].l=l; tree[k].r=r; tree[k].add=0; tree[k].color=1; if(l==r) return ; int mid=(r+l)>>1; creat(l,mid,k<<1); creat(mid+1,r,k<<1|1); } void pushdown(int k) { int x=k*2; tree[x].add=1; tree[x+1].add=1; tree[x].color=tree[k].color; tree[x+1].color=tree[k].color; tree[k].add=0; } void Search(int l,int r,int color,int k) { if(tree[k].l>r||tree[k].r<l) return ; if(l<=tree[k].l&&r>=tree[k].r) { tree[k].color=color; tree[k].add=1; return ; } if(tree[k].add) pushdown(k); int mid=(tree[k].r+tree[k].l)>>1; if(r<=mid) Search(l,r,color,k<<1); else if(l>mid) Search(l,r,color,k<<1|1); else { Search(l,mid,color,k<<1); Search(mid+1,r,color,k<<1|1); } pushup(k); } void p(int l,int r,int k) { if(tree[k].l>r||tree[k].r<l) return ; if(l<=tree[k].l&&r>=tree[k].r) { color1|=tree[k].color; return; } if(tree[k].add) pushdown(k); int mid=(tree[k].r+tree[k].l)>>1; if(r<=mid) p(l,r,k<<1); else if(l>mid) p(l,r,k<<1|1); else { p(l,mid,k<<1); p(mid+1,r,k<<1|1); } } void swap(int &a,int &b) { int t=a;a=b;b=t; } int main() { int n,t,o,color,r,l; scanf("%d%d%d",&n,&t,&o); char str[5]; creat(1,n,1); while(o--) { scanf("%s",str); if(str[0]==‘C‘) { scanf("%d%d%d",&l,&r,&color); if(l>r) swap(l,r); Search(l,r,1<<(color-1),1); } else { scanf("%d%d",&l,&r); if(l>r) swap(l,r); color1=0; p(l,r,1); int ans=0; while(color1) { if(color1&1) ans++; color1>>=1; } printf("%d\n",ans); } } return 0; }
原文：http://www.cnblogs.com/yuanbo123/p/4887880.html