Y. Sneetches and Speeches 1

Codeforces

IDCF10278Y

Time15000ms

Memory1024MB

Difficulty—

English · Original

Formal · Original

The only difference between this problem and the other two is that this problem ONLY HAS QUERIES OF TYPE 1! The sneetches are back on the beaches, with the great Sylvester McMonkey McBean! The $i$th sneetch has $a_i$ stars on his belly ($0 <= a_i <= 1$). Just like normal, many [$l... r$] ranges of sneetches will go through Sylvesters xor-with-1-inator. Formally, after an operation, for all positions between $l$ and $r$ inclusive, the sneetch at that position will have a star on his belly after if and only if he didn't have a star on his belly immediately before walking through the machine. You need to know the largest continuous range of sneetches that all have the same type of belly at each step. Easy stuff, right? But wait! There is a very important detail still unaddressed: we are on a beach! And the great orator Demosthenes practices his speeches on a beach. Demosthenes is giving an inspiring speech which may at times incite the following behavior, doing one of the three things $q$ times: 1. Do the usual operation: make the sneetches in positions $[ l.. r ]$ go through the machine. $l <= r$ 2. Queries of type 2 will not appear in this problem. 3. Queries of type 3 will not appear either. After each operation, Sylvester needs you to report the size of the largest continuous range of sneetches that have the same number of stars on their belly. The first line will contain two integers: $n$ and $q$ representing the number of sneetches and the number of queries. $1 <= n, q <= 3 * 10^5$ The second line will contain a string of 0s and 1s of length $n$. The $i$th character represents the number of stars on the $i$th sneech's belly initially. $q$ lines follow, each of the form $t$ $l$ $r$ where $t$ is always 1 [for this problem] representing the query type as described in the statement, and $1 <= l <= r <= n$. Print $q$ lines, each with a single integer: the length of the longest run of sneetches with the same belly type after each query. This problem was inspired by the problem Sneetches, originally written by Matt Fontaine. The original problem only had queries of type 1, and is essentially the same as this easiest version. ## Input The first line will contain two integers: $n$ and $q$ representing the number of sneetches and the number of queries. $1 <= n, q <= 3 * 10^5$The second line will contain a string of 0s and 1s of length $n$. The $i$th character represents the number of stars on the $i$th sneech's belly initially.$q$ lines follow, each of the form $t$ $l$ $r$ where $t$ is always 1 [for this problem] representing the query type as described in the statement, and $1 <= l <= r <= n$. ## Output Print $q$ lines, each with a single integer: the length of the longest run of sneetches with the same belly type after each query. [samples] ## Note This problem was inspired by the problem Sneetches, originally written by Matt Fontaine. The original problem only had queries of type 1, and is essentially the same as this easiest version.

**Definitions** Let $ n, q \in \mathbb{Z}^+ $ denote the number of sneetches and queries, respectively. Let $ A = (a_1, a_2, \dots, a_n) \in \{0,1\}^n $ be the initial binary sequence representing star counts on sneetches. **Constraints** 1. $ 1 \le n, q \le 3 \cdot 10^5 $ 2. For each query $ j \in \{1, \dots, q\} $: - Operation type $ t_j = 1 $ - Range $ 1 \le l_j \le r_j \le n $ **Operation** For each query $ j $, update $ A $ by flipping all bits in range $ [l_j, r_j] $: $$ a_i \leftarrow 1 - a_i \quad \text{for all } i \in [l_j, r_j] $$ **Objective** After each update, compute the length of the longest contiguous subsequence of identical elements in $ A $: $$ \max_{1 \le i \le j \le n} \left\{ j - i + 1 \;\middle|\; a_i = a_{i+1} = \dots = a_j \right\} $$

API Response (JSON)

{
  "problem": {
    "name": "Y. Sneetches and Speeches 1",
    "description": {
      "content": "The only difference between this problem and the other two is that this problem ONLY HAS QUERIES OF TYPE 1! The sneetches are back on the beaches, with the great Sylvester McMonkey McBean! The $i$th ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 15000,
      "memory_limit": 1048576
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10278Y"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "The only difference between this problem and the other two is that this problem ONLY HAS QUERIES OF TYPE 1!\n\nThe sneetches are back on the beaches, with the great Sylvester McMonkey McBean! The $i$th ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n, q \\in \\mathbb{Z}^+ $ denote the number of sneetches and queries, respectively.  \nLet $ A = (a_1, a_2, \\dots, a_n) \\in \\{0,1\\}^n $ be the initial binary sequence representing...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments