Y. Sneetches and Speeches 1

Codeforces

IDCFY

Time15000ms

Memory1024MB

Difficulty—

English · Original

Chinese · Translation

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.

本题与另外两题的唯一区别是：本题仅包含类型 1 的查询！ Sneetches 又回到了海滩上，伴随着伟大的 Sylvester McMonkey McBean！第 $i$ 只 Sneetch 腹部有 $a_i$ 颗星星（$0 lt.eq a_i lt.eq 1$）。和往常一样，许多形如 $[l... r]$ 的 Sneetch 区间会通过 Sylvester 的异或-1 机器。形式化地说，经过一次操作后，对于 $l$ 到 $r$（含）之间的所有位置，该位置的 Sneetch 腹部有星星，当且仅当它在进入机器前没有星星。你需要在每一步知道所有腹部类型相同的最长连续 Sneetch 区间长度。很简单，对吧？但等等！还有一个重要的细节尚未解决：我们在海滩上！伟大的演说家德摩斯梯尼在海滩上练习他的演讲。德摩斯梯尼正在发表一篇鼓舞人心的演讲，有时会激发以下行为，共进行 $q$ 次操作： 1. 执行常规操作：让位置在 $[l..r]$ 的 Sneetch 通过机器。$l lt.eq r$ 2. 类型 2 的查询不会出现在本题中。 3. 类型 3 的查询也不会出现。每次操作后，Sylvester 都需要你报告腹部星星数量相同的最长连续 Sneetch 区间的长度。第一行包含两个整数：$n$ 和 $q$，分别表示 Sneetch 的数量和查询的数量。$1 lt.eq n, q lt.eq 3 * 10^5$ 第二行包含一个长度为 $n$ 的由 0 和 1 组成的字符串。第 $i$ 个字符表示第 $i$ 只 Sneetch 腹部初始的星星数量。接下来 $q$ 行，每行格式为 $t$ $l$ $r$，其中 $t$ 始终为 1（本题中），表示题面中描述的查询类型，且 $1 lt.eq l lt.eq r lt.eq n$。请输出 $q$ 行，每行一个整数：每次查询后腹部类型相同的最长连续 Sneetch 区间的长度。本题灵感来源于 Matt Fontaine 原创的题目 Sneetches。原题仅包含类型 1 的查询，本质上与本题最简单版本相同。 ## Input 第一行包含两个整数：$n$ 和 $q$，分别表示 Sneetch 的数量和查询的数量。$1 lt.eq n, q lt.eq 3 * 10^5$。第二行包含一个长度为 $n$ 的由 0 和 1 组成的字符串。第 $i$ 个字符表示第 $i$ 只 Sneetch 腹部初始的星星数量。接下来 $q$ 行，每行格式为 $t$ $l$ $r$，其中 $t$ 始终为 1（本题中），表示题面中描述的查询类型，且 $1 lt.eq l lt.eq r lt.eq n$。 ## Output 请输出 $q$ 行，每行一个整数：每次查询后腹部类型相同的最长连续 Sneetch 区间的长度。 [samples] ## Note 本题灵感来源于 Matt Fontaine 原创的题目 Sneetches。原题仅包含类型 1 的查询，本质上与本题最简单版本相同。

**Definitions** Let $ n, q \in \mathbb{Z}^+ $ be 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 \leq n, q \leq 3 \times 10^5 $ 2. For each query $ j \in \{1, \dots, q\} $: - Operation type $ t_j = 1 $ - Range $ 1 \leq l_j \leq r_j \leq n $ **Operation** For each query $ j $, update $ A $ by flipping all bits in the range $ [l_j, r_j] $: $$ a_i \leftarrow 1 - a_i \quad \text{for all } i \in \{l_j, \dots, r_j\} $$ **Objective** After each query, compute the length of the longest contiguous subsequence of identical elements in $ A $: $$ \max_{1 \leq i \leq j \leq 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": "CFY"
  },
  "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": "本题与另外两题的唯一区别是：本题仅包含类型 1 的查询！\n\nSneetches 又回到了海滩上，伴随着伟大的 Sylvester McMonkey McBean！第 $i$ 只 Sneetch 腹部有 $a_i$ 颗星星（$0 lt.eq a_i lt.eq 1$）。和往常一样，许多形如 $[l... r]$ 的 Sneetch 区间会通过 Sylvester 的异或-1 机器。形式化地说，经过一...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n, q \\in \\mathbb{Z}^+ $ be 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 sta...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments