UOJ Logo

NOI.AC

1S 512MB

#775. c

Statistics

Alice 和 Bob 正在玩一个游戏。

具体来说,这个游戏是这样的,给定一个数列,从 Alice 开始,两个人轮流操作,每次操作可以从数列的头部或者尾部删去一个数字,当这个数列满足一定条件的时候,最后一次操作的人获胜。如果一开始就满足条件,则认为 Bob 获胜。

条件有的时候是单调不下降有的时候是单调,这会变化。

现在有一个长度为 $n$ 的数列,两个人在上面玩了 $m$ 次游戏,每次他们选定一个区间 $[l,r]$ 作为游戏的场地。他们想知道如果两个人都采用最优策略,那么谁会获得胜利。

输入格式

第一行两个整数,第一个整数 $n$ 表示序列的长度,第二个整数 $type$,如果为 1 则表示胜利条件是单调不下降,如果为 2 则是单调。

接下来一行 $n$ 个整数,第 i 个整数表示 $a_i$。

接下来一个整数 $m$,表示游戏次数。

接下来 $m$ 行,每行两个整数 $l_i,r_i$ 表示区间。

输出格式

一共 $m$ 行,每行一个字符串,如果 Alice 必胜则输出“Alice”,否则输出“Bob”。

样例数据

输入样例一

4 2
1 5 3 4
3
1 2
1 3
1 4

输出样例一

Bob
Alice
Bob

数据规模与约定

本题采用捆绑测试

对于 20 分的数据,$n,m\le 5$;

对于 40 分的数据,$n,m\le 1000$;

对于另外 30 分的数据,$type=1$;

对于所有数据,满足 $3\le n,m\le 10^6,0\le a_i\le 10^9,1\le l_i\le r_i\le n$。

时间限制:$1\text{s}$

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