题目大意：
一个长度为n的序列，初始化序列中的元素为1。接下来执行Q次更新操作，每次操作将区间[x,y]上的值更新为z。所有操作结束后，求出序列的总和。
思路：
成段更新的线段树的模板题。
代码：
因为之前没有做过成段更新的线段树，所以这次依据此题做出模板，下面是模板代码。
#include
#include
using namespace std;
#define MAXSIZE 100000
int val[MAXSIZE+1];
struct node
{
int total;
//区间属性，这里是total，表示区间元素和。
int left;
int right;
int mark;
//mark表示延迟标记
}tree[MAXSIZE*3];
int create(int root,int left,int right)
//以root为根节点建树。
{
tree[root].mark=0;
tree[root].left=left;
tree[root].right=right;
if(left==right)
return tree[root].total=val[left];
int middle=(left+right)/2;
return tree[root].total=create(2*root,left,middle)+create(2*root+1,middle+1,right);
}
void updata_mark(int root)
//更新root的子节点的延迟标记。
{
if(tree[root].mark)
{
tree[root].total=tree[root].mark*(tree[root].right-tree[root].left+1);
if(tree[root].left!=tree[root].right)
tree[root*2].mark=tree[root*2+1].mark=tree[root].mark;
tree[root].mark=0;
}
}
int calculate(int root,int left,int right)
//以root为根节点的线段树中，求取区间[left,right]的元素和。
{
updata_mark(root);
if(tree[root].left>right||tree[root].right<left)
return 0;
if(left<=tree[root].left&&tree[root].rightright||tree[root].right<left)
return tree[root].total;
if(left<=tree[root].left&&tree[root].right<=right)
{
tree[root].mark=val;
return tree[root].total=val*(tree[root].right-tree[root].left+1);
}
return tree[root].total=updata(2*root,left,right,val)+updata(2*root+1,left,right,val);
}
int main()
{
int t;
scanf("%d",&t);
for(int i=1,n,q;i<=t;i++)
{
scanf("%d%d",&n,&q);
for(int j=1;j<=n;j++)
val[j]=1;
create(1,1,n);
for(int j=0,x,y,z;j<q;j++)
{
scanf("%d%d%d",&x,&y,&z);
updata(1,x,y,z);
}
printf("Case %d: The total value of the hook is %d.\n",i,calculate(1,1,n));
}
}
由于题目中给出了序列元素均初始化为1以及只需考虑序列总和等条件，针对本题对代码进行精简，主要是除去了calculate()函数和val[]数组。
#include
#include
using namespace std;
#define MAXSIZE 100000
struct node
{
int total;
int left;
int right;
int mark;
}tree[MAXSIZE*3];
int create(int root,int left,int right)
{
tree[root].mark=0;
tree[root].left=left;
tree[root].right=right;
if(left==right)
return tree[root].total=1;
int middle=(left+right)/2;
return tree[root].total=create(2*root,left,middle)+create(2*root+1,middle+1,right);
}
void updata_mark(int root)
{
if(tree[root].mark)
{
tree[root].total=tree[root].mark*(tree[root].right-tree[root].left+1);
if(tree[root].left!=tree[root].right)
tree[root*2].mark=tree[root*2+1].mark=tree[root].mark;
tree[root].mark=0;
}
}
int updata(int root,int left,int right,int val)
{
updata_mark(root);
if(tree[root].left>right||tree[root].right<left)
return tree[root].total;
if(left<=tree[root].left&&tree[root].right<=right)
{
tree[root].mark=val;
return tree[root].total=val*(tree[root].right-tree[root].left+1);
}
return tree[root].total=updata(2*root,left,right,val)+updata(2*root+1,left,right,val);
}
int main()
{
int t;
scanf("%d",&t);
for(int i=1,n,q;i<=t;i++)
{
scanf("%d%d",&n,&q);
create(1,1,n);
for(int j=0,x,y,z;j<q;j++)
{
scanf("%d%d%d",&x,&y,&z);
updata(1,x,y,z);
}
printf("Case %d: The total value of the hook is %d.\n",i,tree[1].total);
}
}