给定一个长为 (n) 的序列 (a_i) ，有 (m) 次操作：
- 单点修改
- 询问将区间中的数升序排序后是否是一个公差为 (k) 的等差数列
强制在线
(n, mleq3 imes10^5, 0leq a_i, kleq10^9)
线段树，hash
区间 ([l, r]) 所组成的等差数列首项为 (min{a_{lcdots r}}) ，末项为 (max{a_{lcdots r}}) ，公差为 (k)
可以考虑求出 ([l, r]) 和这个等差数列的hash值，接着对比即可
如果将区间和作为hash值，冲突率很高，可以考虑用每个数的平方作为hash值
设该等差数列首项为 (l) ，公差为 (k) ，项数为 (t)
则它的hash值为 $$displaystylesum_{a=0}t{(l+ak)2}$$
接着大力化式子
[egin{aligned}hash&=displaystylesum_{a=0}^t{l^2+2lak+a^2k^2}\&=(t+1)l^2+kdisplaystylesum_{a=0}^t{a^2k+2la}\&=(t+1)l^2+k(displaystylesum_{a=0}^t{a^2}+2lsum_{a=0}^ta)\&=(t+1)l^2+k(frac{t(t+1)(2t+1)}{6}+lt(t+1))end{aligned}
]
故可 (O(1)) 求出
此题还需要特判 (l=r) 及 (k=0) 的情况
由于我担心被卡，用了双模数，常数稍大 qaq
然而维护平方可以卡掉T_T，貌似维护三次方就吼辣？但式子化起来太麻烦了qaq
upd: 维护任意次方都会被卡，但是比如说维护二十几次方就没人会卡你，但化式子太麻烦了
时间复杂度 (O(nlog n))
#include <bits/stdc++.h>
using namespace std;
#define mid ((l + r) >> 1)
#define lson k << 1, l, mid
#define rson k << 1 | 1, mid + 1, r
const int maxn = 3e5 + 10, P1 = 1e9 + 7, P2 = 1e9 + 9, inv1 = 166666668, inv2 = 833333341;
int n, m, lastans;
struct node {
int mn, mx, v1, v2;
node(int x = INT_MAX, int y = 0, int _v1 = 0, int _v2 = 0) :
mn(x), mx(y), v1(_v1), v2(_v2) {}
} tree[maxn << 2];
inline node operator + (node a, node b) {
return node(min(a.mn, b.mn), max(a.mx, b.mx), (a.v1 + b.v1) % P1, (a.v2 + b.v2) % P2);
}
void build(int k, int l, int r) {
if (l == r) {
int x;
scanf("%d", &x);
tree[k] = node(x, x, 1ll * x * x % P1, 1ll * x * x % P2);
return;
}
build(lson), build(rson);
tree[k] = tree[k << 1] + tree[k << 1 | 1];
}
void upd(int k, int l, int r, int x, int v) {
if (l == r) {
tree[k] = node(v, v, 1ll * v * v % P1, 1ll * v * v % P2);
return;
}
if (x <= mid) {
upd(lson, x, v);
} else {
upd(rson, x, v);
}
tree[k] = tree[k << 1] + tree[k << 1 | 1];
}
node query(int k, int l, int r, int ql, int qr) {
if (ql <= l && r <= qr) {
return tree[k];
}
node res;
if (ql <= mid) res = query(lson, ql, qr);
if (qr > mid) res = res + query(rson, ql, qr);
return res;
}
inline int getsum(int l, int k, int t, int P, int inv) {
return (1ll * l * l % P * (t + 1) % P + k * (1ll * l * t % P * (t + 1) % P + k * (1ll * t * (t + 1) % P * (2 * t + 1) % P * inv % P))) % P;
}
inline int getsum1(int l, int r, int k) {
return getsum(l, k, (r - l) / k, P1, inv1);
}
inline int getsum2(int l, int r, int k) {
return getsum(l, k, (r - l) / k, P2, inv2);
}
inline int reget(int x) {
if (x < 1) x = 1;
if (x > n) x = n;
return x;
}
int main() {
scanf("%d %d", &n, &m);
build(1, 1, n);
int op, x, y, k; node tmp;
while (m--) {
scanf("%d %d %d", &op, &x, &y);
x ^= lastans, y ^= lastans, x = reget(x);
if (op == 1) {
upd(1, 1, n, x, y);
continue;
}
y = reget(y);
if (x > y) swap(x, y);
bool ans;
scanf("%d", &k);
k ^= lastans;
if (x == y) {
ans = 1;
} else {
tmp = query(1, 1, n, x, y);
ans = k ? tmp.mx - tmp.mn == 1ll * k * (y - x) && getsum1(tmp.mn, tmp.mx, k) == tmp.v1 && getsum2(tmp.mn, tmp.mx, k) == tmp.v2 : tmp.mn == tmp.mx;
}
ans ? lastans++, puts("Yes") : puts("No");
}
return 0;
}