某島

… : "…アッカリ~ン . .. . " .. .
June 27, 2013

HDU 3397. Sequence operation

Brief description:

… lxhgww got a sequence contains n characters which are all ‘0’s or ‘1’s. We have five operations here:

    Change operations:

  • 0 a b: change all characters into ‘0’s in [a, b]. (區間賦值
  • 1 a b: change all characters into ‘1’s in [a, b]. (區間賦值
  • 2 a b: change all ‘0’s into ‘1’s and change all ‘1’s into ‘0’s in [a, b]. (區間取反
    Output operations:

  • 3 a b: output the number of ‘1’s in [a, b].
  • 4 a b: output the length of the longest continuous ‘1’ string in [a , b].

Analysis:

… 略)
。。單標記。。暴力 rev。。700ms+
。。雙標記。。1100ms+

External link: