杂题刷刷刷
一句话题解
有很多题想法很巧妙，但实在懒得码了 ，特此记录一下
函数的魔法
题目
对于数x，两种操作：\(x=(x*x*x+x*x) mod 233\)，\(x=(x*x*x-x*x) mod 233\)，求最少的操作次数将x变成y
题解
可达矩阵
求出233*233的可达矩阵\(A^1\),预处理出\(A^1 \sim A^{233}\) （最多计算233次），然后每次遍历233个矩阵就行
老瞎眼 pk 小鲜肉
题目
q次询问，询问[L,R]内最短异或和为0的区间
题解
没有实际操作，但感觉可以离线询问 莫队或者线段树，题解都是线段树就介绍线段树吧，比较保险
首先预处理O(n)求出a[i]作为区间右端点时最近的左端点 \(left[i]\)（map存一下之前相同值的位置，相减再更新就行），离线询问，按照右端点从小到大排序，每次把每个询问区间右端点R之前的值都插入到线段树中，将每个a[i]的长度更新到 \([1,left[i])\)
总结
似乎离线排序询问，再按照右端点排序，然后把右端点前的值进行线段树更新是一个比较常见的套路，至少遇到过两次了，事不过三，下次碰到绝对不能没有思路了
小阳的贝壳
题目
长度为n的数组，3种操作：
- \([l,r]\) 操作：+x
- \([l,r]\) 询问：\(max(abs(a[i+1]-a[i]))\)
- \([l,r]\) 询问：最大公约数
题解
线段树
虽然我是队伍里的数据结构手，但数据结构真的实在太难学了，变化层出不穷，大部分都得靠赛前的积累，赛中大概率是想不出来的，这道题用的是 将数组先化为差分数组，再建树
解决：
-
单点修改，差分数组的常规操作
-
区间询问，差分数组更好做了
-
\(gcd(a,b)=gcd(a,a-b)\) ，\(gcd(a_l,a_{l+1},…,a_r)=gcd(a_l,a_{l+1}-a_l,…,a_r-a_{r-1})\)
所以\(gcd(a_l,gcd_b)\)就是题目的解，\(gcd_b\)就是差分数组的gcd，\(a_l\)是\(\sum_{i=1}^l b_i\) ，所以可以维护一个sum
维护的有三个：sum，abs，gcd就够了，单点更新+区间询问
