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

· · 题解

连续交了7次终于A了。。

嗯嗯，也是平方和，但是为了解决溢出的问题通过了很多数学手段还有哈希的思想将数据缩小。。

1^2+2^2+3^2+…+n^2=n(n+1)(2n+1)/6

就是这个小学讲过的公式

具体看代码吧，幸好有两秒不然600多ms看的我真是虚。。

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
//为了防止溢出大部分地方都通过对p取模的方式缩小
using namespace std;
const int maxn = 5e5 + 5;
const int p = 1e9 + 7;
struct Node
{
    int l, r;
    long long mi, ma, sum;
    Node() {}
    Node(int l1, int r1, long long mi1, long long mi2, long long sum1)
    {
        l = l1, r = r1, mi = mi1, ma = mi2, sum = sum1;
    }
}tree[maxn << 2];
int n, m;
long long a[maxn];
/*小学学过的那种求连续平方和办法的取模改进版本
利用了费马小定理和乘法逆元，将÷6改为×166666668  */
inline long long getsum(long long m, long long n)
{
    long long x = m - 1;
    return ((((((((n * (n + 1)) % p)*(2 * n + 1)) % p) * 166666668) % p - (((((x * (x + 1)) % p)*(2 * x + 1)) % p) * 166666668) % p) % p) + p) % p;
}
void build(int o, int l, int r)
{
    tree[o].l = l, tree[o].r = r;
    if (l == r)
    {
        tree[o].sum = (a[l] * a[r]) % p;
        tree[o].ma = a[l];
        tree[o].mi = a[r];
        return;
    }
    int mid = (l + r) >> 1;
    build(o << 1, l, mid);
    build(o << 1 | 1, mid + 1, r);
    tree[o].sum = (tree[o << 1].sum + tree[o << 1 | 1].sum) % p;
    tree[o].mi = min(tree[o << 1].mi, tree[o << 1 | 1].mi);
    tree[o].ma = max(tree[o << 1].ma, tree[o << 1 | 1].ma);
}
//模板pushup
inline void pushup(int o)
{
    if (tree[o].l == tree[o].r)
        return;
    tree[o].sum = (tree[o << 1].sum + tree[o << 1 | 1].sum) % p;
    tree[o].mi = min(tree[o << 1].mi, tree[o << 1 | 1].mi);
    tree[o].ma = max(tree[o << 1].ma, tree[o << 1 | 1].ma);
}
//模板升级
void update(int o, int x, long long y)
{
    if (tree[o].l == tree[o].r&&tree[o].l == x)
    {
        a[x] = y;
        tree[o].sum = (y * y) % p;
        tree[o].ma = y;
        tree[o].mi = y;
        return;
    }
    int mid = (tree[o].l + tree[o].r) >> 1;
    if (x > mid)
        update(o << 1 | 1, x, y);
    if (x <= mid)
        update(o << 1, x, y);
    pushup(o);
}
//查询该区间内平方和
long long query1(int o, int l, int r)
{
    if (tree[o].l >= l && tree[o].r <= r)
        return tree[o].sum;
    int mid = (tree[o].l + tree[o].r) >> 1;
    if (l > mid)
        return query1(o << 1 | 1, l, r);
    else if (r <= mid)
        return query1(o << 1, l, r);
    else
        return ((query1(o << 1, l, mid)) + (query1(o << 1 | 1, mid + 1, r))) % p;
}
//查询该区间内最小值
long long query2(int o, int l, int r)
{
    if (tree[o].l >= l && tree[o].r <= r)
        return tree[o].mi;
    int mid = (tree[o].l + tree[o].r) >> 1;
    if (l > mid)
        return query2(o << 1 | 1, l, r);
    else if (r <= mid)
        return query2(o << 1, l, r);
    else
        return min((query2(o << 1, l, mid)), (query2(o << 1 | 1, mid + 1, r)));
}
//查询该区间内最大值
long long query3(int o, int l, int r)
{
    if (tree[o].l >= l && tree[o].r <= r)
        return tree[o].ma;
    int mid = (tree[o].l + tree[o].r) >> 1;
    if (l > mid)
        return query3(o << 1 | 1, l, r);
    else if (r <= mid)
        return query3(o << 1, l, r);
    else
        return max((query3(o << 1, l, mid)), (query3(o << 1 | 1, mid + 1, r)));
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &a[i]);
    build(1, 1, n);
    for (int i = 1; i <= m; i++)
    {
        int opt;
        scanf("%d", &opt);
        if (opt == 1)
        {
            int x;
            long long y;
            scanf("%d%lld", &x, &y);
            update(1, x, y);
        }
        if (opt == 2)
        {
            int l, r;
            scanf("%d%d", &l, &r);
            long long tmp = ((query3(1, l, r) - query2(1, l, r)) % p + p) % p;
            //初级判定，如果序列长度和序列最大值与最小值之差不相等则必然不成立
            bool a = (r - l) == tmp;
            if (a == false) {
                printf("yuanxing\n");
                continue;
            }
            //二级判定，关于n的公式算出来的平方和与该区间内真正的平方和对比
            a = (query1(1, l, r) == getsum(query2(1, l, r), query3(1, l, r)));
            if (a == true)
                printf("damushen\n");
            else
                printf("yuanxing\n");
        }
    }
    return 0;
}