PKU 2777 Count Color

2019-11-06 07:54:30

字体：大中小

来源：转载

供稿：网友

题目大意：

在一条直线上插入不同颜色的线段，看有多少段颜色相同的线段。（note:加入有大神嫌题目不够详细的话传送门：http://poj.org/PRoblem?id=2777）

输入输出格式：

给一个l（直线的长度。。直线有长度吗。。不管了。）,t（颜色的种类，尽管好像并没有什么用）,o（询问的次数） “C A B C”表示在区间A，B图上C颜色， “P A B” 表示询问

A，B区间有几种不同的颜色。

分析:

用线段树，插入线段的时候，如果访问的线段已标记，则拆分为三段来插入。(这一份没有用lazy标记）

代码：

#include <iostream>#include <cstdio>#include <queue>#include <string>#include <cmath>#include <cstring>#define N 100000using namespace std;int flag[N];int l,t,o,a,b,c,ans;char k;struct tree{ int l,r,cover;}tree[N];void build(int p,int l,int r){ tree[p].l=l; tree[p].r=r; int m=(l+r)/2; if (r-l>1) { build(p*2,l,m); build(p*2+1,l,r); }}void insert(int p,int a,int b,int c){ int m=(tree[p].l+tree[p].r)/2; printf("%d" ,l); if (tree[p].cover!=c) if (tree[p].l==a && tree[p].r==b) tree[p].cover=c; else { if (tree[p].cover>=0) { tree[p*2].cover=tree[p].cover; tree[p*2+1].cover=tree[p].cover; tree[p].cover=-1; } if (b<=m) insert(p*2,a,b,c); else if (a>=m) insert(p*2+1,a,b,c); else { insert(p*2,a,b,c); insert(p*2+1,a,b,c); } }}int count(int p,int a, int b){ if (tree[p].cover>=0) flag[tree[p].cover]=1; if (b-a>1) { count(p*2,a,(a+b)/2); count(p*2+1,(b+a)/2,b); }}int main(){ scanf("%d%d%d" ,&l,&t,&o); build(1,1,l); for (int i=1;i<=o;i++) { scanf("%c" ,&k); if (k=='C') { scanf("%d%d%d/n" ,&a,&b,&c); insert(1,a,b,c); } else { scanf("%d%d/n" ,&a,&b); memset(flag,0,sizeof(flag)); ans=0; count(1,a,b); for (int j=1;j<=l;j++) if (flag[j]==1) ans++; printf("%d/n" ,ans); printf("%c" ,k); } }}

上一篇：华为机试-字符串排序

下一篇：PCF8591 1602液晶显示

学习交流

索泰发布一款GTX 1070 Mini迷你版本:小机

索泰发布一款GTX 1070 Mini迷你版本:小机箱大爱...

热门图片

猜你喜欢的新闻

猜你喜欢的关注