hdu 4638 Group

http://acm.hdu.edu.cn/showproblem.php?pid=4638
题意:给定一个序列,序列由1-N个元素全排列而成,求任意区间连续的段数。例如序列2,3,5,6,9就是三段(2, 3) (5, 6)(9)。
思路:增加一个元素,如果它两边的元素都出现了,那么段数-1(相当于把两段连接起来合并成了一段),如果两边元素都没有出现,那么段数+1.反过来,减少一个元素时,如果两边元素都出现了,俺么段数+1(相当于把完整的一段断开成两段),如果两边元素都没有出现,那么段数-1.操作可以O(1)完成。。。上莫队。 因为id大小最大才100000,所以判断某个元素是否出现开一个100000大小的布尔数组即可(我竟然傻逼得去用set….然后华丽丽得TLE了2333)

选区_019

 

作者: CrazyKK

ex-ACMer@hust,researcher@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz