HDU 1698 Just a Hook [线段树+区间修改为一个值+区间查询]

题目传送门

一、经验总结

  • \(HDU\) 是杭州电子科技大学的简称，\(POJ\)是北京大学\(OJ\)简称
  • 因读入量较大，使用cin读入直接TLE，换用scanf后AC，看来能用scanf最好以后用scanf!
  • \(HDU\)和\(POJ\)不支持万能头文件，需要小心替换库文件

二、题目理解

给你一个长 \(n\) 的序列，初始值全为 \(1\) ，\(q\) 次操作，每次将 \([ x, y ]\) 的值改为 \(z\) ，问最后整个序列的和为多少?

三、实现代码

//#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long LL;
const int N = 100000 + 10;
int n, q;
struct node {
    int l, r;
    LL sum;
    int add;
} tr[N << 2];

//更新父节点的区间和
void pushup(int u) {
    tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}

/**
 * @brief 向下更新懒标记
 *
 * @param u 以u为根节点
 */
void pushdown(int u) {
    auto &root = tr[u], &left = tr[u << 1], &right = tr[u << 1 | 1];
    if (root.add) { //如果存在需要更新的数据
        left.add = root.add, left.sum = (LL)(left.r - left.l + 1) * root.add;
        right.add = root.add, right.sum = (LL)(right.r - right.l + 1) * root.add;
        root.add = 0; //别忘了清除懒标记
    }
}
void bulid(int u, int l, int r) {
    tr[u] = {l, r}; //不要忘记yxc的上课教训~
    if (l == r) {
        tr[u].sum = 1; //初始区间每个值都是1,因为有可能某些区间是没有被修改过的，需要有初始值
        return;
    }
    int mid = l + r >> 1;
    bulid(u << 1, l, mid);
    bulid(u << 1 | 1, mid + 1, r);
    //更新父节点的信息
    pushup(u);
}

/**
 * @brief 修改区间l,r之间的值为v
 *
 * @param u 以u节点为根进行查询修改
 * @param l 要修改的左区间
 * @param r 要修改的右区间
 * @param v 要修改的值
 */
void modify(int u, int l, int r, int v) {
    if (l <= tr[u].l && tr[u].r <= r) {              //[l,r]包含了u的范围
        tr[u].sum = (LL)v * (tr[u].r - tr[u].l + 1); //范围长度 * 范围内每个数字的值v
        tr[u].add = v;                               //把v这个值，直接放在u节点上，不下传，真懒~
        return;
    }
    int mid = tr[u].l + tr[u].r >> 1;         //中间点
    pushdown(u);                              //下传lazy tag
    if (l <= mid) modify(u << 1, l, r, v);    //修改左儿子
    if (r > mid) modify(u << 1 | 1, l, r, v); //修改右儿子
    pushup(u);                                //因为左右儿子数据的变更，需要再次向上更新父节点信息
}

/**
 * @brief 查询区间加法和
 *
 * @param u 以u为根
 * @param l 区间左端点
 * @param r 区间右端点
 * @return LL 区间和
 */
LL query(int u, int l, int r) {
    if (l <= tr[u].l && tr[u].r <= r) return tr[u].sum; //在区间内
    //更新懒标记
    pushdown(u);
    //拼接左右的结果
    LL ans = 0;
    int mid = tr[u].l + tr[u].r >> 1;
    if (l <= mid) ans += query(u << 1, l, r);
    if (r > mid) ans += query(u << 1 | 1, l, r);
    return ans;
}

int main() {
    int T;
    scanf("%d", &T);
    int cas = 1;
    while (T--) {
        scanf("%d", &n);          // 线段的区间[1~n]
        memset(tr, 0, sizeof tr); //因树状数组多次使用，每次需要清空
        bulid(1, 1, n);           //构建树状数组

        scanf("%d", &q);
        while (q--) {
            int x, y, v;
            scanf("%d%d%d", &x, &y, &v);
            modify(1, x, y, v);
        }
        printf("Case %d: The total value of the hook is %lld.\n", cas++, query(1, 1, n));
    }
    return 0;
}
线段树

相关

#直径，线段树#51nod 1766 树上的最远点对

「NOI2020」命运（树形DP+线段树合并）

线段树学习笔记 1

关于 线段树 的一些认识

线段树

[NOI2015]软件包管理器（巧用线段树）

P6242 【模板】线段树 3

P5494 【模板】线段树分裂

CF1557D Ezzat and Grid（线段树）

cf739 C. Alyona and towers（线段树）

可持久化线段树

Codeforces Round #625 Div1 C,二维偏序，排序+线段树

标签