Logo Infinity Online Judge

InfOJ

时间限制:8 s 空间限制:1024 MB

#199. Dynamic Predecessor Problem

Statistics

题目描述

本题是交互题。

有一个长度为 $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$。