〚d83d〛叠高高

发表于 分类于 ， 本文字数： 2k

#题目背景

传说在古老的索维洛渡奥里斯帝国（*Sōwilō Dualis Empire），有一种被称为 “特图尔（Turtle）” 的神秘生物。

这种神秘生物，恐怕是古老的索维洛渡奥里斯帝国的记载，但却没有人知道这种神秘生物的存在，也没有人知道这种神秘生物是什么样的。

这种神秘生物，在那些派生出来的这种神秘生物中，最大的特点就是它们的身体都是由鳞片组成，这种身体的鳞片，组成了一个结构复杂的结构，可以称为 “贝贝龟”，这种结构的形状和长度，让这种神秘生物绝大多数都是没有意义的，因为这种神秘生物的身体结构，经常会变化。

显然，这种变化过于复杂，容易造成代码设计错误，这种错误可能会导致程序的混乱，或者导致程序无法正常运行。

所以，我们需要一种机制，可以让程序在运行期间动态的调整内存分配方式。

这个机制称为垃圾回收机制。

“特图尔（Turtle）” 存在于公元前约 6000 年左右，在这个时期，索维洛渡奥里斯帝国的统治者，就是现在的美国。

在美国，索维洛渡奥里斯帝国的首都是纽约，这座城市被称为 “奥里斯港”（Aolisi Harbor）。

这种神秘生物，在美国的大部分地区都是不可见的，但在美国的一些地区，这种神秘生物却可见。

所以，在这种环境下，我们需要把这种神秘生物的结构抽象出来，统一为一个抽象类，这样，可以让程序更加简单，更加易读。

这种统一的抽象类，就是 “贝贝龟”。

下面是一个组合的例子，这个例子用到了 “贝贝龟” 的身体结构，它可以形成一个 “贝贝龟” 的组合。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <iostream>
using namespace std;

class Turtle {
public:
    Turtle() {
        cout << "Turtle()" << endl;
    }
    virtual ~Turtle() {
        cout << "~Turtle()" << endl;
    }
};

class BeebiTurtle : public Turtle {
public:
    BeebiTurtle() {
        cout << "BeebiTurtle()" << endl;
    }
    virtual ~BeebiTurtle() {
        cout << "~BeebiTurtle()" << endl;
    }
};

class BeebiTurtleTail : public BeebiTurtle {
public:
    BeebiTurtleTail() {
        cout << "BeebiTurtleTail()" << endl;
    }
    virtual ~BeebiTurtleTail() {
        cout << "~BeebiTurtleTail()" << endl;
    }
};

class BeebiTurtleBody : public BeebiTurtle {
public:
    BeebiTurtleBody() {
        cout << "BeebiTurtleBody()" << endl;
    }
    virtual ~BeebiTurtleBody() {
        cout << "~BeebiTurtleBody()" << endl;
    }
};

class BeebiTurtleHead : public BeebiTurtle {
public:
    BeebiTurtleHead() {
        cout << "BeebiTurtleHead()" << endl;
    }
    virtual ~BeebiTurtleHead() {
        cout << "~BeebiTurtleHead()" << endl;
    }
};

class BeebiTurtleTailBody : public BeebiTurtleTail, public BeebiTurtleBody {
public:
    BeebiTurtleTailBody() {
        cout << "BeebiTurtleTailBody()" << endl;
    }
    virtual ~BeebiTurtleTailBody() {
        cout << "~BeebiTurtleTailBody()" << endl;
    }
};

int main() {
    BeebiTurtleTailBody beebi;
    return 0;
}

编译并运行程序，输出结果如下：

1
2
3
4
5
6
7
8
9
10
11
12
Turtle()
BeebiTurtle()
BeebiTurtleTail()
BeebiTurtleBody()
BeebiTurtleHead()
BeebiTurtleTailBody()
~BeebiTurtleTailBody()
~BeebiTurtleTail()
~BeebiTurtleHead()
~BeebiTurtleBody()
~BeebiTurtle()
~Turtle()

 \\ ~ \\

#题目描述

你用 Github Copilot 写完了题目背景，但是发现背景中的代码输出是

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Turtle()
BeebiTurtle()
BeebiTurtleTail()
Turtle()
BeebiTurtle()
BeebiTurtleBody()
BeebiTurtleTailBody()
~BeebiTurtleTailBody()
~BeebiTurtleBody()
~BeebiTurtle()
~Turtle()
~BeebiTurtleTail()
~BeebiTurtle()
~Turtle()

你看着这只稀碎的 “贝贝龟”，感到十分苦恼，于是你决定解决如下问题：

 \\ ~ \\

现在你有一个长度为 nn 的序列 (Ai)(A_i)，有 mm 次操作，分为以下 44 种：

  • 1 l r x：对于所有的 i∈[l,r]i\in[l,r]，令 AiA_i 加上 xx；

  • 2 l r x：对于所有的 i∈[l,r]i\in[l,r]，令 AiA_i 变为 xx；

  • 3 l r x：将区间 [l,r][l,r] 平移到从 [l+x,r+x][l+x,r+x]，剩余的元素在 相对顺序不变 的前提下，补充平移带来的空位，很容易知道序列长度不变。

  • 4 l r x：对于所有的 i∈[l,r]i\in[l,r]，令 AiA_i 变为 min⁡(Ai,x)\min(A_i,x)；

在每次操作后，你需要输出整个序列的不同前缀最大值个数。你只需要保证你的输出是小于 10910^9 的非负整数，且与答案的奇偶性相同即可。

出于某种原因，你需要将读入的 l,rl,r 异或当前的答案来得到真正的 l,rl,r。

#输入格式

第一行两个整数，表示 n,mn,m。

接下来一行 nn 个整数，表示序列 (Ai)(A_i)。

接下来 mm 行，每行一个操作，格式同题目描述。

#输出格式

在每次操作后，输出一行一个小于 10910^9 的非负整数，表示整个序列的不同前缀最大值个数。

#样例

样例 1, 2 的解释在 “数据范围与提示” 一节。

另外有五个样例。所有样例见下发文件，其中，后五个样例的数据的范围及性质分别对应五个 subtask。

#样例输入 1

1
2
3
4
5
6
7
8
8 6
1 2 3 5 6 8 9 11
1 11 0 -1
4 5 2 4
2 5 2 9
3 7 0 4
3 0 1 -5
3 0 6 0

#样例输出 1（仅供参考）

1
2
3
4
5
6
8
999999999
999999998
0
6
1

#样例输入 2

1
2
3
4
5
6
7
8
9
10
11
17 9
114 332 145 224 499 781 325 114 110 299 143 785 436 447 462 844 893
1 5 9 112
3 12 11 2
2 1 0 678
4 10 20 844
1 4 1 -42
2 5 1 996
4 1 6 737
3 5 6 15
4 5 10 446

#样例输出 2（仅供参考）

1
2
3
4
5
6
7
8
9
7
5
5
5
5
6
3
4
2

#数据范围与提示

#样例 1 解释

  • 在第一次操作前，序列为 1,2,3,5,6,8,9,111,2,3,5,6,8,9,11，故答案为 88。所以这次操作的 l,rl,r 分别为 3,83,8。

  • 在第二次操作前，序列为 1,2,2,4,5,7,8,101,2,2,4,5,7,8,10，故答案为 77。所以这次操作的 l,rl,r 分别为 2,52,5。

  • 在第三次操作前，序列为 1,2,2,4,4,7,8,101,2,2,4,4,7,8,10，故答案为 66。所以这次操作的 l,rl,r 分别为 3,43,4。

  • 在第四次操作前，序列为 1,2,9,9,4,7,8,101,2,9,9,4,7,8,10，故答案为 44。所以这次操作的 l,rl,r 分别为 3,43,4。

  • 在第五次操作前，序列为 1,2,4,7,8,10,9,91,2,4,7,8,10,9,9，故答案为 66。所以这次操作的 l,rl,r 分别为 6,76,7。

  • 在第六次操作前，序列为 10,9,1,2,4,7,8,910,9,1,2,4,7,8,9，故答案为 11。所以这次操作的 l,rl,r 分别为 1,71,7。

注意：你需要异或真正的答案才能得到实际操作的 l,rl,r。

#样例 2 解释

样例输出即为真正的答案，你可以自行解码得到所有操作。

#数据范围

保证任何时刻序列中的数字均为不超过 101810^{18} 的非负整数。

其他限制如下：

子任务编号 分值 n≤n\le m≤m\le 子任务依赖 特殊性质
11 1616 50005000 2×1042\times 10^4  ~  ~
22 2424 5×1045\times 10^4 2×1052\times 10^5  ~ 没有操作 3,43,4
33 2828 5×1045\times 10^4 2×1052\times 10^5 22 没有操作 44
44 2020 5×1045\times 10^4 2×1052\times 10^5  ~ 所有操作都满足 r=l+1r=l+1
55 1212 5×1045\times 10^4 2×1052\times 10^5 33  ~

#提示

本题正解 不是 随机化。

 \\ ~ \\

 \\ ~ \\

std 也支持优先队列和一些其他操作，分别是：查询元素是否存在、插入和删除元素、查询前驱和后继、查询集合里的最大值和最小值

std 称为垃圾回收机制。

std 每行一个整数，是单调递增的，权值为 x。

std and Aoki will play a game using this tree.

std 被至少一个弧覆盖的概率是多少？注意一条弧可以相互交叉或包含。

std 支持一种询问：给定节点 u 和参数 x，假如

std 是悬垂引用的右值向虚基类的基类向下转型时进行的直接初始化的重载决议推导出的显式指定类型或重载集失败时，被丢弃的编译类型

std 所反射的函数或拥有静态存储期的变量被 std::experimental::reflect::get_pointer<T> 的特化 odr 式使用，如同通过取指名该函数或变量的标识表达式的地址。

std 非常快，以至于它在时限的零分之一内通过了本题

std 解决了问题 〚d83d〛叠高高 (2022-02-11 10:12:21)

std is a way to take part in past contest, as close as possible to participation on time.

std 开始析构。

std 仅供学习参考使用。抄袭、复制题解，以达到刷 r█ting 值/AK 数量或　他目的的行为，在索维洛渡奥里斯帝国是严格禁止的。

std 需要一种机制，可以██在于公元前约 a_i 年左右，在　　子树内，就能得到一个森林。

std すべてのピー　をテ　ブルの上　置██．

std 进　 v2.█ 时代！

std 过　复　　容████　　　　计错误，这　错误　　　　　　　　██乱　　　██　　　　　　常　　██

std w█ █　　█　　█　　　n.████ ████.

std 为　应　　　　　　　求　　　　██　 █ █　　 　　显　　　　　　息　　　　　处。

st█ █　　　　　██　　　　　　█　　　█

█　　　　　　　　　　　　　█　　　　　　　　　　　　　　　　　　　██

█　　　　　　　　　　　　　　　　　　　　　█ 　　　　　　　　　　　　　　　　　██

pure virtual method called

terminate called without an active exception