202012-5 星际旅行（线段树模板60分）记录一下

2023-05-16

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int maxn = 1e5 + 5;
const ll MOD = 1e9 + 7;

struct Node {
    ll l, r;
    ll x = 0, y = 0, z = 0;
    ll mul = 1;
    ll addx = 0;
    ll addy = 0;
    ll addz = 0;
}tree[maxn << 2];
int n, m;

void buildTree(ll i, ll l, ll r) {
    tree[i].l = l;
    tree[i].r = r;
    if (l == r) {
        return;
    }

    ll mid = l + ((r - l) >> 1);
    ll lef = i << 1, rig = i << 1 | 1;
    buildTree(lef, l, mid);
    buildTree(rig, mid + 1, r);
    tree[i].x = (tree[lef].x + tree[rig].x) % MOD;
    tree[i].y = (tree[lef].y + tree[rig].y) % MOD;
    tree[i].z = (tree[lef].z + tree[rig].z) % MOD;
}

void pushDown(ll rt) {
    ll lef = rt << 1, rig = rt << 1 | 1;
    tree[lef].x = ((tree[rt].mul * tree[lef].x) % MOD + ((tree[lef].r - tree[lef].l + 1) * tree[rt].addx) % MOD) % MOD;
    tree[lef].y = ((tree[rt].mul * tree[lef].y) % MOD + ((tree[lef].r - tree[lef].l + 1) * tree[rt].addy) % MOD) % MOD;
    tree[lef].z = ((tree[rt].mul * tree[lef].z) % MOD + ((tree[lef].r - tree[lef].l + 1) * tree[rt].addz) % MOD) % MOD;

    tree[rig].x = ((tree[rt].mul * tree[rig].x) % MOD + ((tree[rig].r - tree[rig].l + 1) * tree[rt].addx) % MOD) % MOD;
    tree[rig].y = ((tree[rt].mul * tree[rig].y) % MOD + ((tree[rig].r - tree[rig].l + 1) * tree[rt].addy) % MOD) % MOD;
    tree[rig].z = ((tree[rt].mul * tree[rig].z) % MOD + ((tree[rig].r - tree[rig].l + 1) * tree[rt].addz) % MOD) % MOD;

    tree[lef].mul = (tree[rt].mul * tree[lef].mul) % MOD;
    tree[rig].mul = (tree[rt].mul * tree[rig].mul) % MOD;

    tree[lef].addx = ((tree[rt].mul * tree[lef].addx) % MOD + tree[rt].addx) % MOD;
    tree[lef].addy = ((tree[rt].mul * tree[lef].addy) % MOD + tree[rt].addy) % MOD;
    tree[lef].addz = ((tree[rt].mul * tree[lef].addz) % MOD + tree[rt].addz) % MOD;

    tree[rig].addx = ((tree[rt].mul * tree[rig].addx) % MOD + tree[rt].addx) % MOD;
    tree[rig].addy = ((tree[rt].mul * tree[rig].addy) % MOD + tree[rt].addy) % MOD;
    tree[rig].addz = ((tree[rt].mul * tree[rig].addz) % MOD + tree[rt].addz) % MOD;

    tree[rt].addx = 0; tree[rt].mul = 1;
    tree[rt].addy = 0; tree[rt].addz = 0;
}

void add(ll i, ll l, ll r, ll a, ll b, ll c) {
    if (tree[i].l >= l && tree[i].r <= r) {
        tree[i].x = (tree[i].x + a * (tree[i].r - tree[i].l + 1)) % MOD;
        tree[i].y = (tree[i].y + b * (tree[i].r - tree[i].l + 1)) % MOD;
        tree[i].z = (tree[i].z + c * (tree[i].r - tree[i].l + 1)) % MOD;

        tree[i].addx = (tree[i].addx + a) % MOD;
        tree[i].addy = (tree[i].addy + b) % MOD;
        tree[i].addz = (tree[i].addz + c) % MOD;
        return;
    }

    pushDown(i);
    ll lef = i << 1, rig = i << 1 | 1;
    if (tree[lef].r >= l) add(lef, l, r, a, b, c);
    if (tree[rig].l <= r) add(rig, l, r, a, b, c);
    tree[i].x = (tree[lef].x + tree[rig].x) % MOD;
    tree[i].y = (tree[lef].y + tree[rig].y) % MOD;
    tree[i].z = (tree[lef].z + tree[rig].z) % MOD;
}

void multi(ll i, ll l, ll r, ll k) {
    if (tree[i].l >= l && tree[i].r <= r) {
        tree[i].x = (tree[i].x * k) % MOD;
        tree[i].y = (tree[i].y * k) % MOD;
        tree[i].z = (tree[i].z * k) % MOD;

        tree[i].addx = (tree[i].addx * k) % MOD;
        tree[i].addy = (tree[i].addy * k) % MOD;
        tree[i].addz = (tree[i].addz * k) % MOD;
        tree[i].mul = (tree[i].mul * k) % MOD;
        return;
    }

    pushDown(i);
    ll lef = i << 1, rig = i << 1 | 1;
    if (tree[lef].r >= l) multi(lef, l, r, k);
    if (tree[rig].l <= r) multi(rig, l, r, k);
    tree[i].x = (tree[lef].x + tree[rig].x) % MOD;
    tree[i].y = (tree[lef].y + tree[rig].y) % MOD;
    tree[i].z = (tree[lef].z + tree[rig].z) % MOD;
}

ll* search(ll i, ll l, ll r) {
	ll* ans = new ll[3];	// 重点 
	ans[0] = 0; ans[1] = 0; ans[2] = 0;
    if (tree[i].l > r || tree[i].r < l) return ans;
    if (tree[i].l >= l && tree[i].r <= r) {
    	ans[0] = tree[i].x;
		ans[1] = tree[i].y;
		ans[2] = tree[i].z;
		return ans;
	}

    pushDown(i);
    if (tree[i << 1].r >= l) {
        ll* t = search(i << 1, l, r);
        ans[0] = (ans[0] + t[0]) % MOD;
        ans[1] = (ans[1] + t[1]) % MOD;
        ans[2] = (ans[2] + t[2]) % MOD;
    }

    if (tree[i << 1 | 1].l <= r) {
        ll* t = search(i << 1 | 1, l, r);
        ans[0] = (ans[0] + t[0]) % MOD;
        ans[1] = (ans[1] + t[1]) % MOD;
        ans[2] = (ans[2] + t[2]) % MOD;
    }

    return ans;
}

ll calc(ll t[]) {
    return (((t[0] % MOD) * (t[0] % MOD)) % MOD + ((t[1] % MOD) * (t[1] % MOD)) % MOD
        + ((t[2] % MOD) * (t[2] % MOD)) % MOD) % MOD;
}

int main() {
    scanf("%d %d", &n, &m);
    if (n <= 1000 && m <= 1000) {
        ll x[1005] = {0}, y[1005] = {0}, z[1005] = {0};
        int op, l, r; ll k;
        while (m--) {
            scanf("%d%d%d", &op, &l, &r);
            if (op == 1) {
                ll a, b, c;
                scanf("%lld%lld%lld", &a, &b, &c);
                for (int i = l; i <= r; i++) {
                    x[i] = (x[i] + a) % MOD, y[i] = (y[i] + b) % MOD, z[i] = (z[i] + c) % MOD;
                }
            } else if (op == 2) {
                scanf("%lld", &k);
                for (int i = l; i <= r; i++) {
                    x[i] = (x[i] * k) % MOD, y[i] = (y[i] * k) % MOD, z[i] = (z[i] * k) % MOD;
                }
            } else if (op == 3) {
                for (int i = l; i <= r; i++) {
                    swap(x[i], y[i]);
                    swap(y[i], z[i]);
                }
            } else {
                ll X = 0, Y = 0, Z = 0;
                for (int i = l; i <= r; i++) {
                    X = (X + x[i]) % MOD, Y = (Y + y[i]) % MOD, Z = (Z + z[i]) % MOD;
                }
                printf("%lld\n", (X * X % MOD + Y * Y % MOD + Z * Z % MOD) % MOD);
            }
        }
    } else {
    	buildTree(1, 1, n);
	    while (m --) {
	        int op; scanf("%d", &op);
	        if (op == 1) {
	            int l, r, a, b, c;
	            scanf("%d %d %d %d %d", &l, &r, &a, &b, &c);
	            add(1, l, r, a, b, c);
	        } else if (op == 2) {
	            int l, r, k;
	            scanf("%d %d %d", &l, &r, &k);
	            multi(1, l, r, k);
	        } else if (op == 3) {
	            int a, b; scanf("%d %d", &a, &b);
	        } else if (op == 4) {
	            int l, r; scanf("%d %d", &l, &r);
	            ll* t = search(1, l, r);
	            printf("%lld\n", calc(t));
	        }
	    }
	}
    
    return 0;
}

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

202012-5 星际旅行（线段树模板60分）记录一下的相关文章

2021蓝桥杯B组 G题砝码称重

题目大意 xff1a 解法一 xff1a 首先想到的是可以用广度优先搜索的方式来进行暴力求解 xff0c 通过使用递归来将每一种方法遍历 xff0c 并且标记 xff0c 不过由于此方法的时间复杂度是O n3 故使用暴力搜索只能完成50 的
2021蓝桥杯B组第I题杨辉三角形

第I题杨辉三角形题目大意 xff1a 解法一 xff1a xff08 得20 xff09 思路 xff1a 当指考虑小范围的值时 xff0c 我们可以直接根据杨辉三角形的规律 xff1a 第i行第j列的值 61 第i 1行第j列的值 4
Docker--安装Docker和简单使用

1 docker的安装 1 首先先有一台配置高的虚拟机 xff08 至少两核四G xff09 2 按官方文档 Install Docker Engine on CentOS Docker Documentation 删除docker软件包
力扣 1697. 检查边长度限制的路径是否存在

给你一个 n 个点组成的无向图边集 edgeList xff0c 其中 edgeList i 61 ui vi disi 表示点 ui 和点 vi 之间有一条长度为 disi 的边请注意 xff0c 两个点之间可能有超过一条边给你一个
c++stl 学习心得

一 c 43 43 和c的区别 xff1a 1 函数默认值在C 43 43 中我们在定义或声明一个函数的时候 xff0c 有时会在形参中给它赋一个初始值作为不传参数时候的缺省值 xff0c 例如 xff1a int is xff08 in
LeetCode 189.轮转数组（双指针）

题目传送门 xff1a 轮转数组题目详情 xff1a 给你一个数组 xff0c 将数组中的元素向右轮转 k 个位置 xff0c 其中 k 是非负数示例 1 输入 nums 61 1 2 3 4 5 6 7 k 61 3 输出 5 6 7
P1005 [NOIP2007 提高组] 矩阵取数游戏

题目描述帅帅经常跟同学玩一个矩阵取数游戏 xff1a 对于一个给定的 n m 的矩阵 xff0c 矩阵中的每个元素 ai j 均为非负整数游戏规则如下 xff1a 每次取数时须从每行各取走一个元素 xff0c 共 n 个经过 m 次后
C - The Domino Effect（dfs+回溯）

作者 xff1a JF 题目描述一组标准的双六多米诺骨牌包含28块骨牌 xff08 称为骨头 xff09 xff0c 每个骨牌使用类似骰子的点子显示从0 xff08 空白 xff09 到6的两个数字 28块独特的骨骼由以下PIP组合组成
主脑提示（ Master-Mind Hints ）

题目 MasterMind is a game for two players One of them Designer selects a secret code The other Breaker tries to break it A
poj 1068 parencondings

题目描述 xff1a 定义 S 为一个合法的括号字符串 S 可以用以下两种方式编码 xff1a 1 用一个整数数组 P 来表示 xff0c 其中元素 p i 是 S 中每个 39 39 前的 39 39 的个数 xff1b 2 用一个整数数
Linux-USB Gadget : Part 6: dummy hcd 驱动简介

Linux USB Gadget Part 6 dummy hcd 驱动简介作者 xff1a zjujoe 转载请注明出处 Email xff1a zjujoe 64 yahoo com BLOG xff1a http blog csdn
MySQL连接命令

一 MySQL 连接本地数据库 xff0c 用户名为 root xff0c 密码 123 xff08 注意 xff1a p 和 123 之间不能有空格 xff09 C gt mysql h localhost u root p123 二 M
Java数值中加下划线的作用

在看OkHttp源码的时候 xff0c 看到了如下的代码 xff1a int connectTimeout 61 10 000 int readTimeout 61 10 000 int writeTimeout 61 10 000 一时之
docke--制作镜像

镜像库 xff1a http hub docker com 1 为什么要自己制作镜像 xff1f 更加有安全性 xff1b 可以根据自己的需求得到更加合适自己的镜像 2 镜像有什么 xff1f 操作系统核心代码工具库运行时的环境 d
ubuntu虚拟机，可以ping通域名和主机，但是浏览器不能上网

根据nat配置好网络 xff0c 和dns地址后 xff0c 可以ping通域名和主机 xff0c 但是浏览器不能上网 xff0c 花了好大的时间折腾后面发现是谷歌浏览器设置了代理 xff0c 并且在使用时默认使用代理出去 xff0c 如
[OpenCV] aruco Markers识别

reference http docs opencv org 3 1 0 d5 dae tutorial aruco detection html 姿态估计 xff08 Pose estimation xff09 在计算机视觉领域扮演着十分
SELECT command denied to user

root cause org hibernate exception SQLGrammarException could not execute query com mysql jdbc exceptions jdbc4 MySQLSynt
struts2 与 servlet

Struts2 1 过滤规则与 Servlet 之间的微妙关系 2009 05 14 22 06 58 标签 xff1a struts2 servlet 404 访问不到 it 分类 xff1a 网站开发技术学习Struts2也有一段时
select 下拉框--- 根据返回值显示值

lt div align 61 34 left 34 gt lt select name 61 34 personalAssess quality 34 gt lt option value 61 34 34 lt c if test 61
多线程与并发编程

认识多任务多进程单线程多线程要认识多线程就要从操作系统的原理说起以前古老的DOS操作系统 V 6 22 是单任务的 xff0c 还没有线程的概念 xff0c 系统在每次只能做一件事情比如你在copy东西的时候不能rename文件

随机推荐

用户注册信息检查

用户名检查 function checkName var check 61 A Za z0 9 43 var name 61 document getElementById 34 uname 34 value var fo 61 docum
js中对象不支持此属性或方法

一般在ie中执行js会报这样的错误 xff0c 基本问题就是你引用了某个对象中不存在的方法 xff0c 可能是这个方法本来存在而你写错了 xff0c 或者调用这个方法的时候传入了非法的参数 xff0c 但这只是初心造成的 xff0c 还有就
android 五大布局（转）

大家好我们这一节讲一下Android对用五大布局对象它们分别是FrameLayout 框架布局不知道是不是这么翻译的 LinearLayout 线性布局 AbsoluteLayout 绝对布局 RelativeLayout 相对布局
flex校验

package cn newtouch flexDemo business validator import mx binding utils BindingUtils import mx containers FormItem impor
docker--最全的网络类型（7类）

目录 1bridge桥接模式 xff08 默认 xff09 2 host 3 overlay 4 ipvlan 5 macvlan 6 none 7 container 官网有六类 xff1a Networking overview Doc
flex 国际化

Flex 开发 xff08 国际化 xff09 在Flex4 之前默认只支持en US ja JP 这两种本地化 xff0c 因此如果想在Flex 中支持中文或者其他语言时 xff0c 需要额外的操作 xff1a 1 首先添加新的本地化支持
使用mysqladmin命令来修改mysql的root密码

一般mysql的root默认密码为空 xff0c 如果你之前并没有设置过root密码就使用mysqladmin命令 xff0c 你可以使用如下mysqladmin命令来修改root密码 1 2 3 mysqladmin u root p p
CCF化学方程式的配平

include lt iostream gt include lt string gt include lt cctype gt include lt unordered map gt using namespace std unorder
CCF 201909-4 推荐系统

include lt cstdio gt include lt set gt include lt unordered map gt include lt algorithm gt using namespace std typedef l
CCF 201903-4 消息传递接口
Docker学习笔记（一）

Docker学习笔记 xff08 一 xff09 什么是Docker Docker 使用 Google 公司推出的 Go 语言进行开发实现 xff0c 基于 Linux 内核的 cgroup xff0c namespace xff0c 以
Docker学习笔记(二)

Docker镜像 Docker 镜像是一个特殊的文件系统 xff0c 除了提供容器运行时所需的程序库资源配置等文件外 xff0c 还包含了一些为运行时准备的一些配置参数 xff08 如匿名卷环境变量用户等 xff09 Docker
Java多线程里共享变量线程安全问题的原因

Java多线程里共享变量线程安全问题的原因 Java多线程里对于共享变量的操作往往需要考虑进行一定的同步互斥操作 xff0c 原来是因为Java内存模型导致的共享内存对于线程不可见 Java 内存模型规定 xff0c 将所有的变量都存放在主
重构-改善既有代码的设计读书笔记一

重构定义为何重构改进软件设计使软件更容易理解帮助找到Bug提高编程速度何时重构添加功能修改错误复审总而言之 xff0c 当你觉得代码的可读性可维护性可修改性到达一定难以接受的程度 xff0c 就可以开始考虑是否可以使用重
Spring文档学习笔记一

Spring文档学习笔记一目录 Spring文档学习笔记一 Spring的宗旨主要特征几个核心理念 IoC 依赖解析过程 Spring循环依赖的解决方式更详细的得估计得看Spring源码 1 4 2 Dependencies and
python数据结构算法DAY2| 快速排序

目录快速排序 xff08 quick sort xff09 1 什么是快速排序 2 快速排序思路 3 快速排序代码 4快速排序复杂度 5 快速排序函数与冒泡排序的效率比较 6 快速排序的缺点解决办法 xff1a 快速排序 xff08 q
Go里w http.ResponseWriter，调用w.Write()方法报错

Go里w http ResponseWriter写入报错http request method or response status code does not allow 1 下面是报错截图 2 点进去Write方法它首先是一个接口 x
CCF 202012-3 带配额的文件系统练习

大模拟 xff0c 没涉及什么算法主要是数据结构的设计细节的考虑 xff0c 挺锻炼的 xff0c 记录一下 xff0c 代码加了注释 include lt iostream gt include lt string gt include
多接口继承和多层抽象类设计理解

多接口继承和多层抽象类设计理解以JDK集合List框架为例有感以后可能又会有新的理解 xff0c 先记录一下设计得好的接口一般也要遵循单一职责原则 xff0c 最上层的接口一般属于独立的 xff0c 不再有依赖的 xff0c 如Ite
202012-5 星际旅行（线段树模板60分）记录一下

include lt bits stdc 43 43 h gt using namespace std typedef long long ll const int maxn 61 1e5 43 5 const ll MOD 61 1e9

202012-5 星际旅行 （线段树模板60分）记录一下

202012-5 星际旅行 （线段树模板60分）记录一下 的相关文章

随机推荐

热门标签

202012-5 星际旅行（线段树模板60分）记录一下

202012-5 星际旅行（线段树模板60分）记录一下的相关文章