鸡格线

原题链接

TAG：线段树

思路

通过打表可以发现对于任意的 \(x\)，经过极少次的 \(f(x)\) 操作，可以收敛到某一值 \(f(x_0)=x_0\)。

其中 \(x_0\) 有三个：0，99，100。

通过线段树可以直接维护区间的修改。

结点信息

需要维护的信息：区间的总和，区间的最大最小值。

修改操作

因为操作的次数极小，可以进行单点暴力修改，当收敛到某个值的时候，直接省略接下去的操作。

查询操作

需要求出当前所有数字的和，即区间 \([1,n]\) 的和，那么就是线段树根节点的 \(sum\) 值。

---

代码

#include <bits/stdc++.h>
using LL = long long;

const int N = 100010;

int n, m;
int w[N];
struct Node {
    int l, r;
    LL sum, max, min;
} tr[N << 2];

void pushup(int u) {
    tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
    tr[u].max = std::max(tr[u << 1].max, tr[u << 1 | 1].max);
    tr[u].min = std::min(tr[u << 1].min, tr[u << 1 | 1].min);
}

void build(int u, int l, int r) {
    if (l == r) {
        tr[u] = {l, r, w[r], w[r], w[r]};
        if (w[r] == 0) {
            tr[u].max = tr[u].min = 100;
        }
    } else {
        tr[u] = {l, r};
        int mid = l + r >> 1;
        build(u << 1, l, mid);
        build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }
}

void modify(int u, int l, int r, int x, int y, int k) {
    if (tr[u].max <= 100 && tr[u].min >= 99) return;
    if (l > y || r < x) return;
    if (l == r) {
        while (k && tr[u].max != 99 && tr[u].max != 100) {
            tr[u].max = std::sqrt(tr[u].max) * 10 + .5;
            k--;
        }
        tr[u].sum = tr[u].min = tr[u].max;
    } else {
        int mid = l + r >> 1;
        modify(u << 1, l, mid, x, y, k);
        modify(u << 1 | 1, mid + 1, r, x, y, k);
        pushup(u);
    }
}

int main() {
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    std::cout.tie(0);

    std::cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        std::cin >> w[i];
    }

    build(1, 1, n);

    int op;
    while (m--) {
        std::cin >> op;
        if (op == 1) {
            int l, r, k;
            std::cin >> l >> r >> k;
            modify(1, 1, n, l, r, k);
        } else std::cout << tr[1].sum << "\n";
    }

    return 0;
}