当前没有测试数据。

题目描述

定义： 第六分块

这是一个数据结构问题。

给定整数 $n,m$ ，以及长度 $n$ 的序列 $a_1,\dots,a_n$ ，共 $m$ 次操作。

每次操作可以是 $1,l,r,x$ 表示将 $a_l,a_{l+1},\dots,a_r$ 的值增加 $x$，或 $2,l,r$ 表示查询 $a_l,a_{l+1},\dots,a_r$ 的最大子段和（即在序列中选取相邻的若干个（可以是 0 个）元素求和的最大值）。

要求 $1\le n\le 10^5,\;1\le m\le 2\times 10^5,\; 1\le l\le r\le n,\; |x|\le 10^{6}$ ，初始情况下 $|a_i|\le 10^{12}$ ，所有数值为整数。

输入格式为依次输入 $n,m,a_1,\dots,a_n$ ，然后依次输入每个操作。

输出格式为对每个操作 $2,l,r$ 输出一个整数表示答案。

这个问题存在时间复杂度为 $O((n+m)\sqrt n)$ 的算法。

定义： (max,+)矩阵乘法

$a,b,c$ 分别是 $n_1\times n_2,\;n_2\times n_3,\;n_1\times n_3$ 规模的由 $[0,1000]$ 范围内的整数构成的矩阵，满足：

$c_{i,k}=\mathop\max\limits_{j=1}^{n_2}a_{i,j}+b_{j,k}$ 。

$a,b$ 矩阵中的元素在范围内独立均匀随机选取。

输入格式为依次输入 $n_1,n_2,n_3$ ，然后依次输入 $a$ 和 $b$ 矩阵。

输出格式为输出 $c$ 矩阵。

输入（输出）一个 $A\times B$ 规模的矩阵 $v$ 时，需要对 $i=1,\dots,A$ 依次输入（输出）$v_{i,1},\dots,v_{i,B}$ 。

你需要解决的问题

你需要编写一个程序，这个程序的输入为空，输出是一个由 指令 构成的程序，这个程序用于求解 (max,+)矩阵乘法 （需要按输入格式读若干个整数，最后按输出格式写若干个整数），且可以调用一次对 第六分块 的求解（对应的指令是特殊函数调用3，需要先按输入格式写若干个整数表示问题描述，调用后按输出格式读若干个整数得到答案）和若干次读写整数（对应的指令是特殊函数调用1,2）。

下发的库 （std.cpp）可以简化生成指令的过程，你可以基于下发的库编写程序。

下发的 模拟器 （chk.cpp）可以执行由指令构成的程序，并给出得分。

模拟器的编译运行方式可以参考下发的 makefile 。

评分方式

如果你的程序不能正常结束，或输出的指令格式错误，或输出行数超过1024，或输出的一行中超过1024个字符，则不能得到任何分数。

输出的指令构成的程序格式正确时，模拟器将对输出的程序进行评测。

输出的程序将被执行4次，依次对应 $n_1=n_2=n_3=50,100,150,200$ 。如果某次执行出现运行时错误（例如），则本题得0分；否则每次执行如果输出了正确的答案并正常结束，则可以得到 $25\left(\min(1,\max(0,2-\frac{M}{M_0}))\cdot\min(1,\max(0,2-\frac{T}{T_0}))\right)$ 的分数。总分为每次执行的分数之和。

其中 $M$ 为内存访问次数，$T$ 为指令执行条数，在 指令和模拟器 一节定义。

$M_0=150000$

$T_0=3000000$

指令和模拟器

以下简单介绍评测用的模拟器支持的指令，更详细的指令行为可以查看模拟器的源代码。

内存模型和计算代价统计：

可以读写的内存被表示为由int64_t整数组成的数组 M ，大小为 $2^{24}$ ，初值为0；

指针 S 初始值为 M ，可能被 call 和 ret 指令修改；

指令的操作数表示为 M[S[<Int32>]] 或 S[<Int32>] ，用于读写内存；

指令不保存在 M 中，不能读写。

模拟器统计的计算代价包括 指令执行条数 和 内存访问次数。

一条指令（不包括 <Label>: ）被执行时， 指令执行条数增加1 ，指令中出现的每个 M[S[<Int>]] 导致 内存访问次数增加1 。

模拟器从第一条指令开始执行，执行 exit 后结束执行。

指令默认顺序执行，但对于指令说明中要求跳转的情况，执行完当前指令后调整到相应位置继续执行。

指令中需要用到以下语法元素：

语法元素	说明
<A>	可以是 M[S[<Int>]] 或 S[<Int>] ，表示指令中需要读写的数据的来源
<UOP>	可以是 - !
<BOP>	可以是 `+ - * / % ^ &
<Label>	64位有符号整数常数，十进制，表示可以跳转到的标签
<Int>	64位有符号整数常数，十进制
<Int32>	32位有符号整数常数，十进制

支持的指令如下（需要严格满足描述的语法格式，不允许出现空格等）：

指令	说明
<A>=<A>	赋值，读取右边的 <A> 写到左边的 <A>
<A>=<UOP><A>	一元运算，语义和c++对int64_t的相应运算相同，运算结果写到左边的 <A>
<A>=<A><BOP><A>	二元运算，语义和c++对int64_t的相应运算相同，运算结果写到左边的 <A>
<A>=<Int>	赋值为常数
<A>=&S[<Int>]	取地址，相当于计算 S-M+<Int> 保存到 <A>
if <A> goto <Label>	条件跳转，如果 <A> 非零则跳转到 <Label>
goto <Label>	无条件跳转到 <Label>
ret	跳转到 S[0] 保存的指令地址，将 S 修改为 M+S[1]
call <Label> <Int>	保存下一条指令的地址到 S[<Int>] ，保存 S-M 到 S[<Int>+1] ，将 S 修改为 S+<Int> ，跳转到 <Label>
exit	结束执行
ncall <Int> <A>	特殊函数调用，<Int> 表示特殊函数的类型，可能读写 <A>
<Label>:	标签，同个标签只能出现一次，不计入指令执行条数，用于表示跳转到的指令地址

特殊函数调用的规定：

<Int>	<A>	说明
1	读的整数的地址	读一个整数
2	写的整数	写一个整数
3	占位	只能调用一次，功能在题目描述中指定

输入输出模型：

输入输出被保存在一个初始为空的由整数组成的队列中。

特殊函数1从队列开头中取出一个整数，作为读取的结果；

特殊函数2将待写的整数放到队列末尾；

特殊函数3按指定输入输出格式调用特殊函数1,2读写整数。

使用下发的库生成指令

为了方便地生成指令，你可以使用下发的基于宏定义的库作为你提交的源代码的一部分，编译运行后可以输出生成的指令到标准输出。

<Type> 可以为 Int 表示int64_t，或者 Ptr<T> 表示类型 T 的指针，或者 Array<T,n> 表示类型 T 的大小 n 的数组。要求 T 是 <Type> 。

在表达式中， Int 之间可以使用二元运算符 + - * / % ^ & | << >> < <= > >= == != += -= *= /= %= ^= &= |= <<= >>= 和一元运算符 + - ! ，计算结果的表达式类型为 Int。

Ptr<T> 或 Array<T,n> 和 Int 之间可以使用二元运算符 + - ，计算结果的类型为 Ptr<T>。

Ptr<T> 或 Array<T,n> 可以使用一元运算符 * ，计算结果的类型为 T 。

表达式中可以出现数组访问运算符 <Expr>[<Expr>] ，要求左边为 Array<T,n> 或 Ptr<T> ，右边为 Int ，计算结果的类型为 T。

表达式中可以出现整数常量，可以被隐式转化为 Int 处理。

表达式中可以使用 () 改变运算符优先级。

表达式中可以出现类型转化 <Type>(<Expr>) ，仅限于 Array<T,n> 转为 Ptr<T> 或同个类型内的转化，以及 T 转为 Ptr<T> 表示c++中的 &。

表达式中可以出现赋值 <Expr>=<Expr> ，赋值时需要满足右侧类型能转化为左侧类型。

<Expr> 是表达式，只能包含整数或类型为某种 <Type> 的变量，变量的作用域规则和c++相同。

If(<Expr>) ... End 类似于c++中的if语句。

If(<Expr>) ... Else ... End 对应于c++中的if-else语句。

While(<Expr>) ... End 对应于c++中的while语句。

For(A,B,C) ... End 对应于c++中的for语句，其中 A,B,C为 <Expr> 。

Break; Continue; Return; 对应c++中相应的关键字。

<Expr>; 用于计算表达式，并处理表达式中可能出现的赋值。

<Type> x; 或 <Type> x=<Expr>; 用于在栈上定义变量。特别地，如果 <Expr> 的形式为 <Expr>[<Expr>] 或 <Expr> ，则 x 是右侧表达式的引用，而不是一个新的变量。

Func(name,args) ... End 用于定义无返回值的函数，args 为参数（可以为空，或包含形如 <Type> x; 的若干个定义），从第一个被定义的函数开始执行。函数定义不能嵌套，参数类型必须是 Int 或 Ptr<T>，语句必须出现在函数定义内。

Read(<Expr>); ，Write(<Expr>); ，Solve(); 分别表示特殊函数调用1,2,3。

未说明的用法可能能通过编译，但不一定能正确翻译为指令。

框架没有进行过多的优化，因此生成的指令可能有较高的指令执行条数。内存访问次数对应于形如 <Expr>[<Expr>] 或 *<Expr> 且类型不是数组的表达式的执行次数。