#P11183. [ROIR 2018 Day2] 大数据处理

[ROIR 2018 Day2] 大数据处理

题目描述

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

某实验室正在研发一种能处理大规模数据的新型超级计算机。

这台超算的内存包含 2k2^k 个存储单元,依次编号为 02k1.0\ldots 2^k-1. 用内存段 [L,R][L,R] 表示编号 L≥LR≤R 的所有存储单元,该内存段的长度为 RL+1.R-L+1.

定义:如果内存段 [L,R][L,R] 的长度是 22 的整数次幂(不妨假设是 2i2^i),且 LL2i2^i 的整数倍,那么这个内存段是「正确的内存段」。

k=3,k=3, 则正确的内存段为 [0,7],[0,7], [0,3],[0,3], [4,7],[4,7], [0,1],[0,1], [2,3],[2,3], [4,5],[4,5], [6,7],[6,7], [0,0],[0,0], [1,1],[1,1], [2,2],[2,2], [3,3],[3,3], [4,4],[4,4], [5,5],[5,5], [6,6][6,6][7,7].[7,7].

现在,每个存储单元所存储的值均为 0. 你需要给每个存储单元赋值。简单起见,我们用游程编码的形式给出每个单元上的值。开头的 c1c_1 个单元中存储的值为 v1,v_1, 接下来 c2c_2 个单元中存储的的值为 v2,v_2, 以此类推,最后的 cnc_n 个单元中存储的值为 cn,c_n, 1vim.1≤v_i≤m.

举个例子,如果 k=3,k = 3, n=3,n = 3, m=2,m = 2, c={1,c = \{1, 2,2, 5},5\}, v={1,v = \{1, 2,2, 1},1\}, 那么内存将被赋值为 [1,[1, 2,2, 2,2, 1,1, 1,1, 1,1, 1,1, 1].1].

你只有一种方法给单元赋值:STORE([l,r],x).\mathtt{STORE}([l,r],x). 该函数表示将内存段 [l,r][l,r] 中所有单元全部赋值为 x.x. 注意,[l,r][l,r] 必须是合法的内存段。

试求至少需要多少次操作才能达成要求。

输入格式

第一行三个整数 k,n,mk,n,m
接下来的 nn 行,每行两个整数 ci,vic_i,v_i

输出格式

输出一行一个整数,表示至少的次数。

3 3 2
1 1
2 2
5 1
3

提示

样例解释

目标:[1,2,2,1,1,1,1,1][1, 2, 2, 1, 1, 1, 1, 1]

  • STORE([0,7],1),\mathtt{STORE}([0, 7], 1), 得到 [1,1,1,1,1,1,1,1];[1, 1, 1, 1, 1, 1, 1, 1];
  • STORE([1,1],2),\mathtt{STORE}([1, 1], 2), 得到 [1,2,1,1,1,1,1,1];[1, 2, 1, 1, 1, 1, 1, 1];
  • STORE([2,2],2),\mathtt{STORE}([2, 2], 2), 得到 [1,2,2,1,1,1,1,1].[1, 2, 2, 1, 1, 1, 1, 1].

数据范围

0k30,0 ≤ k ≤ 30, 1n105,1 ≤ n ≤ 10^5, 1m109.1 ≤ m ≤ 10^9.

子任务编号 分值 kk\le kk\le mm\le
1 15 33 88  88 
2  15  1919 1010
3 15
4 10 5050
5 15 1919
6 30