区间修改,区间求和
题意
给定$n$个点,初值都为$1$,每次操作要么将某个区间的值都赋为1或2或3,要么查询某个区间的和。(带懒标记的模板题)
#include <iostream>
#define lc u << 1
#define rc u << 1 | 1
using namespace std;
const int N = 100010;
struct Node{
int l, r, s, add;
}tr[N << 2];
int turn;
void pushup (int u) { tr[u].s = tr[lc].s + tr[rc].s; }
void pushdown (int u)
{
if (tr[u].add)
{
int &x = tr[u].add;
tr[lc].add = tr[rc].add = x;
tr[lc].s = (tr[lc].r - tr[lc].l + 1) * x;
tr[rc].s = (tr[rc].r - tr[rc].l + 1) * x;
x = 0;
}
}
void build (int u, int l, int r)
{
tr[u] = {l, r, 0, 0};
if (l == r) { tr[u].s = 1; return; }
int mid = l + r >> 1;
build (lc, l, mid), build (rc, mid + 1, r);
pushup (u);
}
void modify (int u, int l, int r, int c)
{
if (tr[u].l >= l && tr[u].r <= r) tr[u].s = (tr[u].r - tr[u].l + 1) * c, tr[u].add = c;
else
{
pushdown (u);
int mid = tr[u].l + tr[u].r >> 1;
if (l <= mid) modify (lc, l, r, c);
if (r > mid) modify (rc, l, r, c);
pushup (u);
}
}
int query (int u, int l, int r)
{
if (tr[u].l >= l && tr[u].r <= r) return tr[u].s;
int mid = tr[u].l + tr[u].r >> 1;
int res = 0;
pushdown (u);
if (l <= mid) res = query (lc, l, r);
if (r > mid) res += query (rc, l, r);
return res;
}
void solve()
{
int n;
cin >> n;
build (1, 1, n);
int m;
cin >> m;
while (m--)
{
int l, r, c;
cin >> l >> r >> c;
modify (1, l, r, c);
}
cout << "Case " << turn << ": The total value of the hook is " << query (1, 1, n) << "." << endl;
}
int main()
{
ios::sync_with_stdio(0);
int T = 1;
cin >> T;
for(turn = 1 ; turn <= T ; turn++)
solve();
}