应该算简单的一种！！
#include<iostream>
using namespace std;
const int NO = -1;
const int N=100000;
int n,Q;
struct seg_tree
{
int l,r;
int tag;
}tree[4*N];
void make_tree(int cnt,int left,int right)
{
tree[cnt].l = left;
tree[cnt].r = right;
tree[cnt].tag = 1;
if(left+1 == right)
return ;
int mid = (left + right) / 2;
make_tree(2*cnt,left,mid);
make_tree(2*cnt+1,mid,right);
}
void updata(int cnt,int left,int right,int flag)
{
if(tree[cnt].tag == flag)
return;
if(left==tree[cnt].l && right == tree[cnt].r)
{
tree[cnt].tag = flag;
return ;
}
if(tree[cnt].tag != NO)
{
tree[2*cnt].tag = tree[cnt].tag;
tree[2*cnt+1].tag = tree[cnt].tag;
}
tree[cnt].tag = NO;
int mid = (tree[cnt].l+tree[cnt].r) / 2;
if(mid<=left)
updata(cnt*2+1,left,right,flag);
else if(mid>=right)
updata(cnt*2,left,right,flag);
else
{
updata(cnt*2,left,mid,flag);
updata(cnt*2+1,mid,right,flag);
}
}
int find_ans(int cnt,int left,int right)
{
if(tree[cnt].tag != NO)
return (tree[cnt].r-tree[cnt].l) * tree[cnt].tag;
int mid = (left + right)/2;
return find_ans(cnt*2,left,mid) + find_ans(cnt*2+1,mid,right);
}
int main()
{
int cas;
int i,j,k;
cin >> cas;
for(k=1;k<=cas;k++)
{
cin >> n >>Q;
make_tree(1,1,n+1);
int beg,end,flag;
while(Q--)
{
scanf("%d %d %d",&beg,&end,&flag);
updata(1,beg,end+1,flag);
}
printf("Case %d: The total value of the hook is %d./n",k,find_ans(1,1,n+1) );
}
return 0;
}