在线儿童游戏,小花仙蜘蛛丝,李占双
count colortime limit: 1000ms | memory limit: 65536k | |
total submissions: 40404 | accepted: 12188 |
description
chosen problem solving and program design as an optional course, you are required to solve all kinds of problems. here, we get a new problem.input
first line of input contains l (1 <= l <= 100000), t (1 <= t <= 30) and o (1 <= o <= 100000). here o denotes the number of operations. following o lines, each contains "c a b c" or "p a b" (here a, b, c are integers, and a may be larger than b) as an operation defined previously.output
ouput results of the output operation in order, each line contains a number.sample input
2 2 4 c 1 1 2 p 1 2 c 2 2 2 p 1 2
sample output
2 1
source
poj monthly--2006.03.26,dodo#include #include #include #include #include #include #include #include #include #include using namespace std; const double eps = 1e-6; const double pi = acos(-1.0); const int inf = 0x3f3f3f3f; const int mod = 1000000007; #define ll long long #define cl(a,b) memset(a,b,sizeof(a)) #define maxn 100010 struct node { int l,r,s; } t[maxn<<2]; int l,o,t; int sum[33];//因为颜色数不多,可以用一个数组来装;1表示该区间有该颜色,0反之 void build(int l, int r, int i) { t[i].l = l; t[i].r = r; t[i].s = 1; if(l == r) return ; int mid = (l+r)>>1; build(l, mid, i<<1); build(mid+1, r, i<<1|1); } void update(int l, int r, int m, int i) { if(t[i].s == m) return ; if(t[i].l == l && t[i].r == r) { t[i].s = m; return ; } if(t[i].s != -1) { t[i<<1].s = t[i<<1|1].s = t[i].s; t[i].s = -1; } int mid = (t[i].l+t[i].r)>>1; if(l > mid) update(l, r, m, i<<1|1); else if(r <= mid) update(l, r, m, i<<1); else { update(l, mid, m, i<<1); update(mid+1, r, m, i<<1|1); } } void query(int l, int r, int i) { if(t[i].s != -1)//如果纯色把该颜色标记 { sum[t[i].s] = 1; return ; } else//否则继续查询子节点 { int mid = (t[i].l+t[i].r)>>1; if(l > mid) query(l, r, i<<1|1); else if(r <= mid) query(l, r, i<<1); else { query(l, mid, i<<1); query(mid+1, r, i<<1|1); } } } int main() { char ch; int a,b,c; while(scanf("%d%d%d",&l,&t,&o)==3) { build(1, l, 1); while(o--) { getchar(); scanf("%c",&ch); if(ch == 'c') { scanf("%d%d%d",&a,&b,&c); update(a, b, c, 1); } int ans = 0; if(ch == 'p') { cl(sum, 0);//每次查询之前清零 scanf("%d%d",&a,&b); query(a, b, 1); for(int i=1; i<=t; i++)//统计出现过的颜色数 if(sum[i]) ans++; printf("%d\n",ans); } } } return 0; }
如对本文有疑问,请在下面进行留言讨论,广大热心网友会与你互动!! 点击进行留言回复
如何在没有core文件的情况下用dmesg+addr2line定位段错误
用QT制作3D点云显示器——QtDataVisualization
网友评论