Just a Hook---hdu1698（线段树---区间处理）

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1698

现有n个金属（编号1---n），每个金属的材质都是铜，有m个操作，每个操作都是把编号 L 到 R 区间的金属变成(铜，银，金)三种中的一种，其中三种材质的代号和价值是（铜1，银2，金3）;最后求n个金属的所有价值总和；

#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;#define N 100010
#define MOD 1000000007
#define met(a, b) memset(a, b, sizeof(a))
#define INF 0x3f3f3f3ftypedef long long LL;#define Lson r<<1
#define Rson r<<1|1struct Tree
{
int L, R, sum;
int Mid() { return (L+R)/; }
int len() { return (R-L+); }
}a[N<<];void Build(int r, int L, int R)
{
a[r].L = L , a[r].R = R, a[r].sum = ;
if(L == R)return;
Build(Lson, L, a[r].Mid());
Build(Rson, a[r].Mid()+, R);
}
void Down(int r)
{
if(a[r].sum && a[r].L != a[r].R)
{
a[Lson].sum = a[Rson].sum = a[r].sum;
a[r].sum = ;
}
}void Update(int r, int L, int R, int num)
{
if(a[r].sum == num) return; Down(r); if(a[r].L == L && a[r].R == R)
{
a[r].sum = num;
return;
}
if(R <= a[r].Mid())
Update(Lson, L, R, num);
else if(L > a[r].Mid())
Update(Rson, L, R, num);
else
{
Update(Lson, L, a[r].Mid(), num);
Update(Rson, a[r].Mid()+, R, num);
}
}int Query(int r)
{
if(a[r].sum !=)
return a[r].sum*a[r].len();
int ans = ;
ans += Query(Lson);
ans += Query(Rson);
return ans;
}
int main()
{
int T, n, m, t = ;
scanf("%d", &T);
while(T--)
{
scanf("%d %d", &n, &m);
Build(, , n);
while(m--)
{
int L, R, num;
scanf("%d %d %d", &L, &R, &num);
Update(, L, R, num);
}
int ans = Query();
printf("Case %d: The total value of the hook is %d.\n", t++, ans);
}
return ;
}