博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
BZOJ 1798:
阅读量:5332 次
发布时间:2019-06-14

本文共 2645 字,大约阅读时间需要 8 分钟。

6:
      LAZY 线段树有乘法的更新
   #include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
const int maxn = 101000;
long long value[maxn], mod;
struct SegNode {
    int left, right;
    long long sum, add, mul;
    int mid() {
        return (left + right) >> 1;
    }
    int size() {
        return right - left + 1;
    }
};
struct SegmentTree {
    SegNode tree[maxn*5];
    void pushUp(int idx) {
        tree[idx].sum = (tree[idx<<1].sum + tree[idx<<1|1].sum) % mod;
    }
    void pushDown(int idx) {
        tree[idx<<1].add = (tree[idx].mul % mod * tree[idx<<1].add % mod + tree[idx].add) % mod;
        tree[idx<<1|1].add = (tree[idx].mul % mod * tree[idx<<1|1].add % mod + tree[idx].add) % mod;
        tree[idx<<1].mul = tree[idx<<1].mul % mod * tree[idx].mul % mod;
        tree[idx<<1|1].mul = tree[idx<<1|1].mul % mod * tree[idx].mul % mod;
        tree[idx<<1].sum = (tree[idx<<1].sum % mod * tree[idx].mul % mod
            + tree[idx<<1].size() * tree[idx].add % mod) % mod;
        tree[idx<<1|1].sum = (tree[idx<<1|1].sum % mod * tree[idx].mul % mod
            + tree[idx<<1|1].size() * tree[idx].add % mod) % mod;
        tree[idx].add = 0;
        tree[idx].mul = 1;
    }
    void build(int left, int right, int idx) {
        tree[idx].left = left;
        tree[idx].right = right;
        tree[idx].sum = 0;
        tree[idx].mul = 1;
        tree[idx].add = 0;
        if (left == right) {
            tree[idx].sum = value[left] % mod;
            return ;
        }
        int mid = tree[idx].mid();
        build(left, mid, idx<<1);
        build(mid+1, right, idx<<1|1);
        pushUp(idx);
    }
    void update(int left, int right, int idx, int opt, long long val) {
        if (tree[idx].left == left && tree[idx].right == right) {
            if (opt == 1) {
                tree[idx].add = (tree[idx].add + val) % mod;
                tree[idx].sum = (tree[idx].sum + tree[idx].size() % mod * val) % mod;
            } else {
                tree[idx].add = tree[idx].add % mod * val % mod;
                tree[idx].mul = tree[idx].mul % mod * val % mod;
                tree[idx].sum = tree[idx].sum % mod * val % mod;
            }
            return ;
        }
        pushDown(idx);
        int mid = tree[idx].mid();
        if (right <= mid)
            update(left, right, idx<<1, opt, val);
        else if (left > mid)
            update(left, right, idx<<1|1, opt, val);
        else {
            update(left, mid, idx<<1, opt, val);
            update(mid+1, right, idx<<1|1, opt, val);
        }
        pushUp(idx);
    }
    long long query(int left, int right, int idx) {
        if (tree[idx].left == left && tree[idx].right == right) {
            return tree[idx].sum % mod;
        }
        pushDown(idx);
        int mid = tree[idx].mid();
        if (right <= mid)
            return query(left, right, idx<<1);
        else if (left > mid)
            return query(left, right, idx<<1|1);
        else {
            return (query(left, mid, idx<<1) % mod + query(mid+1, right, idx<<1|1));
        }
    }
};
SegmentTree tree;
int n, m;
void init() {
    scanf("%d %lld", &n, &mod);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &value[i]);
    tree.build(1, n, 1);
}

转载于:https://www.cnblogs.com/forgot93/p/4275872.html

你可能感兴趣的文章
AutoCompleteTextView的用法
查看>>
keepalive专题
查看>>
WebServer
查看>>
Dubbo源码分析:Invoker
查看>>
Leetcode 1. Two Sum
查看>>
Leetcode 111. Minimum Depth of Binary Tree
查看>>
saltstack学习-6:文件系统
查看>>
**leetcode笔记--4 Sum of Two Integers
查看>>
SSM命名规范框架
查看>>
2018.10.25 bzoj4350: 括号序列再战猪猪侠(区间dp)
查看>>
JXU1NDRBJXU0RTJBJXU1MjJCJXU1NDI3
查看>>
程序集与托管模块的概念(转)
查看>>
网站seo怎么做
查看>>
并发编程之队列
查看>>
Android上解析Json格式数据
查看>>
mysql的相关命令整理
查看>>
hdu5909 Tree Cutting 【树形dp + FWT】
查看>>
欧拉项目第四题之三位数之积数的最大回数
查看>>
Codeforces Round #482 (Div. 2) B、Treasure Hunt(模拟+贪心)979B
查看>>
overflow :scroll在IOS上很卡的解决方案
查看>>