我要招人

去企业版

首页 > 试题广场 >

筱玛爱线段树

[编程题]筱玛爱线段树

时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

筱玛是一个热爱线段树的好筱玛。

筱玛的爷爷马爷在游戏中被筱玛吊打了，于是他恼羞成怒，决定给筱玛出这样一道数据结构题：

给定一个长度为 $n$ 的数组 $A$ ，刚开始每一项的值均为 $0$ 。

支持以下两种操作，操作共 $m$ 次：

$\texttt{1 l r}$ ：将 $A_l\sim A_r$ 的每一项的值加上 $1$ 。

$\texttt{2 l r}$ ：执行操作编号在 $[l,r]$ 内的所有操作各一次，保证 $r$ 小于当前操作的编号。

$m$ 次操作结束后，你要告诉马爷 $A$ 数组变成什么样子了。

由于答案可能会很大，你只需要输出数组 $A$ 中的每个数在模 $10^9+7$ 意义下的值。

输入描述:

第一行两个数，分别表示数组长度及操作次数。
接下来行，每行三个数，表示一次操作。

输出描述:

输出一行共个数，表示次操作结束后，的值。

示例1

输入

输出

3 3 3 0

备注:

对于100%的数据，。

算法知识视频讲解

__故人__

发表于 2020-10-12 13:59:39

分析我们主要考虑如何处理的操作又重新做一次，这个我们考虑区间加，定义为第次操作要执行的次数。那么这个我们可以通过差分做到。最后处理区间加。这个一样可以用差分来做，那么最后的复杂度为。差分，我们定义数组，如果原值为。那么满足。那么给全部等同于。这样我们对展开全文

又在摸鱼的大熊猫很勤奋努力

发表于 2020-10-12 18:45:28

筱玛爱线段树这个看上去有点树套树的感觉,但是它的区间满足某些性质，于是可以差分做首先有一个差分数组叫做，它的后缀和表示第个操作被除了这个操作本身操作了多少次还有一个，他的前缀和就表示第的数的答案然后题目的操作有一个性质：保证小于当前操作的编号所以是可以从后往前倒着推的，那么如果没有展开全文

林思艺

发表于 2020-10-12 17:04:14

题意给你一个初始值为的序列。你现在有两种操作，一是给的区间加；二是再执行一遍第次到第次的操作。思路两次差分。第一次为处理第二种操作，我们定义为第次操作要执行的次数，用差分实现。第二次是处理区间加，也可以用差分。所以，差分就对啦！代码 #include<bits/stdc++.h> 展开全文

DeNeRATe

发表于 2020-10-12 19:09:46

分析观察题目可以发现题目要求维护两种数组的区间加当Opt==2时，将操作区间加一当Opt==1时，将数组范围内的数加一我们还发现，第一种区间加，会影响第二种区间加所以我们在维护第一种区间加的基础上再维护第二种区间加并且我们发现第一种区间加会影响它之前的询问所以我们需要倒叙维护每个操作的次展开全文

Kur1su

发表于 2020-10-15 13:55:39

Description 筱玛是一个热爱线段树的好筱玛。筱玛的爷爷马爷在游戏中被筱玛吊打了，于是他恼羞成怒，决定给筱玛出这样一道数据结构题：给定一个长度为nn的数组AA，刚开始每一项的值均为00。支持以下两种操作，操作共mm次 mm次操作结束后，你要告诉马爷AA数组变成什么样子了。由于答案可能会很大，展开全文

sunsetcolors

发表于 2020-10-13 00:31:41

筱玛爱线段树题目地址： https://ac.nowcoder.com/acm/problem/25737 基本思路：如果只进行操作,很显然可以直接差分,那么我看引入的操作,其实也是一个差分的形式,所以我们考虑将查询离线,倒着维护两个差分,第一个差分我们可以在树状数组上进行,是维护当前的展开全文

shyyhs

发表于 2020-10-13 01:09:38

两次差分.第一次统计下某个操作要操作多少次,第二次差分就是直接统计答案了.注意要从后往前算. #include <bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e5+5; const int 展开全文

lifehappy

发表于 2020-10-12 23:10:51

筱玛爱线段树思路比较容易想到离线后从后向前处理，所以我们只要维护两个差分数组即可了，一个是答案数组，从前向后的，一个是当编号被操作了几次的数组，从后向前的，然后只需要按照要求模拟即可。代码 /* Author : lifehappy */ #include <bits/stdc++. 展开全文

昵称很长很长真是太好了

发表于 2020-10-18 10:03:57

题意：有两个操作，操作一和操作二。操作1：区间[l:r] +1操作2：执行操作编号在[l,r]内的所有操作各一次题解：两次差分。第一次差分，因为题目说保证r小于当前操作的编号，所以我们统计做了多少次操作1我们要倒着统计。如果正着进行差分计算，行不通，，因为你不知道后面具体有哪些操作包含了当前展开全文

ViolentFly

发表于 2020-10-13 14:57:18

题意：一个长度为n的数组，初始值都是0，给出2个操作：操作1：区间[l:r] 加1操作2：执行操作编号在[l,r]内的所有操作各一次求最后序列是多少？分析： 1、首先操作2是在之前操作再进行一次，所以我们可以先统计当前这个位置被操作了多少次，怎么统计呢，每个2的操作是对前展开全文

问题信息

线段树

难度：

0条回答 0收藏 9浏览

筱玛爱线段树

输入描述:

输出描述:

输入

输出

备注:

问题信息

热门推荐

相关试题