题目链接

又是一道有趣的题目

题意:

有两种操作:

  • 修改数列某个位置的值
  • 询问某个区间的值是否是连续的(即排序后是否单调递增且差都为 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;
}
分类: 文章

Remmina

No puzzle that couldn't be solved.

5 条评论

quhengyi11 · 2019年4月1日 5:18 下午

好吧我自闭了我以前是看 lxl 的课件写这题的,他课件里写的是询问某个区间排序后是否为等差数列,然后我就爆 80 分了,为此还推了一个极其恶心的求任意等差数列立方和的公式 QAQ(:

quhengyi11 · 2019年4月1日 5:10 下午

高斯整点是什么科技 QAQ

我维护和+平方和+立方和被卡成了 80 分 TAT

好多题解里说立方和不好卡我一直感觉是我的实现出锅了

    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$为半径)

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

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用 * 标注