题目描述

本题是交互题。

有一个长度为 $n$ 的 01 序列 $[a_1,a_2,\dots,a_n]$，初始时 $a_i=0$。

$q$ 次操作，每次操作为以下三种之一：

• assign：给出 $i,x$，将 $a_i$ 赋值为 $x$，$x\in \{0,1\}$。
• nxt：给出 $i$，求最小的 $j>i$ 使得 $a_j=1$，若不存在答案为 0。
• pre：给出 $i$，求最大的 $j\lt i$ 使得 $a_j=1$，若不存在答案为 0。

实现细节

你需要引用 trie.h。你需要实现以下函数：

• void init(int n)
• void assign(int i,int x)
• int pre(int i)
• int nxt(int i)

首先，交互器会调用 init(n)。$n$ 为 01 序列的长度。

然后交互器会调用 $q$ 次 assign,pre,nxt 函数，其意义与题目描述中相同。

• assign 操作中，有 $1\le i\le n,x\in \{0,1\}$。
• pre 操作中，有 $1\le i\le n+1$。
• nxt 操作中，有 $0\le i\le n$。

评分方式

首先交互题会受到和常规题相同的限制，如超时/超空间会导致得零分。在此基础上，你得到满分当且仅当所有 pre,nxt 操作的返回值均正确。

保证交互库占用时间不超过 $2.5$ 秒，占用空间不超过 $64\texttt{MB}$。这意味着你至少有 $5.5$ 秒可用时间，$960\texttt{MB}$ 可用空间。

子任务

• 子任务 1（$35$ 分）保证 $n=5\times 10^3,q\le 5\times 10^4$。
• 子任务 2（$65$ 分）保证 $n=2\times 10^8,q\le 5\times 10^7$。