题意：给你个n，表示区间【1，n】，价值初始为1，给你m段区间和价值，更新区间，区间价值以最后更新为准，问更新后区间价值总和为多少
思路：两种方法，可以先存下来，倒过来更新，一更新节点马上跳出，比较快
线段树
#include <iostream>
using namespace std;
int data[100005][3];
int main()
{
int t,q,n,i,j,sum,k,v;
scanf("%d",&t);
for(i=1;i<=t;i++)
{
scanf("%d%d",&n,&q);
for(j=1;j<=q;j++)
scanf("%d%d%d",&data[j][0],&data[j][1],&data[j][2]);
sum=0;
for(k=1;k<=n;k++)
{
v=1;
for(j=q;j>=1;j--)
if(data[j][0]<=k && k<=data[j][1])//寻找k所在的更新区间，若存在则更新
{
v=data[j][2]; //若找的最后面的更新区间，则停止
break;
}
sum+=v;
}
printf("Case %d: The total value of the hook is %d.\n",i,sum);
}
return 0;
}
#include <iostream>
#include<cstdio>
using namespace std;
#define N 300010
struct node{
int value;
int l,r;
}tree[N];
void Build(int l,int r,int id){
tree[id].l=l;
tree[id].r=r;
tree[id].value=1;
if(l!=r){
int mid=(l+r)>>1;
Build(l,mid,id<<1);
Build(mid+1,r,id<<1|1);
}
}
void update(int l,int r,int value,int id){
int mid=(tree[id].l+tree[id].r)>>1;
if(tree[id].l==l&&tree[id].r==r){
tree[id].value=value;
return;
}
if(tree[id].value==value)
return;
if(tree[id].value!=-1){
tree[id<<1].value=tree[id<<1|1].value=tree[id].value;
tree[id].value=-1;
}
if(r<=mid)
update(l,r,value,id<<1);
else if(l>mid)
update(l,r,value,id<<1|1);
else{
update(l,mid,value,id<<1);
update(mid+1,r,value,id<<1|1);
}
}
int query(int id){
if(tree[id].value!=-1)
return (tree[id].r-tree[id].l+1)*tree[id].value;
return query(id<<1)+query(id<<1|1);
}
int main(int argc, char** argv) {
int t,n,m,x,y,k,Cas=1;
scanf("%d",&t);
while(t--){
scanf("%d",&n);
Build(1,n,1);
scanf("%d",&m);
while(m--){
scanf("%d%d%d",&x,&y,&k);
update(x,y,k,1);
}
printf("Case %d: The total value of the hook is %d.\n",Cas++,query(1));
}
return 0;
}