首页 > 代码库 > poj2777( Count Color)
poj2777( Count Color)
题目地址：Count Color
题目大意：
给一个划分为L的线段染色，有两种操作，一种C操作 给定l，r区间染色为val。另一种操作P 查询l，r区间的颜色有多少种。
解题报告：
线段树，区间更新。
这题的lazy 表示该区间颜色种类，如果单色则为“1”，如果多色为”0“。tag 代表该区间的哪一种颜色。如果修改区间的颜色时，判断修改的颜色和该区间的颜色是否相同，相同的话就return，如果直接找到该区间，直接lazy赋值为”1“，tag 赋值为”v“，不用往下递归，因为该区间包含下面的子区间的单色，所以查询的时候，只需要看从根区间往下递归，只要遇到单色区间，就说明往下的子区间也就一定是该颜色。
代码：
1 #include <algorithm> 2 #include <iostream> 3 #include <sstream> 4 #include <cstdlib> 5 #include <cstring> 6 #include <cstdio> 7 #include <string> 8 #include <bitset> 9 #include <vector> 10 #include <queue> 11 #include <stack> 12 #include <cmath> 13 #include <list> 14 #include <map> 15 #include <set> 16 using namespace std; 17 /***************************************/ 18 #define ll long long 19 #define int64 __int64 20 /***************************************/ 21 const int INF = 0x7f7f7f7f; 22 const double eps = 1e-8; 23 const double PIE=acos(-1.0); 24 const int d1x[]= {0,-1,0,1}; 25 const int d1y[]= {-1,0,1,0}; 26 const int d2x[]= {0,-1,0,1}; 27 const int d2y[]= {1,0,-1,0}; 28 const int fx[]= {-1,-1,-1,0,0,1,1,1}; 29 const int fy[]= {-1,0,1,-1,1,-1,0,1}; 30 /***************************************/ 31 void openfile() 32 { 33 freopen("data.in","rb",stdin); 34 freopen("data.out","wb",stdout); 35 } 36 /**********************华丽丽的分割线,以上为模板部分*****************/ 37 const int M=100100; 38 39 struct tree 40 { 41 int left,right; 42 int lazy,tag; 43 } node[M*4]; 44 45 int cnt; 46 int p[31]; 47 void build__tree(int id,int l,int r) 48 { 49 int mid=(l+r)/2; 50 node[id].lazy=1; 51 node[id].tag=1; 52 node[id].left=l; 53 node[id].right=r; 54 if (l==r) 55 return ; 56 build__tree(id*2,l,mid); 57 build__tree(id*2+1,mid+1,r); 58 } 59 void updata(int id,int l,int r,int v) 60 { 61 int mid=(node[id].left+node[id].right)/2; 62 if (node[id].left==l&&node[id].right==r) 63 { 64 node[id].lazy=1; 65 node[id].tag=v; 66 return ; 67 } 68 if (node[id].tag==v&&node[id].lazy) 69 return ; 70 if (node[id].lazy) 71 { 72 node[id].lazy=0; 73 updata(id*2,node[id].left,mid,node[id].tag); 74 updata(id*2+1,mid+1,node[id].right,node[id].tag); 75 } 76 if (r<=mid) 77 updata(id*2,l,r,v); 78 else if (l>mid) 79 updata(id*2+1,l,r,v); 80 else 81 { 82 updata(id*2,l,mid,v); 83 updata(id*2+1,mid+1,r,v); 84 } 85 } 86 void query(int id,int l,int r) 87 { 88 int mid=(node[id].left+node[id].right)/2; 89 if (node[id].lazy) 90 { 91 p[node[id].tag]=1; 92 return; 93 } 94 if (r<=mid) 95 query(id*2,l,r); 96 else if (l>mid) 97 query(id*2+1,l,r); 98 else 99 {100 query(id*2,l,mid);101 query(id*2+1,mid+1,r);102 }103 }104 int main()105 {106 int l,t,o;107 while(scanf("%d%d%d",&l,&t,&o)!=EOF)108 {109 int i,j;110 build__tree(1,1,l);111 while(o--)112 {113 char c;114 int x,y,val;115 getchar();116 scanf("%c",&c);117 if (c==‘C‘)118 {119 scanf("%d%d%d",&x,&y,&val);120 if (x>y)121 swap(x,y);122 updata(1,x,y,val);123 }124 if (c==‘P‘)125 {126 cnt=0;127 memset(p,0,sizeof(p));128 scanf("%d%d",&x,&y);129 if (x>y)130 swap(x,y);131 query(1,x,y);132 for(int i=1;i<31;i++)133 if (p[i])134 cnt++;135 printf("%d\n",cnt);136 }137 }138 139 }140 return 0;141 }142 143 /*144 2 2 100145 C 1 1 2146 P 1 2147 C 2 2 2148 P 1 2149 C 2 2 2150 P 1 2151 C 1 1 2152 P 1 2153 C 1 2 2154 P 1 2155 C 1 2 1156 157 5 3 1000158 C 2 3 2159 C 2 4 3160 C 3 5 2161 C 2 3 1162 C 1 3 2163 P 1 5164 165 5 3 1000166 P 1 5167 C 2 3 2168 P 1 5169 C 2 4 3170 P 1 5171 C 3 5 2172 P 1 5173 C 2 3 1174 P 1 5175 C 1 3 2176 P 1 5177 C 4 4 3178 P 1 5179 */
poj2777( Count Color)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。