emmmm… 第一次考场做这么恶心的题还打错了。。。记录一下。。。

# 1. 题目

• 单点修改
• 询问一个区间排序后是否为等差序列

# 2. 题解

（以上 “哈哈” 使用倍增算法生成）

It’s easy to think, but it’s difficult to code. —— Cai

• 区间最大
• 区间最小
• 区间和
• 差分序列的区间 GCD
• 区间内是否有重复元素

#include <bits/stdc++.h>

#define NS (300005)
#define LS(a) (a << 1)
#define RS(a) (a << 1 | 1)
#define REG register

using namespace std;

typedef long long LL;

template<typename _Tp> inline void IN(_Tp& dig)
{
char c; bool flag = 0; dig = 0;
while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
if (flag) dig = -dig;
}

int n, m, arr[NS], dt[NS], pre[NS];

int mn[NS << 2], mx[NS << 2], mp[NS << 2], gc[NS << 2];

LL sum[NS << 2];

map<int, int> h;

set<int> pos[NS << 1];

struct Pac
{
int x, y, o; LL z;
Pac() {x = y = z = o = 0;}
Pac(REG int a, REG int b, REG LL c, REG int d) {x = a, y = b, z = c, o = d;}
};

int hs = 0;

inline int H(REG int a)
{
REG int tmp = h[a];
if (tmp != 0) return tmp;
h[a] = ++hs; return hs;
}

/*SGT1 for mn, mx, sum and min_pos*/

inline void pup1(REG int a)
{
REG int l = LS(a), r = RS(a);
sum[a] = sum[l] + sum[r], mp[a] = min(mp[l], mp[r]);
mn[a] = min(mn[l], mn[r]), mx[a] = max(mx[l], mx[r]);
}

void Build1(REG int l, REG int r, REG int a)
{
if (l == r)
{
mn[a] = mx[a] = sum[a] = arr[l], mp[a] = pre[l];
return;
}
REG int mid = (l + r) >> 1;
Build1(l, mid, LS(a)), Build1(mid + 1, r, RS(a)), pup1(a);
}

inline void Update1(REG int x, REG int d)
{
REG int a = 1, l = 1, r = n, mid;
while (l < r)
{
if (mid = (l + r) >> 1, x <= mid) a = LS(a), r = mid;
else a = RS(a), l = mid + 1;
}
mn[a] = mx[a] = sum[a] = d, a >>= 1;
while (a) pup1(a), a >>= 1;
}

inline void Update_mp(REG int x, REG int d)
{
REG int a = 1, l = 1, r = n, mid;
while (l < r)
{
if (mid = (l + r) >> 1, x <= mid) a = LS(a), r = mid;
else a = RS(a), l = mid + 1;
}
mp[a] = d, a >>= 1;
while (a) pup1(a), a >>= 1;
}

Pac Query1(int l, int r, int L, int R, int a)
{
if (l <= L && R <= r) return Pac(mn[a], mx[a], sum[a], mp[a]);
int Mid = (L + R) >> 1;
Pac res(INT_MAX, INT_MIN, 0, INT_MAX), tmp;
if (l <= Mid)
{
tmp = Query1(l, r, L, Mid, LS(a));
res.x = min(res.x, tmp.x);
res.y = max(res.y, tmp.y);
res.z += tmp.z, res.o = min(res.o, tmp.o);
}
if (r > Mid)
{
tmp = Query1(l, r, Mid + 1, R, RS(a));
res.x = min(res.x, tmp.x);
res.y = max(res.y, tmp.y);
res.z += tmp.z, res.o = min(res.o, tmp.o);
}
return res;
}

/*SGT2 for gcd*/

int gcd(REG int a, REG int b) {return b ? gcd(b, a % b) : a;}

inline void pup2(int a)
{
REG int l = LS(a), r = RS(a);
gc[a] = gcd(gc[l], gc[r]);
return;
}

void Build2(REG int l, REG int r, REG int a)
{
if (l == r) {gc[a] = dt[l]; return;}
REG int mid = (l + r) >> 1;
Build2(l, mid, LS(a)), Build2(mid + 1, r, RS(a)), pup2(a);
}

inline void Update2(REG int x, REG int d)
{
REG int a = 1, l = 1, r = n - 1, mid;
while (l < r)
{
if (mid = (l + r) >> 1, x <= mid) a = LS(a), r = mid;
else a = RS(a), l = mid + 1;
}
gc[a] = d, a >>= 1;
while (a) pup2(a), a >>= 1;
}

int Query2(REG int l, REG int r, REG int L, REG int R, REG int a)
{
if (l <= L && R <= r) return gc[a];
REG int Mid = (L + R) >> 1, res = -1;
if (l <= Mid)
{
if (res < 0) res = Query2(l, r, L, Mid, LS(a));
else res = gcd(res, Query2(l, r, L, Mid, LS(a)));
}
if (r > Mid)
{
if (res < 0) res = Query2(l, r, Mid + 1, R, RS(a));
else res = gcd(res, Query2(l, r, Mid + 1, R, RS(a)));
}
return res;
}

int main(int argc, char const* argv[])
{
IN(n), IN(m);
if (n == 1)
{
while (m--) puts("Yes");
return 0;
}
for (REG int i = 1; i <= n; i += 1) IN(arr[i]);
for (REG int i = n, j; i >= 1; i -= 1)
{
j = H(arr[i]);
if (pos[j].empty()) pre[i] = n + 1;
else pre[i] = *(pos[j].upper_bound(i));
pos[j].insert(i);
}
for (REG int i = 1; i < n; i += 1) dt[i] = abs(arr[i + 1] - arr[i]);
Build1(1, n, 1), Build2(1, n - 1, 1);
REG int op, x, y, k, tot = 0, h, g; Pac tmp; int cnt = 0;
REG set<int>::iterator it;
while (m--)
{
IN(op), IN(x), IN(y), x ^= tot, y ^= tot;
if (op == 1)
{
Update1(x, y), h = H(arr[x]), pos[h].erase(x);
it = pos[h].upper_bound(x);
if (it != pos[h].begin())
{
if (it == pos[h].end()) it--, Update_mp(*it, n + 1);
else
{
REG int tmp = *it; it--;
Update_mp(*it, tmp);
}
}
h = H(y), it = pos[h].insert(x).first, it++;
if (it != pos[h].end()) Update_mp(x, *it);
else Update_mp(x, n + 1);
it--; if (it != pos[h].begin()) it--, Update_mp(*it, x);
arr[x] = y;
if (x > 1) Update2(x - 1, abs(y - arr[x - 1]));
if (x < n) Update2(x, abs(arr[x + 1] - y));
}
else
{
++cnt;
if (x > y) swap(x, y);
IN(k), k ^= tot; if (x == y) {puts("Yes"), tot++; continue;}
tmp = Query1(x, y, 1, n, 1), g = Query2(x, y - 1, 1, n - 1, 1);
if (!k)
{
if (tmp.x == tmp.y) puts("Yes"), tot++;
else puts("No");
}
else if (g != k || tmp.o <= y) puts("No");
else if (tmp.y != (LL)(tmp.x) + 1ll * (y - x) * k) puts("No");
else if ((tmp.z << 1) != 1ll * (tmp.x + tmp.y) * (y - x + 1)) puts("No");
else puts("Yes"), tot++;
}
}
return 0;
}


mmp