【题解】由乃与大母神原型和偶像崇拜 哈希 树状数组 Luogu – 3792

题目链接

又是一道有趣的题目

题意：

有两种操作：

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

题目看起来很不可做，数据又非常非常大，所以就只能哈希了

一种比较简单的哈希方法是维护区间最大最小和区间平方和（或立方和之类的），然而用高斯整点就能卡掉这些算法

比较有趣的做法是先离散化，然后每个值随机给一个 $[0, 2 ^ {64})$权值，定义区间的权值为区间权值异或和

对于连续的一段数值的权值可以用异或前缀和来求

再维护一个区间数值和，这样可以通过区间数值和以及区间长度算出 “如果这个区间是连续的那么这个区间覆盖了哪些数值”，然后求出理论上这些数值的对应的权值异或和，与区间实际权值异或和做对比，就知道这个区间是否是连续的了。

相同的区间的哈希值一定相同，而不同的区间哈希值相同的概率为 $\frac 1 {2 ^ {64}}$，总共有 $\frac {(5 \times 10 ^ 5) ^ 2} 2 = 1.25 \times 10 ^ {11}$个区间，冲突率大约为 $6.78 \times 10 ^ {-9}$，总之就是不可能被卡掉的

而且维护可以用树状数组搞，跑得很快

代码：

#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)
        push(i, f[A[i]]), add(i, A[i]);
}

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)
        {
            push(X[i], f[A[X[i]]]), add(X[i], -A[X[i]]);
            A[X[i]] = Y[i];
            push(X[i], f[Y[i]]), add(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;
}