Range Set Modifying Query

AtCoder

IDabc430_g

Time4000ms

Memory256MB

Difficulty—

There are $N$ sets $S_1, \ldots,S_N$. Initially, all sets are empty. You are given $Q$ queries in the following formats. Process them in order. * Type $1$: Given as `1 L R x`. For each $S_i$ satisfying $L \leq i \leq R$, add $x$. * Type $2$: Given as `2 L R x`. For each $S_i$ satisfying $L \leq i \leq R$, remove $x$. * Type $3$: Given as `3 L R`. Find the maximum number of elements among $S_i$ satisfying $L \leq i \leq R$, and the number of sets that achieve this maximum. ## Constraints * $1\leq N \leq 3\times 10^5$ * $1\leq Q \leq 3\times 10^5$ * For each query, $1 \leq L \leq R \leq N$. * For type $1,2$ queries, $1 \leq x \leq 60$. * All input values are integers. ## Input The input is given from Standard Input in the following format: $N$ $Q$ $\mathrm{query}_1$ $\vdots$ $\mathrm{query}_Q$ Here, $\mathrm{query}_i$ represents the $i$\-th query, and each is given in one of the following formats as shown in the problem statement: $1$ $L$ $R$ $x$ $2$ $L$ $R$ $x$ $3$ $L$ $R$ [samples]

Samples

Input #1

Output #1

2 1
1 2
2 1

*   Initially $(S_1,S_2,S_3,S_4)=(\lbrace\rbrace,\lbrace\rbrace,\lbrace\rbrace,\lbrace\rbrace)$.
*   The $1$\-st query adds $10$ to $S_1,S_2$, resulting in $(S_1,S_2,S_3,S_4)=(\lbrace 10\rbrace,\lbrace 10\rbrace,\lbrace\rbrace,\lbrace\rbrace)$.
*   The $2$\-nd query adds $20$ to $S_2,S_3,S_4$, resulting in $(S_1,S_2,S_3,S_4)=(\lbrace 10\rbrace,\lbrace 10,20\rbrace,\lbrace 20\rbrace,\lbrace 20\rbrace)$.
*   For the $3$\-rd query, the maximum number of elements among $S_1,S_2,S_3$ is $2$ achieved by $S_2$, so print `2 1`.
*   The $4$\-th query removes $20$ from $S_1,S_2$, resulting in $(S_1,S_2,S_3,S_4)=(\lbrace 10\rbrace,\lbrace 10\rbrace,\lbrace 20\rbrace,\lbrace 20\rbrace)$.
*   The $5$\-th query adds $10$ to $S_2,S_3$, resulting in $(S_1,S_2,S_3,S_4)=(\lbrace 10\rbrace,\lbrace 10\rbrace,\lbrace 10,20\rbrace,\lbrace 20\rbrace)$.
*   For the $6$\-th query, the maximum number of elements among $S_1,S_2$ is $1$ achieved by $S_1,S_2$, so print `1 2`.
*   For the $7$\-th query, the maximum number of elements among $S_1,S_2,S_3,S_4$ is $2$ achieved by $S_3$, so print `2 1`.

API Response (JSON)

{
  "problem": {
    "name": "Range Set Modifying Query",
    "description": {
      "content": "There are $N$ sets $S_1, \\ldots,S_N$. Initially, all sets are empty. You are given $Q$ queries in the following formats. Process them in order. *   Type $1$: Given as `1 L R x`. For each $S_i$ satisf",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 4000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "abc430_g"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "There are $N$ sets $S_1, \\ldots,S_N$. Initially, all sets are empty.\nYou are given $Q$ queries in the following formats. Process them in order.\n\n*   Type $1$: Given as `1 L R x`. For each $S_i$ satisf...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments