给定一个长度为 \(n\) 的序列，第 \(i\) 个数为 \(a_i\)
进行以下操作：
- 单点修改
- 查询区间排完序是否是个公差为 \(k\) 的等差数列
\(1\leq n,m\leq 3\times10^5, 0\leq a_i,y,k\leq10^9\)
solution：
一种新方法：维护区间的平方和的 \(hash\) 值
如果这个区间为等差数列，首项为 \(x\) ，公差为 \(k\) ，项数为 \(n\) 那么就有
\[hash = \sum_{i = 0}^{i = n - 1}(x + ki)^2 \\
= \sum_{i = 0}^{i = n - 1}(x^2 + 2kix + k^2i^2)\\~~
= nx^2 + 2k\sum_{i = 0}^{i = n - 1}ix + k^2\sum_{i = 0}^{i = n - 1}i^2
\]
\[\sum_{i = 0}^{i = n - 1}i = \frac{(n - 1)\times n}{2}
\]
\[\sum_{i = 0}^{i = n - 1}i^2 = \frac{n(n - 1)(2n - 1)}{6}
\]
\[hash = nx^2 + k(n - 1)nx + \frac{k^2 n(n - 1)(2n - 1)}{6}
\]
维护两个 hash 值，线段树维护两个区间平方和，最后比较是否相等就可以判断等差数列了
/*
work by:Ariel_
inv[10^9 + 7] = 166666668
inv[10^9 + 9] = 833333341
*/
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
#include <algorithm>
#define rg register
#define lson rt << 1
#define rson rt << 1 | 1
#define mid ((tree[rt].l + tree[rt].r) >> 1)
using namespace std;
const int N = 3e5 + 100;
const int mod1 = 1e9 + 7;
const int mod2 = 1e9 + 9;
const int INF = 0x7fffffff;
typedef long long ll;
int read(){
int x = 0,f = 1; char c = getchar();
while(c < ‘0‘||c > ‘9‘) {if(c == ‘-‘) f = -1; c = getchar();}
while(c >= ‘0‘ && c <= ‘9‘) {x = x*10 + c - ‘0‘; c = getchar();}
return x*f;
}
int a[N];
struct Tree{int l, r, min, val1, val2;}tree[N << 2];
void push_up(int rt) {
tree[rt].min = min(tree[lson].min, tree[rson].min);
tree[rt].val1 = (tree[lson].val1 + tree[rson].val1) % mod1;
tree[rt].val2 = (tree[lson].val2 + tree[rson].val2) % mod2;
}
void build(int rt, int l, int r) {
tree[rt].l = l, tree[rt].r = r;
if (l == r) {
tree[rt].min = a[l];
tree[rt].val1 = (ll(a[l]) * a[l]) % mod1;
tree[rt].val2 = (ll(a[l])* a[l]) % mod2;
return ;
}
build(lson, l, mid), build(rson, mid + 1, r);
push_up(rt);
}
int query_min(int rt, int L, int R) {
if (L <= tree[rt].l && tree[rt].r <= R) return tree[rt].min;
int res = INF;
if (L <= mid) res = min(res, query_min(lson, L, R));
if (R > mid) res = min(res, query_min(rson, L, R));
return res;
}
int query_val1(int rt, int L, int R) {
if (L <= tree[rt].l && tree[rt].r <= R) return tree[rt].val1;
int res = 0;
if (L <= mid) res += query_val1(lson, L, R), res %= mod1;
if (R > mid) res += query_val1(rson, L, R), res %= mod1;
return res;
}
int query_val2(int rt, int L, int R) {
if (L <= tree[rt].l && tree[rt].r <= R) return tree[rt].val2;
int res = 0;
if (L <= mid) res += query_val2(lson, L, R), res %= mod2;
if (R > mid) res += query_val2(rson, L, R), res %= mod2;
return res;
}
void modify(int rt, int pos, int k) {
if (tree[rt].l == tree[rt].r) {
tree[rt].min = k;
tree[rt].val1 = (ll(k) * k) % mod1;
tree[rt].val2 = (ll(k) * k) % mod2;
return ;
}
if (pos <= mid) modify(lson, pos, k);
else modify(rson, pos, k);
push_up(rt);
}
int solve(ll x, ll n, ll k, ll mod){
x %= mod,n %= mod,k %= mod;
ll res = 0;
res += ((ll(n) * x % mod) * x) % mod, res %= mod;
res += (((ll(n) * (n - 1) % mod) * k % mod) * x) % mod,res %= mod;
res += (((((ll(k) * k % mod) * n % mod) * (n - 1) % mod) * (2 * n - 1) % mod) * ((mod == 1e9 + 7) ? 166666668 : 833333341)) % mod,res %= mod;
return res % mod;
}
bool Check(int l, int r, int k) {
int n = r - l + 1, x = query_min(1, l, r);
return query_val1(1, l, r) == solve(x, n, k, mod1) && (query_val2(1, l, r) == solve(x, n, k, mod2));
}
int n, m, opt, cnt;
int main(){
//freopen("a.in", "r", stdin);
n = read(), m = read();
for (int i = 1; i <= n; i++) a[i] = read();
build(1, 1, n);
for (int i = 1; i <= m; i++) {
int opt = read();
if (opt == 1) {
int x = read(), y = read();
modify(1, x ^ cnt, y ^ cnt);
}
else {
int l = read(), r = read(), k = read();
Check(l ^ cnt, r ^ cnt, k ^ cnt) ? cnt++, printf("Yes\n") : printf("No\n");
}
}
return 0;
}