题解 P3792 【由乃与大母神原型和偶像崇拜】

iuyi · 2020-07-31 16:58:25 · 题解

有一种简单的哈希：

用树状数组维护区间和区间平方和区间异或和

平方和用自然溢出就可以了

查询时通过区间和求出如果这个区间满足条件最大值和最小值是多少

判断一下平方和异或和是否都满足条件

然后就过了

常数很小

目前还没有被卡

#include <bits/stdc++.h>

using namespace std;

const int N = 500005;
int n;
int a[N];
long long tr1[N];
int tr2[N];
unsigned long long tr3[N]; 

int sm2(int x) {
    switch(x&3) {
        case 0: return x;
        case 1: return 1;
        case 2: return x+1;
        case 3: return 0;
        default: return -1;
    }
}

unsigned long long sm3(int p) {
    unsigned long long a = (long long)p*(p+1);
    unsigned long long b = p*2+1;
    if (a%2 == 0) {
        a /= 2;
    }
    else {
        b /= 2;
    }
    if (a%3 == 0) {
        a /= 3;
    }
    else {
        b /= 3;
    }
    return a*b;
}

signed main() {
    int m;
    scanf("%d%d",&n,&m);
    for (int i = 1; i <= n; i++) {
        scanf("%d",a+i);
    }
    for (int i = 1; i <= n; i++) {
        int p = i;
        while (p <= n) {
            tr1[p] += a[i];
            tr2[p] ^= a[i];
            tr3[p] += (unsigned long long)a[i]*a[i];
            p += p&-p;
        }
    }
    while (m--) {
        int op,l,r;
        scanf("%d%d%d",&op,&l,&r);
        if (op == 1) {
            int p = l;
            while (p <= n) {
                tr1[p] += r-a[l];
                tr2[p] ^= r^a[l];
                tr3[p] += (unsigned long long)r*r-(unsigned long long)a[l]*a[l];
                p += p&-p;
            }
            a[l] = r;
        }
        else {
            long long as1 = 0;
            int as2 = 0;
            unsigned long long as3 = 0;
            int ll = l;
            int rr = r;
            while (rr >= ll) {
                as1 += tr1[rr];
                as2 ^= tr2[rr];
                as3 += tr3[rr];
                rr -= rr&-rr;
            }
            ll--;
            while (ll > rr) {
                as1 -= tr1[ll];
                as2 ^= tr2[ll];
                as3 -= tr3[ll];
                ll -= ll&-ll;
            }
            int ans = 0;
            as1 *= 2;
            if (as1%(r-l+1) == 0) {
                int fr = as1/(r-l+1)-(r-l);
                if (fr%2 == 0) {
                    fr /= 2;
                    if ((sm2(fr-1)^sm2(fr+r-l)) == as2 && sm3(fr+r-l)-sm3(fr-1) == as3) {
                        ans = 1;
                    }
                }
            }
            if (ans) {
                puts("damushen");
            }
            else {
                puts("yuanxing");
            }
        } 
    }
    return 0;
}