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

· · 题解

指针毁我青春

看到题以为正解是分块于是开始想不正经做法。。。想到可以维护一些区间信息再和当它是连续区间的信息比较，类似于哈希的思想把区间转成数字，后来发现还真是。

这道题既然是类似哈希思想，不妨设个假的哈希函数：

h(l,r)=\sum_{i=l}^r a_i^2

区间平方和线段树随便维护。。。

但显然还要维护区间的max和min，由于值域小，\sum_{i=min}^{max}i^2暴力算就好。同时显然区间长度不等于max-min+1也不是值域连续的区间。

于是线段树维护区间平方和，区间minmax。区间平方和int自然溢出就好。

提醒：指针赋新地址原来的地址还会保留占空间，所以赋新地址前要先delete之前的地址

稀有指针党代码（然鹅指针出莫名其妙的MLE调半天）：

#pragma GCC optimize(3)
#include <iostream>
#include <cstdio>

using namespace std;

inline int read() {
    char ch = getchar();
    int s = 0, f = 1;
    while (!isdigit(ch)) f = (ch == '-' ? -1 : 1), ch = getchar();
    while (isdigit(ch)) s = (s << 1) + (s << 3) + (ch & 15), ch = getchar();
    return s * f;
}

int n, m, opt, l, r;

struct node {
    int mn = 0x3f3f3f3f, mx = -0x3f3f3f3f, sum = 0;
    node *left = NULL;
    node *right = NULL;

    inline void update() {
        sum = left -> sum + right -> sum;
        mn = (left -> mn > right -> mn ? right -> mn : left -> mn);
        mx = (left -> mx > right -> mx ? left -> mx : right -> mx);
    }

    inline void build(int l, int r) {
        if (l >= r) { mn = mx = read(); sum = mn * mn; }
        else {
            left = new node; left -> build(l, l + r >> 1);
            right = new node; right -> build((l + r >> 1) + 1, r);
            update();
        }
    }

    inline void modify(int ll, int rr, int l, int k) {
        if (ll >= rr) { mn = mx = k; sum = k * k; }
        else {
            if (l <= ll + rr >> 1) left -> modify(ll, ll + rr >> 1, l, k);
            else right -> modify((ll + rr >> 1) + 1, rr, l, k);
            update();
        }
    }

    inline node* query(int ll, int rr, int l, int r) {
        node *rt = new node; rt -> sum = sum; rt -> mn = mn; rt -> mx = mx;
        if (ll >= l && rr <= r) return rt;
        rt -> left = new node; rt -> right = new node;
        if (l <= ll + rr >> 1) {delete rt -> left; rt -> left = left -> query(ll, ll + rr >> 1, l, r); }
        if (r > ll + rr >> 1) {delete rt -> right; rt -> right = right -> query((ll + rr >> 1) + 1, rr, l, r); }
        rt -> update(); delete rt -> left; delete rt -> right; return rt;
    }
};

int main() {
    n = read(); m = read();
    node *root = new node; root -> build(1, n);
    while (m--) {
        opt = read(); l = read(); r = read();
        if (opt == 1) root -> modify(1, n, l, r);
        else {
            if (l > r) swap(l, r);
            node *rr = root -> query(1, n, l, r);
            if (r - l + 1 != (rr -> mx - rr -> mn + 1)) { delete rr; puts("yuanxing"); continue; }
            int s = 0;
            for (int i = rr -> mn; i <= rr -> mx; ++i) s += i * i;
            if (rr -> sum != s) puts("yuanxing");
            else puts("damushen"); delete rr;
        }
    }
    return 0;
}