python/TangDou/AcWing/SegmentTree/CF444C.md

DZY Loves Colors

一、题面翻译

有一个 n 个元素组成的序列，每个元素有两个属性：颜色 c_i 和权值w_i。c_i 初始为i，w_i初始为 0。

m 次操作，操作有两种：

• 1 l r x：对i \in [l,r] 的所有 i 进行如下操作：设第 i 个元素 原来 的颜色为 y，您要把第 i 个元素的颜色改为 x，权值 增加 |y-x|。

• 2 l r：求 \displaystyle \sum_{i=l}^rw_i。

• 1 \le n,m \le 10^5,1 \le x \le 10^8

二、题目解析

• ① 修改涉及到绝对值，可以通过判断区间内的数是否全部相等再进行区间操作,区间内的数是否全部相等用属性标签same表示
• ② 通过懒标记 same 判断该区间的所有颜色是否都相等，相等时就可以将懒标记下传，更新add
• ③ 递归出口：递归到叶子时，叶子一定满足tr[u].same=color[i]>0,每次我们修改时候对相同的颜色段修改，不相同的颜色段递归暴力修改
• ④ 本题不是一道标准的懒标记题目，而是一个类似于魔改的懒标记题目：根据区间上的属性决定是否在区间上进行统计、打懒标记标签，如果不符合，就递归到叶子,暴力统计

三、实现代码

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

const int N = 500010;

#define int long long
#define mid ((l + r) >> 1)
#define ls (u << 1)
#define rs (u << 1 | 1)
struct Node {
    int l, r, len;
    int sum;  // 属性：权值的和 sum(Wi)
    int same; // 属性：区间的颜色值是否相同，如果相同，记录颜色值为same,注意：颜色值从1开始,最大是n
    int add;  // 懒标记:增加
} tr[N << 2];

void pushup(int u) {
    tr[u].sum = tr[ls].sum + tr[rs].sum; // 属性1:Wi权值和
    if (tr[ls].same == tr[rs].same)      // 属性2:same属性。如果左右儿子的same属性一致，则父亲的same属性标注为左儿子的same属性
        tr[u].same = tr[ls].same;
    else
        tr[u].same = 0;
    // 注意：这个else中的same属性也一定要清零！原来是左右儿子一致，再次修改后就不一致，那么父亲需要标记不一致
    // 这个和初始值为0没有任何关系，最初我还以为不需要加上这句，后来想想不对，这是一个动态变化的过程，需要及时清零
}

void pushdown(int u) {
    if (tr[u].same) { // 如果存在add懒标记，并且整个区间是一样的值
        tr[ls].sum += tr[ls].len * tr[u].add;
        tr[rs].sum += tr[rs].len * tr[u].add;
        tr[ls].add += tr[u].add;
        tr[rs].add += tr[u].add;
        tr[ls].same = tr[u].same;
        tr[rs].same = tr[u].same;
        tr[u].add = 0;
    }
}

void build(int u, int l, int r) {
    tr[u].l = l, tr[u].r = r, tr[u].len = r - l + 1;
    if (l == r) {
        tr[u].same = l; // 颜色值Ci,初始值为i,对于叶子而言i即是l
        return;
    }
    build(ls, l, mid), build(rs, mid + 1, r);
    pushup(u);
}

void modify(int u, int L, int R, int v) {
    int l = tr[u].l, r = tr[u].r;
    if (l > R || r < L) return;

    if (l >= L && r <= R && tr[u].same) {
        tr[u].sum += tr[u].len * abs(v - tr[u].same);
        tr[u].add += abs(v - tr[u].same);
        tr[u].same = v;
        return;
    }
    pushdown(u);
    modify(ls, L, R, v), modify(rs, L, R, v);
    pushup(u);
}

int query(int u, int L, int R) {
    int l = tr[u].l, r = tr[u].r;
    if (l >= L && r <= R) return tr[u].sum;
    if (l > R || r < L) return 0;

    pushdown(u);
    return query(ls, L, R) + query(rs, L, R);
}

signed main() {
#ifndef ONLINE_JUDGE
    freopen("CF444C.in", "r", stdin);
#endif
    // 加快读入
    ios::sync_with_stdio(false), cin.tie(0);
    int n, m, op;
    cin >> n >> m;

    // n个元素，构建线段树
    build(1, 1, n);

    while (m--) {
        int op;
        cin >> op;
        if (op == 1) {
            int l, r, x;
            cin >> l >> r >> x;
            modify(1, l, r, x); // 区间修改为x
        } else if (op == 2) {
            int l, r;
            cin >> l >> r;
            cout << query(1, l, r) << endl;
        }
    }
    return 0;
}