在 DotA 游戏中，帕吉的肉钩是很多英雄最害怕的东西。钩子由连续若干段的等长金属棒制成。
现在帕吉对钩子由一些操作：
我们将金属棒 1 ~ n 依次编号，帕吉可以把编号 x~y 的金属棒变成铜棒、银棒、金棒。
每段铜棒的价值是 1；每段银棒的价值是 2；每段金棒的价值是 3。
肉钩的总价值是 n 段金属棒价值之和。
帕吉想知道若干操作以后钩子的总价值。
输入格式
第一行一个整数 N（1≤N≤10^5），表示肉钩金属棒的数量，初始状态为 铜棒。
第二行一个整数 Q（1≤Q≤10^5 ），表示操作数。
接下来 Q 行，一行三个整数，X,Y,Z(1≤X≤Y≤N,1≤Z≤3)。
输出格式
一行一个整数，表示钩子的总价值，用样例中的格式。
样例输入复制
10
2
1 5 2
5 9 3
样例输出复制
The total value of the hook is 24.
#include
using namespace std;
const int MAX_N = 100001;
int s[4 * MAX_N], col[4 * MAX_N];
void up(int p) {
s[p] = s[2 * p] + s[2 * p + 1];
}
void down(int p, int l, int r) {
if (col[p]) {
int mid = (l + r) / 2;
s[2 * p] = col[p] * (mid - l + 1);
s[2 * p + 1] = col[p] * (r - mid);
col[2 * p] = col[p];
col[2 * p + 1] = col[p];
col[p] = 0;
}
}
void modify(int p, int l, int r, int x, int y, int c) {
if (l >= x && r <= y) {
s[p] = (r - l + 1) * c;
col[p] = c;
return;
}
down(p, l, r);
int mid = (r + l) / 2;
if (x <= mid)
modify(2 * p, l, mid, x, y, c);
if (y > mid)
modify(2 * p + 1, mid + 1, r, x, y, c);
up(p);
}
int query(int p, int l, int r, int x, int y) {
if (l >= x && r <= y)
return s[p];
down(p, l, r);
int res = 0, mid = (l + r) / 2;
if (x <= mid)
res += query(2 * p, l, mid, x, y);
if (y > mid)
res += query(2 * p + 1, mid + 1, r, x, y);
return res;
}
int main() {
int n, q;
cin >> n;
cin >> q;
for (int i = 1; i <= n; i++)
modify(1, 1, n, i, i, 1);
while (q--) {
int x, y, z;
cin >> x >> y >> z;
modify(1, 1, n, x, y, z);
}
cout << "The total value of the hook is " << query(1, 1, n, 1, n) << '.';
return 0;
}