UOJ#228.基础数据结构练习题

题目链接

 ?这个题目就是让我们实现三个操作\(1.\)区间加，\(2.\)区间开方，\(3.\)区间求和。可以用势能线段树来写，也可以用分块来写。我们就用分块来写这个题。
 ?我们先对整个序列进行预处理，将整个序列分成多个块

    for (int i = 1; i <= n; i ++ ) std::cin >> a[i];
    int lim = sqrt(n);
    for (int i = 1; i <= lim; i ++ ) bln[i] = (i - 1) * lim + 1, brn[i] = i * lim;
    if (brn[lim] < n) lim ++, bln[lim] = brn[lim - 1] + 1, brn[lim] = n;
    for (int i = 1; i <= lim; i ++ ) 
        for (int j = bln[i]; j <= brn[i]; j ++ ) 
            belong[j] = i, update(i);

 ?由于本题不同于单单只进行区间加的操作或者区间开方的操作，如果我们仅仅只有\(sqrtfree\)来维护这个区间能否继续暴力开方的话，是可以被卡掉的，如果我们一直开方开到\(1\)之后，再进行一次区间加的操作，把所有的数都加到\(10^5\)，那么就是出题人在\(O(1)\)的时间复杂度下，让我们继续进行\(O(\log V)\)次暴力，但是每一次的暴力复杂度又是\(O(n)\)的，所以很容易就被出题人卡时间了。如果只是单纯的区间开方不进行区间加的话，可以在\(O(n\log V + q\sqrt n)\)的复杂度下完成区间开方。所以本题我们要多用\(mx[i]\)和\(mn[i]\)来维护区间最值，在开方的时候我们只需要去判断最大值和最小值是否相等，如果相等的话，我们计算开方前后的变化量是多少，然后我们对整块进行开方操作就简化成了对整块进行一次区间加法，所有的数都加上一个\(\sqrt mx - mx\),这样就可以实现\(O(1)\)的时间复杂度下对整块进行开方的操作。采用区间最大值和最小值来实现区间开方的话，出题人想卡的话，就要用\(O(\frac{n}{B})\)次操作去破坏所有块的最大值最小值的性质，这个时候我们的开方操作就会从\(O(1)\)退化为\(O(n)\)，所以采用这个方法的话，出题人卡我们的代价就会变大。

维护区间最值操作

 ?其实就是将那个整块的标记先释放，然后重新求出\(sum\)，\(mx[bel]\)和\(mn[bel]\)。

    auto update = [&] (int id) {
        for (int i = bln[id]; i <= brn[id]; i ++ ) a[i] += tag[id];
        sum[id] = 0, mx[id] = 0, mn[id] = inf;
        for (int i = bln[id]; i <= brn[id]; i ++ ) 
            mx[id] = std::max(mx[id], a[i]), mn[id] = std::min(mn[id], a[i]), sum[id] += a[i];
        tag[id] = 0;
    };

操作一：区间加法

 ?我们用\(tag\)和\(sum\)来维护这个区间的懒惰标记和整块的总和，并且才实现完区间加法的时候，要时刻更新我们的\(sum\)和\(mx\),\(mn\)，，每一次都要及时的将\(tag\)懒惰标记向下释放，为的是维护最大值和最小值。

    auto change = [&] (int l, int r, i64 val) {
        if (belong[l] == belong[r]) {
            for (int i = l, bel = belong[l]; i <= r; i ++ ) a[i] += val;
            update(belong[l]);
            return ;
        }

        for (int i = belong[l] + 1; i < belong[r]; i ++ ) 
            tag[i] += val, mx[i] += val, mn[i] += val, sum[i] += 1ll * (brn[i] - bln[i] + 1) * val;
        for (int i = l, bel = belong[l]; i <= brn[bel]; i ++ ) a[i] += val;
        for (int i = bln[belong[r]], bel = belong[r]; i <= r; i ++ ) a[i] += val;
        update(belong[l]), update(belong[r]);
    };

操作二：区间开方

 ?判断区间最大值和区间最小值是否相等，从而来选择我们这个时候对区间开方的操作是暴力开方还是采用类区间加法来实现区间开方。

    auto sqrtop = [&] (int l, int r) -> void {
        if (belong[l] == belong[r]) {
            update(belong[l]);
            for (int i = l, bel = belong[l]; i <= r; i ++ ) a[i] = i64(sqrt(a[i]) + 1E-9);
            update(belong[l]);
            return ;
        }

        for (int i = belong[l] + 1; i < belong[r]; i ++ ) {
            if (mx[i] == mn[i]) {
                const i64 dlt = mx[i] - sqrtv(mx[i]);
                tag[i] -= dlt, mx[i] -= dlt, mn[i] -= dlt, sum[i] -= (brn[i] - bln[i] + 1) * dlt;
            } else {
                const int sv = sqrtv(mx[i]);
                if (i64(sv) * sv == mx[i] && mx[i] - mn[i] == 1) {
                    const i64 dlt = mx[i] - sv;
                    tag[i] -= dlt, mx[i] -= dlt, mn[i] -= dlt, sum[i] -= (brn[i] - bln[i] + 1) * dlt;
                } else {
                    for (int id = brn[i]; id >= bln[i]; --id)
                        SQRT(a[id] += tag[i]);
                    tag[i] = 0, update(i);
                }
            }
        }
        update(belong[l]);
        for (int i = l, bel = belong[l]; i <= brn[bel]; i ++ ) a[i] = i64(sqrt(a[i]) + 1E-9);
        update(belong[l]);
        update(belong[r]);
        for (int i = bln[belong[r]], bel = belong[r]; i <= r; i ++ ) a[i] = i64(sqrt(a[i]) + 1E-9);
        update(belong[r]);
    };

操作三：区间求和

 ?区间求和操作就是很正常的操作了。

    auto query = [&] (int l, int r) -> i64 {
        i64 ans = 0;
        if (belong[l] == belong[r]) {
            for (int i = l, bel = belong[l]; i <= r; i ++ ) ans += a[i] + tag[bel];
            return ans;
        }

        for (int i = belong[l] + 1; i < belong[r]; i ++ ) ans += sum[i];
        for (int i = l, bel = belong[l]; i <= brn[bel]; i ++ ) ans += a[i] + tag[bel];
        for (int i = bln[belong[r]], bel = belong[r]; i <= r; i ++ ) ans += a[i] + tag[bel];
        return ans;
    };