毒瘤题目选集

连续自然数

给定一个长度为n的正整数数序列v

一共m个操作

操作分为两种

0 p x//把v[p]的值改为x

1 l r//查询v[l~r]是否可以组成一个连续数列(不一定是排好序的，例如v={2,3,5,4,6,8,6}.,v[2~5]排序后是3 4 5 6，是一个连续数列)

n,m<=1e5

这题的思路很简单(毒瘤)

用一个线段树维护区间最大值，最小值，区间和，区间平方和

其实就是哈希思想

哈希就是把非固定长度的信息压缩成固定长度的信息，与其说是一种算法，不如说是一种思想

在这道题里面，就是把区间信息压缩成4个整数

假设一段数是连续数列，那么可以根据最大值，最小值，区间长度求出对应的和，平方和。与线段树维护的信息比较，如果不符合，那么一定不是连续数列

如果求出的区间和与平方和与线段树维护的信息一致，那么一定是连续数列。。。吗？

反例:  1 5 3 4 5 2 7 12 9 10 11 12 14

虽然有可能被hack，但这就是哈希，牺牲一点准确率来换取时间

除了维护平方和，也可以维护立方和，四次方和，也可以用自己想到的蛇皮方式哈希，防止被hack。维护的信息越多，被hack的概率就越小

为避免高精，可以对一个大质数取模(比如长者的生日)，当然，也可以自然溢出

关于计算连续自然数的平方和，由于数据规模较小，可以直接暴力或者打表

如果数据规模大，则需要自己现推，也可以问度娘

对n²求和，得到的前n项和数列S_n一定是一个“三次函数”

可以用待定系数法去推，设S_n=an³+bn²+cn+d

代入S₁,S₂,S₃,S₄解出a,b,c,d即可

前n项的高次幂和的推导同理

毒瘤题目选集

原文：https://www.cnblogs.com/LMXZ/p/12098326.html