算术天才⑨与等差数列

题意

给定一个长度为 \(n\) 的序列 \(a\)，接下来有 \(m\) 次操作：

操作 \(1\)：给定 \(x,y\)，将 \(a_x\) 修改为 \(y\)。
操作 \(2\)：给定 \(l,r,k\)，询问将区间 \([l,r]\) 中的数从小到大排序后是否形成一个公差为 \(k\) 的等差数列。

强制在线，\(x,y,l,r,k\) 均需要异或之前输出的 Yes 个数来解密。

数据范围

\(1\leqslant n,m \leqslant 3\times 10^5\)。
\(0\leqslant a_i,y,k \leqslant 10^9\)。

思路

似乎有一种随机化+维护若干次方然后哈希的做法，但据说可以被卡，所以不妨使用不需要随机化的线段树做法。

先假设不带修，来思考公差为 \(k\) 的等差数列怎么判。

首先 \(k=0\) 是简单的，维护一下区间 max, min 即可，而当 \(k\ne 0\) 时，\([l,r]\) 要形成等差数列则具有以下充要条件：

\(\max\limits_{l\leqslant i \leqslant r} \{a_i\}-\min\limits_{l\leqslant i \leqslant r} \{a_i\}=(r-l)\times k\)。
区间内每个数互不相等。
对于 \(l < i \leqslant r\)，有 \(|a_i-a_{i-1}| \equiv 0 \pmod{k}\)。

条件 \(1\) 仍旧是区间 max, min；对于条件 \(2\)，考虑记录每个数的上一次出现位置 \(lst_i\)，若 \(\max\limits_{l\leqslant i \leqslant r}\{ lst_i\}<l\)，即每个数上次出现都不在区间内，也就是互不相等；条件 \(3\) 则是可以转化为 \(\gcd\limits_{l<i\leqslant r} \{|a_i-a_{i-1}|\}\equiv 0 \pmod{k}\)，依然可以轻松判断，这些东西预处理一下即可。

接下来考虑带修如何做，不难发现上面的三个条件都可以丢到线段树上去维护，也就是线段树记录区间 max, min, max lst, gcd 和最左最右端的数方便维护差值。然后就是单点修改。

首先 max, min 和左右端的数都是直接的，那么就是看 lst 该如何维护。

由于值域 \(V\) 较大且强制在线，所以肯定要上 STL 了，考虑使用 map 套 set 来记录每个数的出现位置，那么修改 \(x\) 可能影响到 lst 的位置就是去 map[a[x]] 中找后继、map[y] 中找后继以及 \(x\) 本身了，用三次单点修改来维护即可，本题结束。

复杂度

时间：\(O((n+m)\log n)\)，由于多次单修和 STL，常数不小。
空间：\(O(n)\)。

Code

点击查看代码

#include <iostream>
#include <set>
#include <map>
#define _1 (__int128)1using namespace std;
using ll = long long;
using pii = pair<int, int>;void FileIO (const string s) {freopen((s + ".in").c_str(), "r", stdin);freopen((s + ".out").c_str(), "w", stdout);
}const int N = 3e5 + 10, INF = 1e9 + 10;struct SegTree {int mx, mi, lst, g, pre, suf;
} tr[N * 4], ret;int n, m, a[N], ans;
map<int, set<int>> mp;int Prev (int id) {auto it = mp[a[id]].lower_bound(id);if (it == mp[a[id]].begin()) return 0;else return *prev(it);
}int gcd (int x, int y) {if (!x || !y) return x + y;while (x ^= y ^= x ^= y %= x) {}return y;
}SegTree Merge (SegTree i, SegTree j) {if (i.mi == INF) return j;if (j.mi == INF) return i;return {max(i.mx, j.mx), min(i.mi, j.mi), max(i.lst, j.lst), gcd(gcd(i.g, j.g), abs(j.pre - i.suf)), i.pre, j.suf};
}void pushup (int id) {tr[id] = Merge(tr[id * 2], tr[id * 2 + 1]);
}void build (int id, int l, int r) {if (l == r) {tr[id] = {a[l], a[l], Prev(l), 0, a[l], a[l]};return ;}int mid = (l + r) >> 1;build(id * 2, l, mid), build(id * 2 + 1, mid + 1, r);pushup(id);
}void modify (int id, int l, int r, int x) {if (l == r) {tr[id] = {a[l], a[l], Prev(l), 0, a[l], a[l]};return ;}int mid = (l + r) >> 1;if (mid >= x) modify(id * 2, l, mid, x);else modify(id * 2 + 1, mid + 1, r, x);pushup(id);
}void Query (int id, int l, int r, int x, int y) {if (l >= x && r <= y) {ret = Merge(ret, tr[id]);return ;} else if (l > y || r < x) return ;int mid = (l + r) >> 1;Query(id * 2, l, mid, x, y), Query(id * 2 + 1, mid + 1, r, x, y);
}signed main () {ios::sync_with_stdio(0), cin.tie(0);// FileIO("");cin >> n >> m;for (int i = 1; i <= n; i++) cin >> a[i], mp[a[i]].insert(i);build(1, 1, n);for (int i = 1, op, x, y, k; i <= m; i++) {cin >> op >> x >> y, x ^= ans, y ^= ans;if (op == 1) {auto it = mp[a[x]].upper_bound(x);mp[a[x]].erase(x), a[x] = y;if (it != mp[a[x]].end()) modify(1, 1, n, *it);mp[a[x]].insert(x), it = mp[a[x]].upper_bound(x);if (it != mp[a[x]].end()) modify(1, 1, n, *it);modify(1, 1, n, x);} else {cin >> k, k ^= ans;if (x > y) swap(x, y);ret = {0, INF, 0, 0, 0, 0}, Query(1, 1, n, x, y);if (!k) {if (ret.mx == ret.mi) ans++, cout << "Yes\n";else cout << "No\n";} else {if (ret.mx - ret.mi != 1ll * (y - x) * k || ret.lst >= x || ret.g % k) {cout << "No\n";continue;}cout << "Yes\n";ans++;}}}return 0;
}