Skip to content

Codeforces - 444C. DZY Loves Colors

题解约 1.2 千字
# 数据结构 # 线段树 # Codeforces
检测到 KaTeX 加载失败，可能会导致文中的数学公式无法正常渲染。

#题面

#题目描述

DZY loves colors, and he enjoys painting.

On a colorful day, DZY gets a colorful ribbon, which consists of nn units (they are numbered from 11 to nn from left to right). The color of the ii -th unit of the ribbon is ii at first. It is colorful enough, but we still consider that the colorfulness of each unit is 00 at first.

DZY loves painting, we know. He takes up a paintbrush with color xx and uses it to draw a line on the ribbon. In such a case some contiguous units are painted. Imagine that the color of unit ii currently is yy. When it is painted by this paintbrush, the color of the unit becomes xx, and the colorfulness of the unit increases by ∣x−y∣|x - y|.

DZY wants to perform mm operations, each operation can be one of the following:

  1. Paint all the units with numbers between ll and rr (both inclusive) with color xx.
  2. Ask the sum of colorfulness of the units between ll and rr (both inclusive).

Can you help DZY?

#输入格式

The first line contains two space-separated integers n,mn, m (1≤n,m≤1051 \leq n, m \leq 10^{5}).

Each of the next mm lines begins with a integer type\mathrm{type} (type∈{1,2}\mathrm{type} \in \{1, 2\}), which represents the type of this operation.

If type=1\mathrm{type} = 1 , there will be 33 more integers l,r,xl, r, x (1≤l≤r≤n1 \leq l \leq r \leq n; 1≤x≤1081 \leq x \leq 10^{8}) in this line, describing an operation 11.

If type=2\mathrm{type} = 2 , there will be 22 more integers l,rl, r (1≤l≤r≤n1 \leq l \leq r \leq n) in this line, describing an operation 22.

#输出格式

For each operation 22, print a line containing the answer — sum of colorfulness.

#输入输出样例

样例输入 #1

3 3
1 1 2 4
1 2 3 5
2 1 3

样例输出 #1

8

样例解释 #1

In the first sample, the color of each unit is initially [1,2,3][1, 2, 3], and the colorfulness is [0,0,0][0, 0, 0].

After the first operation, colors become [4,4,3][4, 4, 3], colorfulness become [3,2,0][3, 2, 0].

After the second operation, colors become [4,5,5][4, 5, 5], colorfulness become [3,3,2][3, 3, 2].

So the answer to the only operation of type 22 is 88.

样例输入 #2

3 4
1 1 3 4
2 1 1
2 2 2
2 3 3

样例输出 #2

3
2
1

样例输入 #3

10 6
1 1 5 3
1 2 7 9
1 10 10 11
1 3 8 12
1 1 10 3
2 1 10

样例输出 #3

129

#思路

可以考虑使用线段树维护区间权值和以及区间/节点颜色。每次修改是直接修改颜色相同的区间，对于区间内颜色不同的则暴力递归修改，暴力修改的次数至多为 n+2mn + 2m 次。时间复杂度为 O(mlog⁡n)O(m \log n)，可以通过本题。

在代码中为了节省内存空间，若区间内颜色不同则线段树上表示该区间的节点的颜色值为 −1-1，若区间内颜色相同则颜色值为对应值。

#代码

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
#include <iostream>
#include <cmath>

using std::cin;
using std::cout;
const char endl = '\n';

struct node {
    int l, r;
    int color, new_color;
    long long sum, sum_delta;
    node *lchild, *rchild;

    node()
        : l(0), r(0), color(-1), new_color(-1), sum(0), sum_delta(0), lchild(nullptr), rchild(nullptr) {}

    node(int _l, int _r)
        : l(_l), r(_r), color(-1), new_color(-1), sum(0), sum_delta(0), lchild(nullptr), rchild(nullptr) {}

    ~node() {
        delete lchild;
        delete rchild;
    }

    void pushup() {
        sum = 0;
        color = -1;

        if (lchild != nullptr) {
            sum += lchild->sum;
            color = lchild->color;
        }

        if (rchild != nullptr) {
            sum += rchild->sum;
            color = color == rchild->color ? color : -1;
        }
    }

    void pushdown() {
        if (new_color == -1 || sum_delta == 0) return;

        if (lchild != nullptr) {
            if (sum_delta) {
                lchild->sum_delta += sum_delta;
                lchild->sum += sum_delta * (lchild->r - lchild->l + 1);
            }

            if (new_color != -1) {
                lchild->color = lchild->new_color = new_color;
            }
        }

        if (rchild != nullptr) {
            if (sum_delta) {
                rchild->sum_delta += sum_delta;
                rchild->sum += sum_delta * (rchild->r - rchild->l + 1);
            }

            if (new_color != -1) {
                rchild->color = rchild->new_color = new_color;
            }
        }

        new_color = -1;
        sum_delta = 0;
    }
};

void build(node *&u, int l, int r) {
    u = new node(l, r);

    if (l == r) {
        u->color = l;

        return;
    }

    int mid = (l + r) >> 1;

    if (l <= mid) build(u->lchild, l, mid);
    if (r > mid) build(u->rchild, mid + 1, r);

    u->pushup();
}

void modify(node *u, int l, int r, int new_color) {
    if (l <= u->l && u->r <= r && ~u->color) {
        u->sum += static_cast<long long>(std::abs(u->color - new_color)) * (u->r - u->l + 1);
        u->sum_delta += std::abs(u->color - new_color);
        u->color = u->new_color = new_color;

        return;
    }

    int mid = (u->l + u->r) >> 1;
    u->pushdown();

    if (l <= mid) modify(u->lchild, l, r, new_color);
    if (r > mid) modify(u->rchild, l, r, new_color);

    u->pushup();
}

long long query(node *u, int l, int r) {
    if (l <= u->l && u->r <= r) {
        return u->sum;
    }

    int mid = (u->l + u->r) >> 1;
    long long res = 0;

    u->pushdown();

    if (l <= mid) res += query(u->lchild, l, r);
    if (r > mid) res += query(u->rchild, l, r);

    return res;
}

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    node *root;

    cin >> n >> m;

    build(root, 1, n);

    while (m--) {
        int op, l, r;

        cin >> op >> l >> r;

        if (op == 1) {
            int x;

            cin >> x;

            modify(root, l, r, x);
        } else {
            cout << query(root, l, r) << endl;
        }
    }

    delete root;

    return 0;
}