「Daily OI Round 1」Xor

Luogu

IDLGP9595

Time1000ms

Memory512MB

DifficultyP5

线段树洛谷原创O2优化分治位运算

给定一个长度为 $n$ 的序列，一共有 $q$ 次询问，每次询问给定正整数 $x$，然后依次执行以下操作： - 把序列中所有数异或上 $x$。 - 求长度最大的区间 $[l,r]$（$l,r$ 是非负整数）满足区间中的每个整数在序列中出现，区间的长度定义为 $r-l+1$。 **注意，在每个询问过后序列是发生变化的。** **几个需要说明的地方：** 1. “区间”指的是数的区间，比如区间 $[1,3]$ 中的整数有 $1,2,3$，与序列无关。 2. “序列”指的是修改后的序列，同时不包括之前的序列。 ## Input 第一行两个正整数 $n,q$ 表示序列长度和询问个数。第二行 $n$ 个正整数 $a_i$ 表示一开始的序列。接下来 $q$ 行，每行一个正整数 $x$ 表示一个询问。 ## Output 输出 $q$ 行，一行一个整数表示每个询问的答案。 [samples] ## Note ### **样例解释** 对于第一组样例，序列初始是 $\{1,2,3,4,5\}$，第一次询问给定 $x=1$，则异或后的序列为 $\{0,3,2,5,4\}$。区间 $[2,5]$ 中的每个整数 $2,3,4,5$ 都在这个序列中，这是满足条件的最大区间，所以答案为 $5-2+1=4$。 ### **数据范围** **本题开启捆绑测试。** | $\text{Subtask}$ | 分值 | $n,q\leq$ | $a_i\leq$ | $x\leq$ | | :----------: | :----------: | :----------: | :----------: | :----------: | | $0$ | $10$ | $10^3$ | $10^3$ | $10^3$ | | $1$ | $20$ | $5\times10^5$ | $10^3$ | $10^3$ | | $2$ | $10$ | $5\times10^5$ | $10^3$ | $5\times10^5$ | | $3$ | $60$ | $5\times10^5$ | $5\times10^5$ | $5\times10^5$ | 对于全部数据，保证：$1\leq n,q,a_i,x\leq 5\times10^5$。

Samples

Input #1

Output #1

4
5

Input #2

10 10
5 9 8 3 5 7 10 19 5 24
10
56
19
14
18
53
52
57
96
1000

Output #2

API Response (JSON)

{
  "problem": {
    "name": "「Daily OI Round 1」Xor",
    "description": {
      "content": "给定一个长度为 $n$ 的序列，一共有 $q$ 次询问，每次询问给定正整数 $x$，然后依次执行以下操作： - 把序列中所有数异或上 $x$。 - 求长度最大的区间 $[l,r]$（$l,r$ 是非负整数）满足区间中的每个整数在序列中出现，区间的长度定义为 $r-l+1$。 **注意，在每个询问过后序列是发生变化的。** **几个需要说明的地方：** 1. “区间”指的是数的区间，比如区间",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P5"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9595"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "给定一个长度为 $n$ 的序列，一共有 $q$ 次询问，每次询问给定正整数 $x$，然后依次执行以下操作：\n\n- 把序列中所有数异或上 $x$。\n- 求长度最大的区间 $[l,r]$（$l,r$ 是非负整数）满足区间中的每个整数在序列中出现，区间的长度定义为 $r-l+1$。\n\n**注意，在每个询问过后序列是发生变化的。**\n\n**几个需要说明的地方：**\n\n1. “区间”指的是数的区间，比如区间...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments