UOJ Logo Universal Online Judge

UOJ

#327. 【UTR #3】去月球

统计

Scape和Mythological交流了玩几何冲刺的经验之后,Mythological非常高兴,又推荐给Scape一款游戏To the moon。

游戏中一位老人John的记忆被药物尘封,进行了解除尘封的仪式之后,Scape走入了他的记忆。

John的记忆中有一个唤做River女孩的身影,有着数不尽的纸兔子,有一个沙包,一只鸭嘴兽玩偶,一座灯塔。Scape被深深的打动了。

”我的鸭嘴兽和沙包又在哪里呢?” Scape这样想到,不禁幻想出Mythological决定给他送 $n$ 份礼物,其中第 $i$ 份的种类是 $a_i$。这些礼物按顺序排成一行。

她挑选礼物的方式很特别,她每次会选择两份种类相同的礼物,并且这对礼物满足它们之间没有尚未拿走的礼物,并将这对礼物拿走。

现在Scape给出了若干次询问,每次询问如果他送给她的是区间 $\left [L_i,R_i\right ]$ 之间的礼物,那么她最多能拿走多少份礼物。

任务

你需要编写两个函数/过程,以完成题目的任务:

  • init(n, m, a[], t);
    • 在程序最开始运行时会调用一次来完成初始化。
    • $n$ 表示 $a$ 的长度是 $n$,$m$ 表示 $a_i$ 的最大可能值,$a$ 数组的下标从 $1$ 开始,$t$ 表示子任务编号。
  • query(l, r);
    • 表示询问区间 $\left [L ,R\right ]$ 的答案 。
    • 保证 $L\leq R$。

实现细节

本题只支持 C/C++。

你只能提交一个源文件实现如上所述的 init 和 query 函数/过程,并且遵循下面的命名和接口。你需要包含头文件 mythological.h。

void init(int n, int m, int a[], int t);
int query(int l, int r);

如果有不清楚的地方,见样例及测评库下载,内附了样例程序

评测库大概需要占用$8\texttt{MB}$的内存和$100\texttt{ms}$的时间。

因为评测库使用了fread来进行快速读入,所以用命令行输入数据的选手需要在输入数据完毕后用"Ctrl+D"来输入EOF。

评测方式

评测系统将读入如下格式的输入数据:

  1. 第 $1$ 行:四个整数 $n,m,q,t$,分别是这组测试数据的大小,$a_i$ 的最大可能值,询问个数和子任务编号。
  2. 第 $2$ 行:$n$ 个整数,第 $i$ 个整数表示 $a_i$。
  3. 第 $2+i$ 行($1\le i\le q$):两个整数 $L_i,R_i$,表示询问的区间。

样例一

input

9 10 3 0
1 1 3 2 1 1 2 3 1
2 9
1 2
2 5

output

8
2
0

样例二

input

10 10 3 0
1 2 3 4 5 6 7 8 9 10
1 9
2 3
4 5

output

0
0
0

样例三

见样例及测评库下载。

限制与约定

对于所有数据,$1\le n\le 1\times 10^5$,$1\le m\le 1\times10^5$,$ q\leq 2\times 10^6$,$ L_i \le R_i$。

为了拿到每个子任务的分数,你必须通过所有他依赖的子任务。

子任务 分值 $n$ $q$ 其他性质 依赖的subtask
1 20 $\le 1000$ $\le 1000$
2 16 $\le 1\times 10^5$ $\le 1\times 10^5$ 每种权值最多出现两次 $1$
3 25 $\le 1\times 10^5$ $\le 1\times 10^5$ 询问的 $L,R$ 生成方式给出(见下) $1$
4 19 $\le 1\times 10^5$ $\le 1\times 10^5$ $1,2,3$
5 20 $\le 1\times 10^5$ $\le 2\times 10^6$ $1,2,3,4$

子任务3生成询问的方式如下:

定义 $$F_i=(2000i^2+629i+2333) \bmod n+1$$

则对所有的 $1\le i\le q$,有 $$L_i = \min\left\{F_{2i-1},F_{2i} \right\}$$ $$R_i = \max\left\{F_{2i-1},F_{2i} \right\}$$

交互式类型的题目怎么本地测试

时间限制:$2\texttt{s}$

空间限制:$512\texttt{MB}$

下载

样例数据下载