CF665B Shopping

题目描述

小 $W$​​ 的商店开始了线上购物,线下提货的服务。商店有 $k$​​ 个商品(编号 $1$ 到 $k$), $n$ 个用户使用了这项服务。每个用户的订单都包含 $m$ 个商品,并在线付费,以 $a_{ij}$ 表示第 $i$ 个用户的订单中第 $j$ 个商品的编号。所有的商品是排成一排的,在小 $W$ 收到第 $i$ 件商品时,他会从前向后找所有的商品 $a_{ij}$ ( $1\le j\le m$ ),令 $pos(x)$ 表示该用户需要的编号为 $x$ 的商品,此时在序列中的位置。小 $W$ 需要 $pos(a_{i1})+pos(a_{i2})+...+pos(a_{im})$ 为第 $i$ 个客户服务的时间。当小 $W$ 访问第 $x$ 个元素时,他会将新的存货放到最前面,并将位置为 $x$ 的元素移除,因此,此序列是在不断更新的。你需要算出小 $W$​ 需要的时间。假设市场上有无尽的存货。

输入格式

第一行包含三个整数 $n$ , $m$ 和 $k$ ( $1\le n,k\le 100,1\le m\le k$ ) 。第二行包含 $k$ 个正整数 $p_1,p_2,...,p_k$ ( $1\le p_i\le k$ ) 。接下来的 $n$​​​ 行,每行包含 $m$​​​ 个正整数 $ a_{ij} $​​​ ( $1\le a_{ij}\le k$​​​​​ ) 。

输出格式

仅一行,输出一个整数 $t$​ ,即小 $W$​ 需要的时间。 #### 样例解释: 顾客 $1$ 想要 $1$ 号和 $5$号商品 。$pos(1)=3$ ,所以新的顺序是: $[1,3,4,2,5]$ 。$ pos(5)=5 $ ,所以新的顺序是: $[5,1,3,4,2]$ 。第一个顾客需要的时间为 $3+5=8$ 。顾客 $2$ 想要 $3$ 号和 $1$ 号商品。$pos(3)=3$ ,所以新的顺序是: $[3,5,1,4,2]$ 。$ pos(1)=3 $ ,所以新的顺序是: $ [1,3,5,4,2] $ 。第二个顾客需要的时间为 $3+3=6$ 。总时间是 $8+6=14$ 。在形式上,在队列里, $pos(x)$ 是 $x$​​​ 的指针。

说明/提示

Customer $ 1 $ wants the items $ 1 $ and $ 5 $ . $ pos(1)=3 $ , so the new positions are: $ [1,3,4,2,5] $ . $ pos(5)=5 $ , so the new positions are: $ [5,1,3,4,2] $ . Time taken for the first customer is $ 3+5=8 $ . Customer $ 2 $ wants the items $ 3 $ and $ 1 $ . $ pos(3)=3 $ , so the new positions are: $ [3,5,1,4,2] $ . $ pos(1)=3 $ , so the new positions are: $ [1,3,5,4,2] $ . Time taken for the second customer is $ 3+3=6 $ . Total time is $ 8+6=14 $ . Formally $ pos(x) $ is the index of $ x $ in the current row.