这题挺好的…
给定一个序列,支持
- 单点修改
- 询问一个区间从大到小排序后是否是给定公差的等差数列
如果一个区间是一个公差是$k$的等差数列,那么这个区间会满足:
- 最大值和最小值之差为(区间长度-1)$\times$公差
- 区间内所有相邻数之间的差$gcd$为公差的倍数
- 当公差不为0时,区间里没有相等的数
1条件:线段树维护最大值最小值即可。
2条件:维护这个区间的所有相邻两数差的$gcd$即可。具体而言,设这个标记为$gd$,在从左右儿子$push~up$到当前结点时,考虑每个节点维护这个区间最左和最右的元素,然后相减求$gcd$再与两区间的$gd$值的$gcd$即可。
3条件:因为强制在线,所以不能对数据($\leq 10^9$)离散化,于是只能用个$map$搞下。考虑对于每种值开一个$set$,记录这个值所有的下标,记$a_i$为原序列,$pre_i$为$i$这个位置与$a_i$相等的数在前面最大的位置,$nxt_i$为$i$这个位置与$a_i$相等的数在前面最小的位置,然后我们对一个区间询问有没有相同的数,就可以看作是在$pre$和$nxt$数组上这个区间里前者取最大值,后者取最小值,若这两个值在区间中,自然就证明了这个区间里有重复数字辣。
然而原题的出题人并没有考虑到条件3,也就是说,不写条件3的两棵线段树和那两个容器的版本造的数据,所以内存限制被出题人卡到$128MB$,我可能写的丑在bzoj被卡了内存,不过没写条件3的还是可以顺利地过的。写了条件3的版本本地写了个脚本也测$ac$了。不过应该是我写丑的原因,每棵线段树如果能写优到两倍点空间的话这题还是可以在$128MB$内过的。
条件1~2
条件1~3:容器+询问的常数,带起来就是$O(n\times 10logn)$了,常数有点大