• 修改数列某个位置的值
• 询问某个区间的值是否是连续的（即排序后是否单调递增且差都为 1）

#include <bits/stdc++.h>

#define NS (500005)
#define lowbit(a) ((a) & -(a))

using namespace std;

typedef unsigned long long ull;

mt19937_64 Rand(19260817);

inline char getC()
{
static char buff[1000000], *p = buff, *q = buff;
if (p == q)
{
q = (p = buff) + fread(buff, 1, 1000000, stdin);
if (p == q) return EOF;
}
return *p++;
}

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

int n, m, A[NS], H[NS << 2], hs, O[NS], X[NS], Y[NS];

ull t[NS], t2[NS], f[NS << 2], pre[NS << 2];

inline void push(int a, ull d)
{
while (a <= n) t[a] ^= d, a += lowbit(a);
}

inline ull sum(int a)
{
ull res = 0;
while (a) res ^= t[a], a -= lowbit(a);
return res;
}

inline void add(int a, int d)
{
while (a <= n) t2[a] += d, a += lowbit(a);
}

inline ull tot(int a)
{
ull res = 0;
while (a) res += t2[a], a -= lowbit(a);
return res;
}

void build()
{
for (int i = 1; i <= hs; i += 1)
f[i] = Rand(), pre[i] = pre[i - 1] ^ f[i];
for (int i = 1; i <= n; i += 1)
}

int main(int argc, char const* argv[])
{
IN(n), IN(m);
for (int i = 1; i <= n; i += 1)
IN(A[i]), H[++hs] = A[i], H[++hs] = A[i] + 1;
for (int i = 1; i <= m; i += 1)
{
IN(O[i]), IN(X[i]), IN(Y[i]);
if (O[i] == 1) H[++hs] = Y[i], H[++hs] = Y[i] + 1;
}
sort(H + 1, H + 1 + hs);
int tmp = hs;
H[0] = -1, hs = 0;
for (int i = 1; i <= tmp; i += 1)
if (H[i] != H[i - 1]) H[++hs] = H[i];
for (int i = 1; i <= n; i += 1)
A[i] = lower_bound(H + 1, H + 1 + hs, A[i]) - H;
for (int i = 1; i <= m; i += 1)
if (O[i] == 1) Y[i] = lower_bound(H + 1, H + 1 + hs, Y[i]) - H;
build();
for (int i = 1; i <= m; i += 1)
if (O[i] == 1)
{
A[X[i]] = Y[i];
}
else
{
ull k = tot(Y[i]) - tot(X[i] - 1), x = Y[i] - X[i] + 1;
k = (k << 1) - x * x + x;
if (k % (x << 1)) { puts("yuanxing"); continue; }
x = k / (x << 1), x = pre[x + Y[i] - X[i]] ^ pre[x - 1];
if (x == (sum(Y[i]) ^ sum(X[i] - 1))) puts("damushen");
else puts("yuanxing");
}
return 0;
}


#### Remmina

No puzzle that couldn't be solved.

### 5 条评论

#### Remmina · 2019年4月1日 8:21 下午

高斯整点就是圆上整点，即 $x ^ 2 + y ^ 2 = C$的解（$C$为常数）

找两个高斯整点就能卡掉平方和

立方和。。。难道是球上整点？

我看到 Luogu 上有人说可以卡掉维护 $n$次方和的哈希（$n < 20$），不是很清楚 OvO…

#### quhengyi11 · 2019年4月4日 2:18 下午

但是不论是圆上整点还是球上整点都很难高效查找吧 QwQ

而且这题还限制了你要卡的是坐标数值上连续的点，限制太多了真不好卡吧 QAQ

(抱歉前几天去月考去了没来回复 qwq)

#### Remmina · 2019年4月5日 8:03 上午

找整点有非常高效的算法，似乎能做到 $O(\sqrt r)$（$r$为半径）

至于离散化，这个我还不是很清楚