作业帮HDU的acm1199题总是WA,估计数组范围不够,这题数组应该开多少?All the input are less than 2^31-1.Problem DescriptionThere are infinite balls in a line (numbered 1 2 3 .),and initially all of them are paint black.Now Jim use a brush pa
来源：学生作业帮助网 编辑：作业帮 时间：2024/04/28 17:17:42
HDU的acm1199题总是WA,估计数组范围不够,这题数组应该开多少?All the input are less than 2^31-1.Problem DescriptionThere are infinite balls in a line (numbered 1 2 3 .),and initially all of them are paint black.Now Jim use a brush pa
HDU的acm1199题总是WA,估计数组范围不够,这题数组应该开多少?All the input are less than 2^31-1.
Problem Description
There are infinite balls in a line (numbered 1 2 3 .),and initially all of them are paint black.Now Jim use a brush paint the balls,every time give two integers a b and follow by a char 'w' or 'b','w' denotes the ball from a to b are painted white,'b' denotes that be painted black.You are ask to find the longest white ball sequence.
Input
First line is an integer N (
HDU的acm1199题总是WA,估计数组范围不够,这题数组应该开多少?All the input are less than 2^31-1.Problem DescriptionThere are infinite balls in a line (numbered 1 2 3 .),and initially all of them are paint black.Now Jim use a brush pa
题目说了,数据范围到2^31-1.但是显然我们开不了这么大的数组……再退一万步说,就算能开这么大的数组,用暴力算法,这个O(2000*2^31)的时间复杂度估计得算一个小时吧……
如果你是acm初学者；或者如果你不想搞acm只是想练一些题提高代码水平；或者如果你连二叉树都还写的不熟练：
请跳过这个题.
如果你有了一定的代码能力,如果你是要认真的搞acm,这个题就是必会的数据结构之一：线段树.请百度线段树的有关知识,一搜一大把.另外,由于这个数据范围实在太大,会涉及到数据离散化的知识.建议你先找一个不用离散化的普通线段树的题,过了之后再来搞这个题.
有问题欢迎追问.