[ROI 2017] 排序幻觉 (Day 1)

Luogu

IDLGP10650

Time2000ms

Memory512MB

DifficultyP4

贪心2017O2优化位运算ROI（俄罗斯）

给定长度为 $n$ 的整数数列 $a$，如果一个整数 $b$ 满足： $$ (a_1 \operatorname{xor} b) \le (a_2 \operatorname{xor} b) \le \dots \le (a_n \operatorname{xor} b) $$ 则称 $b$ 是 $a$ 数列的**幻数**。接下来有 $q$ 次修改，每次修改一个数 $a_{u_i}$ 为整数 $k_i$，每次修改都会对后面的询问产生影响。你需要求出第一次修改前以及每次修改后这个数列的最小的幻数是多少，特别的，如果不存在幻数请输出 $-1$。 ## Input 第一行一个整数 $n$ 表示数列长度。第二行 $n$ 个整数表示整数数列 $a$。第三行一个整数 $q$ 表示询问次数。接下来 $q$ 行每行两个整数 $u_i,k_i$，表示将 $a_{u_i}$ 修改为 $k_i$。 ## Output 共 $(q+1)$ 行，每行一个整数表示当前数列最小的幻数，如果没有幻数请输出 $-1$。 [samples] ## Note #### 【数据范围】 | 子任务编号 | 分值 | $1 \le n \le$ | $1 \le q \le $ | $0 \le a_i,k_i \le$ | | :----------: | :----------: | :----------: | :----------: | :----------: | | $1$ | $30$ | $500$ | $500$ | $2^9$ | | $2$ | $29$ | $10^3$ | $10^3$ | $2^{30}$ | | $3$ | $21$ | $10^5$ | $10^5$ | $2^{30}$ | | $4$ | $30$ | $10^6$ | $10^6$ | $2^{30}$ |

Samples

Input #1

Output #1

API Response (JSON)

{
  "problem": {
    "name": "[ROI 2017] 排序幻觉 (Day 1)",
    "description": {
      "content": "给定长度为 $n$ 的整数数列 $a$，如果一个整数 $b$ 满足： $$ (a_1 \\operatorname{xor} b) \\le (a_2 \\operatorname{xor} b) \\le \\dots \\le (a_n \\operatorname{xor} b) $$ 则称 $b$ 是 $a$ 数列的**幻数**。 接下来有 $q$ 次修改，每次修改一个数 $a_{u_i}$ 为整",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P4"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10650"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "给定长度为 $n$ 的整数数列 $a$，如果一个整数 $b$ 满足：\n\n$$\n(a_1 \\operatorname{xor} b) \\le (a_2 \\operatorname{xor} b) \\le \\dots \\le (a_n \\operatorname{xor} b)\n$$\n\n则称 $b$ 是 $a$ 数列的**幻数**。\n\n接下来有 $q$ 次修改，每次修改一个数 $a_{u_i}$ 为整...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments