UOJ228. 基础数据结构练习题

发布于 16 天前  36 次阅读


Link

Sol

先考虑没有区间加操作怎么做。就直接暴力开根

现在有了区间加怎么做。题目里面的开根号是向下取整的。注意到数字多次开根以后都会变成一个定值。比如说:

5 8 9 4 第一次开根以后变成 2 2 3 2 ,再开一次就变成了 1 1 1 1

很好,很有精神!我们就来分一下这个性质。假设数是v, 那么经过log_{log_v}次开根就变成了定值。

有了这个性质,我们来考虑一下这个东西怎么维护。因为在log_{log_v}次开根后变成了定值,相当于我们的操作变成了区间赋值。什么时候赋值?最快到定值的是这个区间中min值,最后到达(可能与min值同时)的是区间max值。那么我们现在关心的就是区间中的最小最大值了。当我们进到一个区间进行更新的时候,假如最大最小值开根的值都一样了,说明我们可以区间赋值了。

分析一下复杂度,操作是 O(log_{log_v}) 的,平均深度log_n。那么渐进意义时间复杂度就是 O(n log_nlog_{log_v})

但是出现这样一种情况: 15 16 15 16 15 16 15 16 这样交替相差1的情况。先开一次根,3 4 3 4 3 4... 开根以后仍然是交替相差1的。加入再加上12, 又变回了原来的情况。这种情况原来的复杂度就无法保证了。那么如何避免这种情况?当最小值和最大值只相差1的时候特判一下就可以了。

其他的标记下放等操作不变即可。

Code

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int SIZE = 2e5 + 5;

int n, q;
int a[SIZE];

struct node {
    int l, r, mi, mx, val, tag;
} tree[SIZE << 2];

namespace ae86 {
    const int bufl = 1 << 15;
    char buf[bufl], *s = buf, *t = buf;
    inline int fetch() {
        if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; }
        return *s++;
    }
    inline int read() {
        int a = 0, b = 1, c = fetch();
        while (!isdigit(c))b ^= c == '-', c = fetch();
        while (isdigit(c)) a = a * 10 + c - 48, c = fetch();
        return b ? a : -a;
    }
}
using ae86::read;

#define lson(p) p << 1
#define rson(p) p << 1 | 1

void update(int p, int x) {
    int len = tree[p].r - tree[p].l + 1;
    tree[p].val += x * len, tree[p].tag += x, tree[p].mi += x, tree[p].mx += x;
}

void pushDown(int p) {
    if (tree[p].tag) {
        update(lson(p), tree[p].tag); update(rson(p), tree[p].tag);
        tree[p].tag = 0;
    }
}

void pushUp(int p) {
    tree[p].mi = std::min(tree[lson(p)].mi, tree[rson(p)].mi);
    tree[p].mx = std::max(tree[lson(p)].mx, tree[rson(p)].mx);
    tree[p].val = tree[lson(p)].val + tree[rson(p)].val;
}

void build(int p, int l, int r) {
    tree[p].l = l, tree[p].r = r;
    if (l == r) {
        tree[p].val = tree[p].mi = tree[p].mx = a[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(lson(p), l, mid); build(rson(p), mid + 1, r);
    pushUp(p);
}

void modifySqrt(int p, int l, int r) {
    int tmp = 0;
    if (l <= tree[p].l && tree[p].r <= r && 
       ((tree[p].mx == tree[p].mi) || (tree[p].mx == tree[p].mi + 1 && (tmp = sqrt(tree[p].mx)) * tmp == tree[p].mx))) {
            update(p, (tmp ? tmp : (int)(sqrt(tree[p].mx))) - tree[p].mx);
            return;
    }
    pushDown(p);
    int mid = (tree[p].l + tree[p].r) >> 1;
    if (l <= mid) modifySqrt(lson(p), l, r);
    if (r > mid) modifySqrt(rson(p), l, r);
    pushUp(p);
}

void modifyAdd(int p, int l, int r, int v) {
    if (l <= tree[p].l && tree[p].r <= r) {
        int len = tree[p].r - tree[p].l + 1;
        tree[p].tag += v, tree[p].val += v * len, tree[p].mi += v, tree[p].mx += v;
        return;
    }
    pushDown(p);
    int mid = (tree[p].l + tree[p].r) >> 1;
    if (l <= mid) modifyAdd(lson(p), l, r, v);
    if (r > mid) modifyAdd(rson(p), l, r, v);
    pushUp(p);
}

int query(int p, int l, int r) {
    if (l <= tree[p].l && tree[p].r <= r) return tree[p].val;
    pushDown(p);
    int mid = (tree[p].l + tree[p].r) >> 1, ans = 0;
    if (l <= mid) ans += query(lson(p), l, r);
    if (r > mid) ans += query(rson(p), l, r);
    return ans;
}

signed main() {
    // freopen("code.in", "r", stdin);
    // freopen("code.out", "w", stdout);
    n = read(), q = read();
    for (int i = 1; i <= n; ++ i) a[i] = read();
    build(1, 1, n); 
    int opt, l, r, x;
    while (q --) {
        opt = read(), l = read(), r = read();
        if (opt == 1) x = read(), modifyAdd(1, l, r, x);
        if (opt == 2) modifySqrt(1, l, r);
        if (opt == 3) printf("%lld\n", query(1, l, r));
    }
    return 0;
}


学会生存 学会关心