某个英雄有这样一个金属长棍,这个金属棍有很多相同长度的短棍组成,大概最多有10w节,现在这个人有一种魔法,他可以把一段区间的金属棍改变成别的物质,例如金银或者铜, 现在他会有一些操作在这个金属棍上,他想知道这些操作结束后金属棍的质量是多少呢?(PS,一节铜重量1, 银 2 ,金3)。
分析:如果做了那到海报覆盖的题目会发现这两题是差不多的,都可以从后面往前去覆盖,只不过返回这次能覆盖多少节就行了。
*************************************************************************
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define Lson root<<1,L,tree[root].Mid()
#define Rson root<<1|1,tree[root].Mid()+1,R const int maxn = ; struct Hook{int l, r, z;}hook[maxn];
struct Tree{
int L, R;
int isCover;//等于1的时候被覆盖,等于2的时候区间下面有被覆盖的
int Mid(){return (L+R)/;}
int Len(){return (R-L+);}
}tree[maxn*]; void Build(int root, int L, int R)
{
tree[root].L = L, tree[root].R = R;
tree[root].isCover = false; if(L == R)return ; Build(Lson);
Build(Rson);
}
void Up(int root)
{
if(tree[root].L != tree[root].R)
if(tree[root<<].isCover == && tree[root<<|].isCover == )
tree[root].isCover = ;
}
int Insert(int root, int L, int R)
{
if(tree[root].isCover == )return ; if(tree[root].L == L && tree[root].R == R && !tree[root].isCover)
{
tree[root].isCover = ;
return tree[root].Len();
}
tree[root].isCover = ; int ans = ; if(R <= tree[root].Mid())
ans = Insert(root<<, L, R);
else if(L > tree[root].Mid())
ans = Insert(root<<|, L, R);
else
ans = Insert(Lson)+Insert(Rson); Up(root); return ans;
} int main()
{
int i, T, t=; scanf("%d", &T); while(T--)
{
int N, M; scanf("%d%d", &N, &M);
Build(, , N); for(i=; i<=M; i++)
scanf("%d%d%d", &hook[i].l, &hook[i].r, &hook[i].z); int ans = N; for(i=M; i>; i--)
{
int len = Insert(, hook[i].l, hook[i].r);
ans = ans - len + len * hook[i].z;
} printf("Case %d: The total value of the hook is %d.\n", t++, ans);
} return ; }