POJ 2777——线段树Lazy的重要性
POJ 2777 Count Color ——线段树Lazy的重要性
原题
链接:http://poj.org/problem?id=2777
Count Color
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 59087 Accepted: 17651
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.
There is a very long board with length L centimeter, L is a positive integer, so we can evenly divide the board into L segments, and they are labeled by 1, 2, ... L from left to right, each is 1 centimeter long. Now we have to color the board - one segment with only one color. We can do following two operations on the board:
- "C A B C" Color the board from segment A to segment B with color C.
- "P A B" Output the number of different colors painted between segment A and segment B (including).
In our daily life, we have very few words to describe a color (red, green, blue, yellow…), so you may assume that the total number of different colors T is very small. To make it simple, we express the names of colors as color 1, color 2, ... color T. At the beginning, the board was painted in color 1. Now the rest of problem is left to your.
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
思路
- 题目大意
一开始我们有一段长为L的序列,其上每个数都为1,之后我们要处理o个操作,一种是将一个区间全部修改为另一个数,另一种是给我们一个区间,要求我们算出这个区间内有多少种不同的数,每个数的值小于30
思路
- 1.一看区间问题,首先想到了线段树
- 2.发现种类数量不符合区间加法,但是我想到了set去重
- 3.但是又想到这个去重,会让复杂度变成约 \(O(o*L*log_2n)\), 这对于1e5量级的L与o是绝对不可以的
- 不过又发现每个数最大为30,那便想到了用二进制来表示一个区间内有多少种数——第几位为1表示这个区间内存在几,而最终我们拆分这个二进制数,统计1的个数就能得出答案。区间合并的时候,用 “或|” 就可以完美地将两个区间的信息合并而不用担心去重的问题。
- 还要注意每次区间操作时,先检查左右端点值,保证l <= r以免被坑
- 1.一看区间问题,首先想到了线段树
线段树code:
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <set>
using namespace std;
long long ff[400005];
int n, t, oo;
long long qu(int o, int l, int r, int x, int y)
{
if (l >= x && r <= y)
{
return ff[o];
}
int mid = (l + r) >> 1;
long long ans1 = 0;
long long ans2 = 0;
if (x <= mid)
{
ans1 = qu(o << 1, l, mid, x, y);
}
if (y > mid)
{
ans2 = qu(o << 1 | 1, mid + 1, r, x, y);
}
return ans2 | ans1;
}
void ch(int o, int l, int r, int x, int y, int v)
{
if (l == r)
{
ff[o] = (1 << (v - 1));
return;
}
int mid = (l + r) >> 1;
if (x <= mid)
{
ch(o << 1, l, mid, x, y, v);
}
if (y > mid)
{
ch(o << 1 | 1, mid + 1, r, x, y, v);
}
ff[o] = ff[o << 1] | ff[o << 1 | 1];
}
int main()
{
scanf("%d%d%d", &n, &t, &oo);
for (int i = 1; i <= 4 * n; ++i)
{
ff[i] = 1;
}
while (oo--)
{
char cc;
scanf("\n%c", &cc);
if (cc == 'C')
{
int ll, rr, tt;
scanf("%d%d%d", &ll, &rr, &tt);
if (ll > rr)
{
int tt = rr;
rr = ll;
ll = tt;
}
ch(1, 1, n, ll, rr, tt);
}
else
{
int ll, rr;
scanf("%d%d", &ll, &rr);
if (ll > rr)
{
int tt = rr;
rr = ll;
ll = tt;
}
long long cco = qu(1, 1, n, ll, rr);
int co = 0;
while (cco)
{
if (cco & 1)
{
++co;
}
cco >>= 1;
}
printf("%d\n", co);
}
}
return 0;
}
这结束了吗?
我一开始感到一阵不解,因为计算次数最多是 o*t 约等于 3e6 的量级,不过看这复杂度,,很是危险
好吧缺了些东西,这就是线段树的lazy标记,因为我们没有设置lazy标记,所以导致冗余计算很多,lazy标记的加入也较为简单,新开4*L的数组空间,在修改操作的区间包含当前区间时,进行标记,并且在其他操作之前进行下放即可,这一操作可以减少大量的计算,是一种不可缺少的优化
AC代码
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <set>
using namespace std;
int ff[400005], ad[400005];
int n, t, oo;
void pd(int o)
{
ad[o << 1] = ad[o];
ad[o << 1 | 1] = ad[o];
ff[o << 1] = ad[o];
ff[o << 1 | 1] = ad[o];
ad[o] = 0;
}
int qu(int o, int l, int r, int x, int y)
{
if (l >= x && r <= y)
{
return ff[o];
}
if (ad[o])
{
pd(o);
}
int mid = (l + r) >> 1;
int ans1 = 0;
int ans2 = 0;
if (x <= mid)
{
ans1 = qu(o << 1, l, mid, x, y);
}
if (y > mid)
{
ans2 = qu(o << 1 | 1, mid + 1, r, x, y);
}
return ans2 | ans1;
}
void ch(int o, int l, int r, int x, int y, int v)
{
if (l >= x && y >= r)
{
ff[o] = (1 << (v - 1));
ad[o] = (1 << (v - 1));
return;
}
if (ad[o])
{
pd(o);
}
int mid = (l + r) >> 1;
if (x <= mid)
{
ch(o << 1, l, mid, x, y, v);
}
if (y > mid)
{
ch(o << 1 | 1, mid + 1, r, x, y, v);
}
ff[o] = ff[o << 1] | ff[o << 1 | 1];
}
int main()
{
scanf("%d%d%d", &n, &t, &oo);
for (int i = 1; i <= 4 * n; ++i)
{
ff[i] = 1;
}
while (oo--)
{
char cc;
scanf("\n%c", &cc);
if (cc == 'C')
{
int ll, rr, tt;
scanf("%d%d%d", &ll, &rr, &tt);
if (ll > rr)
{
int tt = rr;
rr = ll;
ll = tt;
}
ch(1, 1, n, ll, rr, tt);
}
else
{
int ll, rr;
scanf("%d%d", &ll, &rr);
if (ll > rr)
{
int tt = rr;
rr = ll;
ll = tt;
}
int cco = qu(1, 1, n, ll, rr);
int co = 0;
while (cco)
{
if (cco & 1)
{
++co;
}
cco >>= 1;
}
printf("%d\n", co);
}
}
return 0;
}
数据结构在可行的范围内能优化就要优化,不能抱有侥幸心理而增加自己的WA,用线段树处理区间修改类问题时,一定要考虑能否用标记来优化。
最新文章
- 移动端页面去掉click点击 背景色变化
- 在VS2010 下编译 cocos2d-x-2.1.4
- Mysql服务器相互作用的通讯协议包括TCP/IP,Socket,共享内存,命名管道
- mapreduce job提交流程源码级分析(三)
- 【web安全】第二弹:XSS攻防中的复合编码问题
- 【HDU1538】A Puzzle for Pirates(经典的海盗问题)
- WPF技术触屏上的应用系列(二): 嵌入百度地图、API调用及结合本地数据库在地图上进行自定义标点的实现
- T4模板使用技巧
- HTML5中的WebSocket
- ATM取款小项目
- 浅析Spring事务传播行为和隔离级别
- BEM 中文翻译
- c++ primer 笔记 (二)
- this语句的第三、四点
- Linux 下查看某个进程运行的堆栈信息
- HTML5 桌面提示
- 秒杀多线程第七篇 经典线程同步 互斥量Mutex
- svn 配置仓库
- ERROR 1093 (HY000): You can&#39;t specify target table &#39;test&#39; for update in FROM clause
- HTTP Cache怎样计算Age