题目分享I

题意:2*n的地面,q次操作,每次操作将地面翻转,若该地是地面那翻转就成熔岩,如果是熔岩那翻转就成地面,熔岩人不能走,问人是否能从1,1走到2,n ps1,12,n不会在翻转的范围内,n,q1e5

分析:显然如果有1,k2,k2,k+12,k-1同时为岩浆,则这条路不通,其实完全可以拿个cnt记录一下,但我看了一眼n1e5,直接写的线段树,一样能过,线段树数组存的是2,1~2,n中总共能构成岩浆墙的个数,可能会重复统计如1,k2,k-12,k都会加一次,1,k1,k+1都会在2,k加一次,不过不影响,因为我们只要有一堵墙就通不过行,剩下的就是一些情况的讨论,也很容易写出来。

代码:

原文地址:https://www.cnblogs.com/lin4xu/p/12655667.html