洛谷 P3792 由乃与大母神原型和偶像崇拜
Problem
糖果屋的故事讲的就是韩赛尔和格雷特被继母赶出家里，因为没饭吃了，然后进了森林发现了一个糖果屋，里面有个女巫，专门吃小孩子
然而如果我们仔细想想这个故事，会发现它没有那么简单
比如说，女巫真的是吃小孩子吗？如果女巫是个善良的老婆婆，无偿救助在森林里面困住的小孩子呢？
还有就是当韩赛尔和格雷特杀死了女巫，回到家中发现她们的继母也死了
这是否意味着她们实际上杀死的是她们的继母？
所以这个故事本质上讲的是她们杀了她们的母亲，也就是打败了大母神
很多神话故事里面都有打败大母神的情节
你看到这里也许已经觉得由乃精神不正常了
然而由乃自从不小心##了自己的##后早就不正常了
由乃研究了很久大母神原型，但是仍然一脸懵逼
于是就出数据结构题骗钱去了
由乃：给你一个序列，每次询问一个区间是否是值域连续段
zzy：你把题意说详细点
由乃：就是说不能有重复数字，比如1 2 2 3就不行，然后4 2 3 1就可以
yql：sb分块
ddd：sb bitset
由乃：woc你们好树链啊，我。。我带修
zzq：#######sb题
由乃：我就是要出原题
给你一个长为\(n\)的序列\(a\)
每次两个操作：
- 修改\(x\)位置的值为\(y\)
- 查询区间\([l,r]\)否可以重排为值域上连续的一段
如果可以，输出“damushen”
否则输出“yuanxing”
对于\(100\%\)的数据，\(n,m \le 500000\)
初始值的值域小于\(2.5\times 10^7\)，修改操作的\(y\)小于等于\(n\)。
Solution
没有想到什么正解(其实是我不会证)，但是可以用区间\(hash\)的思想。
请问，给你一段数字的某些特征信息，如何得之，它是不是连续值域段？
既然是值域连续段，那么首先就要值域等于其极差+1：
这里我们需要维护\(max\)和\(min\).
然后呢，这一段当然是个公差为1的等差数列，当然满足等差数列的求和公式：
- \(sum=(min+max)*(max-min+1)/2\)
这里我们要维护\(sum\).
再然后呢，是不是还有点不放心？我们再维护一个区间平方和(记为\(pow2\)好了)。这里要先知道，\(\sum_{i=1}^ni^2=\frac n6\times(n+1)\times(2\times n+1)\).这是一个前缀和的形式，使用的时候差分即可。
\[pow2=\frac{max}{6}\times(max+1)\times(2\times max+1)-\frac{min-1}{6}\times min\times(2\times min-1)
\]
到这里，已经可以AC这道题啦！但是如果还是不放心，可以再维护一个立方和(记为\(cub\))。使用公式\(\sum_{i=1}^ni^3=(\sum_{i=1}^ni)^2=\frac{(1+n)^2\times n^2}4\).同上差分即可。
欸？这个数字这么大，会不会溢出？
我这里用\(\text{unsigned long long}\)自然溢出。当然您也可以取模（但是有点慢）。
注意，在模意义下就不能用除法了。但是可以将除法移到等式的另一边去就变成了乘法，可以愉快的比较啦！
Code
/**************************************************************
* Problem: 3792
* Author: Vanilla_chan
* Date: 20210321
* E-Mail: Vanilla_chan@outlook.com
**************************************************************/
#include
#include
#include
#include
#include
#include
#include
如果不要立方和的判断的话可以稳过。
加上立方和，稍有些不稳定（或者说是洛谷评测姬不稳定？）。