(luogu3792) 由乃与大母神原型和偶像崇拜

发表于 分类于 ， ，

原题链接

思路:

虽说可以用莫队解决，但是这个数据范围意味着需要一点高深的卡常技巧.

有一个十分神奇的线段树解法:

使用线段树维护最大值，最小值，以及平方和.

对于每个询问，首先判断最大值与最小值之差是否为区间长度 - 1, 然后比对最小值到最大值的连续平方和与求得的区间平方和即可. 连续平方和可以用公式求解.

“平方和” 相当于给区间做了一个哈希 , 所以不需要精确的平方和值，取模即可.

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include <cstdio>
#include <cctype>
#include <climits>
#include <algorithm>
using namespace std;
using LL = long long;
const int Mn(500500);
const LL MP(998244353); //模数
template<typename T> void qrd(T& x) {
    x = 0;
    int c = getchar();
    while(!isdigit(c)) {
        c = getchar();
    }
    while(isdigit(c)) {
        x = x*10 + c - '0';
        c = getchar();
    }
}
template<typename T, typename... Ts> void qrd(T& x,Ts&... xs) {
    qrd(x); qrd(xs...);
}

int n,m;
LL arr[Mn];
struct Td { //线段树节点
    LL mn, mx, ssm;
} t[Mn<<2];
inline void mtn(int p) {    //合并 
    t[p] = {
            min(t[p<<1].mn, t[p<<1|1].mn),
            max(t[p<<1].mx, t[p<<1|1].mx),
            (t[p<<1].ssm + t[p<<1|1].ssm)%MP
    };
}
void bud(int p=1, int l=1, int r=n) {   //建树
    if(l==r) {
        t[p] = {arr[l],arr[l],arr[l]*arr[l]%MP};
        return;
    }
    int mid((l+r)/2);
    bud(p<<1,l,mid); bud(p<<1|1,mid+1,r);
    mtn(p);
}
void mdf(int mp,LL mx,int p=1,int l=1,int r=n) {    //修改
    if(l==r) {
        t[p] = {mx,mx,mx*mx%MP};
        return;
    }
    int mid((l+r)/2);
    if(mp<=mid) {
        mdf(mp,mx,p<<1,l,mid);
    } else {
        mdf(mp,mx,p<<1|1,mid+1,r);
    }
    mtn(p);
}
Td qry(int ql,int qr,int p=1,int l=1,int r=n) {     //查询
    if(l>=ql && r<=qr) {
        return t[p];
    }
    Td lret = {INT_MAX,INT_MIN,0}, rret = {INT_MAX,INT_MIN,0};
    int mid((l+r)/2);
    if(ql<=mid) {
        lret = qry(ql,qr,p<<1,l,mid);
    }
    if(qr>mid) {
        rret = qry(ql,qr,p<<1|1,mid+1,r);
    }
    return {
        min(lret.mn, rret.mn),
        max(lret.mx, rret.mx),
        (lret.ssm + rret.ssm) % MP
    };
}
inline LL calc(LL x) {  //计算前n项平方和
    const static LL INV_6(166374059);   //6在MP下逆元
    return x*(x+1)%MP*(2ll*x+1)%MP*INV_6%MP;    //公式
}

int main() {
    qrd(n,m);
    for(int i(1);i<=n;++i) {
        qrd(arr[i]);
    }
    bud();
    while(m--) {
        int o, x, y;
        qrd(o,x,y);
        if(o==1) {
            mdf(x,y);
        } else {
            Td tdp = qry(x,y);
            LL sm = (calc(tdp.mx) - calc(tdp.mn-1) + MP) % MP;  //连续平方和
            printf("%s\n",(tdp.ssm==sm && tdp.mx-tdp.mn==y-x)?"damushen":"yuanxing");   //比对
        }
    }
    return 0;
}