题解 ABC256Ex【I like Query Problem】

· · 题解

Chtholly 树模板题，我们把每一个颜色段 (l,r,v) 存入一个 set 中。

首先这个区间求和很容易破坏我们的均摊性质，因此我们可以另开一个线段树（我写的树状数组），在每一次添加或删除颜色段时进行修改，这样添加或删除一个颜色段的复杂度仍为 \mathcal{O}(\log n)。

然后考虑前两种操作，只需要将相关的颜色段取出来，进行对应的修改，将相同的颜色重新合并，再放回去就可以了。

为什么这样是对的？

我们记总势能为所有颜色段的 \log(v+1) 之和，初始时不超过 \mathcal{O}(n\log V)，而每次修改时，假设涉及到了 k 个颜色段，由于相邻颜色段 v 值不同，其中 v 非零的颜色段至少有 \frac{k-1}{2} 个。势能变化如下：

  1. 对于操作一：这些非零的颜色段 v 值至少除以 2，每一个颜色段对应的势能至少减少 \Omega(1)，总势能至少减少 \Omega(k)。

  2. 对于操作二：这些非零的颜色段合并成一个，每一个颜色段对应的势能至少减少 \Omega(1)，总势能至少减少 \Omega(k)。

同时，由于颜色段的分裂，新增了 \mathcal{O}(1) 个颜色段，每一个势能增加 \mathcal{O}(\log V)，总势能至多增加 \mathcal{O}(\log V)。

而进行上述操作所需的时间为 \mathcal{O}(k\log n)。

我们考虑：

综上，时间复杂度为 \mathcal{O}((n+q)\log n\log V)。

常数不小，跑了 3s

代码如下：

#include <bits/stdc++.h>
using namespace std;
const int _ = 5e5 + 10;
int n, q;
struct fenwick_tree {
    long long arr[_];
    #define y ((x)&(-(x)))
    inline void add(int x, long long k) {
        while (x <= n) {
            arr[x] += k;
            x += y;
        }
    }
    inline long long sum(int x) {
        long long ans = 0LL;
        while (x) {
            ans += arr[x];
            (x ^= y);
        }
        return ans;
    }
    #undef y
} A, B;
struct node {
    int l, r, v;
    inline bool operator < (const node rhs) const {
        return r < rhs.r;
    }
};
set<node> S;
inline void ins(node N) {
    S.insert(N);
    int l = N.l;
    int r = N.r;
    int v = N.v;
    A.add(l, v);
    A.add(r + 1, -v);
    B.add(l, (long long) l * v);
    B.add(r + 1, -(long long) (r + 1) * v);
}
inline void del(node N) {
    S.erase(N);
    int l = N.l;
    int r = N.r;
    int v = N.v;
    A.add(l, -v);
    A.add(r + 1, v);
    B.add(l, -(long long) l * v);
    B.add(r + 1, (long long) (r + 1) * v);
}
int m;
node inv[_];
inline void split(int l, int r) {
    auto it = S.lower_bound((node){0, l, 0});
    auto jt = S.lower_bound((node){0, r, 0});
    m = 0;
    for (auto tmp = it; tmp != jt; tmp++) {
        inv[++m] = (*tmp);
    }
    inv[++m] = (*jt);
    for (int i = 1; i <= m; i++) {
        del(inv[i]);
    }
    if (inv[1].l != l) {
        m++;
        for (int i = m; i >= 3; i--) {
            inv[i] = inv[i-1];
        }
        inv[2].l = l;
        inv[2].r = inv[1].r;
        inv[2].v = inv[1].v;
        inv[1].r = l - 1;
    }
    if (inv[m].r != r) {
        m++;
        inv[m].l = r + 1;
        inv[m].r = inv[m-1].r;
        inv[m].v = inv[m-1].v;
        inv[m-1].r = r;
    }
}
inline void calcdivi(int l, int r, int v) {
    for (int i = 1; i <= m; i++) {
        if (inv[i].l >= l && inv[i].r <= r) {
            inv[i].v /= v;
        }
    }
}
inline void calcover(int l, int r, int v) {
    for (int i = 1; i <= m; i++) {
        if (inv[i].l >= l && inv[i].r <= r) {
            inv[i].v = v;
        }
    }
}
inline void merge(void) {
    int t = 1;
    for (int i = 2; i <= m; i++) {
        if (inv[i].v != inv[t].v) {
            inv[++t] = inv[i];
        } else {
            inv[t].r = inv[i].r;
        }
    }
    for (int i = 1; i <= t; i++) {
        ins(inv[i]);
    }
}
inline void divi(int l, int r, int v) {
    split(l, r);
    calcdivi(l, r, v);
    merge();
}
inline void cover(int l, int r, int v) {
    split(l, r);
    calcover(l, r, v);
    merge();
}
inline long long sum(int l, int r) {
    return (r + 1) * A.sum(r) - B.sum(r) - l * A.sum(l - 1) + B.sum(l - 1);
}
int main() {
    cin >> n >> q;
    m = n;
    for (int i = 1; i <= n; i++) {
        cin >> inv[i].v;
        inv[i].l = inv[i].r = i;
    }
    merge();
    while (q--) {
        int o;
        cin >> o;
        switch (o) {
            case 1: {
                int l, r, v;
                cin >> l >> r >> v;
                divi(l, r, v);
                break;
            }
            case 2: {
                int l, r, v;
                cin >> l >> r >> v;
                cover(l, r, v);
                break;
            }
            case 3: {
                int l, r;
                cin >> l >> r;
                cout << sum(l, r) << endl;
                break;
            }
        }
    }
}