大数据处理

译自 ROI 2018 Regional. Day2 T4. Обработка больших данных

某实验室正在研发一种能处理大规模数据的新型超级计算机。
这台超算的内存包含 $2^k$ 个存储单元，依次编号为 $0 \ldots 2^k-1.$ 用内存段[L,R]表示编号≥L且≤R的所有存储单元，该内存段的长度为R-L+1.
定义：如果内存段[L,R]的长度是2的整数次幂（不妨假设是 $2^i$ ），且L是 $2^i$ 的整数倍，那么这个内存段是「正确的内存段」。
若k=3,则正确的内存段为[0,7],[0,3],[4,7],[0,1],[2,3],[4,5],[6,7],[0,0],[1,1],[2,2],[3,3],[4,4],[5,5],[6,6]和[7,7].
现在，每个存储单元所存储的值均为0.你需要给每个存储单元赋值。简单起见，我们用游程编码的形式给出每个单元上的值。开头的 $c_1$ 个单元中存储的值为 $v_1,$ 接下来 $c_2$ 个单元中存储的的值为 $v_2,$ 以此类推，最后的 $c_n$ 个单元中存储的值为 $c_n,$ $1≤v_i≤m.$
举个例子，如果k=3,n=3,m=2,c= {1,2,5 },v= {1,2,1 },那么内存将被赋值为[1,2,2,1,1,1,1,1].
你只有一种方法给单元赋值： $\mathtt{STORE}([l,r],x).$ 该函数表示将内存段[l,r]中所有单元全部赋值为x.注意，[l,r]必须是合法的内存段。
试求至少需要多少次操作才能达成要求。

详情