← 返回题目列表

AtCoder · icpc2014summer_day4_h

H. 锦标赛

中文机器翻译题面 查看原题

问题陈述

今年,国家项目NGU球员权利锦标赛的时机终于到来。 地区锦标赛中,你可以投注全国锦标赛的参赛资格,双方将以$2^n$的队伍进行一对一淘汰赛制对决。

锦标赛积分榜的队伍编号为$0,\ldots,2^n-1$,从第一轮到$n$轮的对决顺序如下。

  1. 第一轮,队号$l和队号$l+1$的队伍对决。 $l \equiv 0 ~(\bmod~2)$)
  2. 在$i+1$轮($1 \le i < n$)中,队号在$l$至$l+2^i$之间且至第$i轮未输过一场比赛的队伍,$l指的是队伍号码在+2^i$至$l+2^{i+1}$之间且至第$i轮未输过任何比赛的队伍。 ($l \equiv 0~(\bmod~2^{i+1})$)

经过$n$回合后,每队的排名以$2^{n-(\text{该队获胜次数})}$确定。 请注意,这场比赛没有平局,因此参赛双方获胜,庄家输。

正式被选为区大会代表后,我们决定让经理去核查其他区比赛的成绩。 他们在这里的研究结果是“从经理那里收到的排名”。 为了更详细地解释“经理收到的排行榜”,它是一条长度为$2^n$的序列,顶点为$i$($0 \leq i \leq 2^n -1 $)显示队伍编号$i$的排名。

然而,经理给我的“排行榜”显示了大量相同的排名! 根据比赛规则,同一位置的大量玩家不可能被绑住。 因此,为了让“经理收到的排名”成为“一致的排名”,计算改变排名的最低球队数量,并告诉经理排名错误的程度。

“稳定排名”指的是因排名决定而产生的锦标赛可能产生的排名。


输入

输入包括“从经理那里收到的排名表”,其格式如下。

$n$ $m$
$a_0$ $a_1$ ... $a_m$
$b_0$ $b_1$ ... $b_{m-1}$
  • 第1行包含两个整数 $n,m$,其中 $2^n$ 表示“地区大会的参赛队伍数”,$m$ 表示“在‘从经理那里收到的排名表’中连续排名并列的区间数量”。
  • 第2行包含 $a_i(0 \le i \le m)$ 共 $m+1$ 个整数,每个 $a_i$ 表示“在‘从经理那里收到的排名表’中连续排名并列的区间的分界位置”。
  • 第3行包含 $b_i(0 \le i < m)$ 共 $m$ 个整数,每个 $2^{b_i}$ 表示“在‘从经理那里收到的排名表’中,队号在 $a_i$ 及以上且小于 $a_{i+1}$ 的队伍的排名”。

约束

  • $1 \le n \le 30$
  • $1 \le m \le 10{,}000$
  • $0=a_0 < a_1 < \cdots < a_{m-1} < a_m = 2^n$
  • $0 \le b_i \le n$

输出

输出1行,表示为了将“从经理那里收到的排名表”变为“无矛盾的排名表”所需修改排名的最少队伍数。


示例输入 1

1 1
0 2
1

样本输入 1 的输出

1

两支参赛队伍的“稳定排名”为{”チーム番号0のチームの順位","チーム番号1のチームの順位使用“}有两种方式:$\{1,2\}$和$\{2,1\}$。 要将排名$\{2,2\}$修改为“稳定排名”,必须将一队排名改为1。


示例输入 2

2 3
0 1 2 4
0 1 2

样本输入 2 的输出

2

示例输入 3

2 3
0 1 3 4
0 2 1

样本输入 3 的输出

0

示例输入 4

4 5
0 1 2 4 8 16
0 1 2 3 4

样本输入 4 的输出

10