[HDU][1698][线段树] Just a Hook

题目大意：

一个长度为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].rightright||tree[root].right

由于题目中给出了序列元素均初始化为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

发表回复取消回复