好毒瘤。为什么数据还有 000 和负数。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
T1
题意解析：给定一个长度为 nnn 的数组 AAA，你需要进行 nnn 次操作。每次操作给定四个数 opt,l,r,copt,l,r,copt,l,r,c。
* opt=0opt=0opt=0：请将 Al,...,ArA_l,...,A_rAl ,...,Ar 的值加上 ccc。
* opt=1opt=1opt=1：查询 ArA_rAr 的值。
考虑分块。
考虑转化成差分数组，BiB_iBi 记录 Ai−Ai−1A_i-A_{i-1}Ai −Ai−1 的值。这样操作 000 转化成将 BlB_lBl 加 ccc，Br+1B_{r+1}Br+1 减 ccc；操作 111 转化成 ∑j=1rBj\sum_{j=1}^r B_j∑j=1r Bj 。
我们将数组分成 O(n)O(\sqrt n)O(n ) 块，查询时我们可以分成两边的散块和中间的整块查询。
我们修改时 O(n)O(\sqrt n)O(n ) 暴力维护每一块的和（可以 O(1)O(1)O(1) 但是没必要），这样查询时中间每一个整块就可以 O(1)O(1)O(1) 了，又因为整块数量不超过 O(n)O(\sqrt n)O(n )，所以查询整块就是 O(n)O(\sqrt n)O(n ) 的；散块直接 O(n)O(\sqrt n)O(n ) 暴力查即可。
时间复杂度：O(nn)O(n\sqrt n)O(nn )。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
T4
题意解析：给定一个长度为 nnn 的数组 AAA，你需要进行 nnn 次操作。每次操作给定四个数 opt,l,r,copt,l,r,copt,l,r,c。
* opt=0opt=0opt=0：请将 Al,...,ArA_l,...,A_rAl ,...,Ar 的值加上 ccc。
* opt=1opt=1opt=1：查询 (∑j=lrAj)mod (c+1)(\sum_{j=l}^r A_j)\mod (c+1)(∑j=lr Aj )mod(c+1) 的值。此时保证 c≥0c\ge 0c≥0。
T1 加强版。
考虑分块。
我们修改的时候也可以分成整块和散块。
对于整块，我们可以直接修改该块的和并打上 lazytag，等到它要分成散块时再下放；对于散块，先下放 lazytag，然后暴力修改。
查询的时候整块依旧查和就行，散块就要先下放 lazytag 然后再暴力找 AiA_iAi 。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
T2
题意解析：给定一个长度为 nnn 的数组 AAA，你需要进行 nnn 次操作。每次操作给定四个数 opt,l,r,copt,l,r,copt,l,r,c。
* opt=0opt=0opt=0：请将 Al,...,ArA_l,...,A_rAl ,...,Ar 的值加上 ccc。
* opt=1opt=1opt=1：查询在 Al,...,ArA_l,...,A_rAl ,...,Ar 中，有多少个数小于 c2c^2c2。
考虑分块。
先思考不带修改怎么做。
我们把 AAA 数组分为 O(n)O(\sqrt n)O(n ) 个块，我们将每个块内的元素从小到大排序。查询时我们对整块进行 lower_bound，两边的小块暴力查找即可。O(nnlogn)O(n\sqrt{n}\log n)O(nn logn)。
注意到修改整块对整块的顺序不影响，不需要重新排序，直接打 lazytag 即可，查询带 lazytag 查就行。散块先下放 lazytag（其实不下放也行），然后暴力修改 AiA_iAi ，最后 sort 排序即可。
注意查询的常数比修改的常数大很多，所以需要调整块长。经测试在块长为 250250250 时可以跑进 3.57s3.57s3.57s。
时间复杂度：O(nnlogn)O(n\sqrt n\log n)O(nn logn)。
Bonus：尝试以 O(nnlogn)O(n\sqrt{n\log n})O(nnlogn ) 的时间复杂度通过该题。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
T3
和 T2 差不多，不讲。代码见我的板子。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
T5
题意解析：给定一个长度为 nnn 的数组 AAA，你需要进行 nnn 次操作。每次操作给定三个数 opt,l,ropt,l,ropt,l,r。
* opt=0opt=0opt=0：请将 Al,...,ArA_l,...,A_rAl ,...,Ar 的值都变为原先的值的根号。
* opt=1opt=1opt=1：查询 (∑j=lrAj)(\sum_{j=l}^r A_j)(∑j=lr Aj ) 的值。
考虑分块。
首先我们注意到每个 AiA_iAi 被开 loglogAi\log\log A_iloglogAi 次根就变为 111 了，所以其实能影响答案的单点改也就那么几次，后面的修改就相当于木棍木棍的中间两个字了。
思考如何判断某些修改是无效的。
显然对于一个块，AiA_iAi 均小于等于 111，即 ∑j=lrAi≤len\sum_{j=l}^r A_i\le len∑j=lr Ai ≤len，那这个块的所有修改就都是无效的。我们遇到无效的修改就跳过，有效的就直接暴力修。显然，根据刚才的结论，每个块最多只会被修改 O(loglogV)O(\log\log V)O(loglogV) 次。对于散块，那还说啥了，直接暴力即可。
查询时和 T1 一样查就行。
时间复杂度：O(nn+nloglogV)O(n\sqrt n+n\log\log V)O(nn +nloglogV)。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
T6
题意解析：给定一个初始长度为 nnn 的数组 AAA，你需要进行 nnn 次操作。每次操作给定？个数 opt,...opt,...opt,...。
* opt=0opt=0opt=0：给定三个数 opt,l,ropt,l,ropt,l,r，请在 AlA_lAl 前面插入一个数 rrr。
* opt=1opt=1opt=1：给定两个数 opt,copt,copt,c，查询 AcA_cAc 的值。
数据随机生成。
考虑分块。
我们把 AAA 数组分成 O(n)O(\sqrt n)O(n ) 块，每块是一个 vector，记录块内的元素。修改先找大块，如果 AlA_lAl 位于这个块，就直接 insert；不在的话继续往下找。查询和插入同理。由于数据随机生成，所以这种做法每个块期望长度依然是 O(n)O(\sqrt n)O(n )，时间复杂度也是 O(nn)O(n\sqrt n)O(nn )。
但是，注意到如果块长占比过大，那么随机选点落到它的概率就更大，这样它的块长也更大……所以，为了减少这种恶性循环的危害，建议将块长调小一点。
时间复杂度：O(nn)O(n\sqrt n)O(nn )。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
T7
和 T4 一样，不写。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
T8
题意解析：给定一个长度为 nnn 的数组 AAA，你需要进行 nnn 次操作。每次操作给定三个数 l,r,cl,r,cl,r,c。
请查询 Al,...,ArA_l,...,A_rAl ,...,Ar 内一个数内元素为 ccc 的个数，并将区间所有元素改为 ccc。
考虑分块。
我们把 AAA 数组分成 n\sqrt nn 个块，设置 lazytag 为当前块内所有元素为一个相同的值 kkk（如果不同则 k=−1k=-1k=−1），这样如果遇到 k≠−1k\not= -1k=−1 的块就可以直接改 lazytag 了，否则就暴力。显然这样如果不算一开始的元素的话，单次操作是 O(n)O(\sqrt n)O(n ) 的。而一开始的元素也只会查询 O(n)O(n)O(n) 次，所以总时间复杂度还是 O(nn)O(n\sqrt n)O(nn )。
时间复杂度：O(nn)O(n\sqrt n)O(nn )。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
T9
题意解析：给定一个长度为 nnn 的数组 AAA，你需要进行 nnn 次操作。每次操作给定两个数 l,rl,rl,r。
请查询 Al,...,ArA_l,...,A_rAl ,...,Ar 中的最小众数。
考虑分块。
首先我们可以 O(n)O(n)O(n) 递推求出 [i,i],[i,i+1],[i,i+2],...,[i,n][i,i],[i,i+1],[i,i+2],...,[i,n][i,i],[i,i+1],[i,i+2],...,[i,n] 的最小众数。所以我们可以 O(nn)O(n\sqrt n)O(nn ) 求出 [n,n][\sqrt n,\sqrt n][n ,n ]，[n,2n],[n,3n],...,[n,n],[2n,2n],[2n,3n],...,[n,n][\sqrt n,2\sqrt n],[\sqrt n,3\sqrt n],...,[\sqrt n,n],[2\sqrt
n,2\sqrt n],[2\sqrt n,3\sqrt n],...,[n,n][n ,2n ],[n ,3n ],...,[n ,n],[2n ,2n ],[2n ,3n ],...,[n,n] 的最小众数。记录下来。
然后我们 O(nn)O(n\sqrt n)O(nn ) 预处理每个块每个元素的个数，然后做前缀和。
每一个查询还是分成整块和散块。整块的话直接查表。
我们枚举散块的每一个元素，显然不超过 2n2\sqrt n2n 个。我们可以通过查表找到整块内它们出现的个数，然后暴力统计散块内出现的个数，更新答案。
时间复杂度：O(nn)O(n\sqrt n)O(nn )。
