喵哈哈村的种花魔法(线段树的区间更新)

关键词：

3 1
1 2 3
1 2 5

6 7 3

3 2
1 2 3
1 3 2
1 2 5

8 9 5


这题是线段树区间更新问题

以下贴出常规写法，以及大佬的写法。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #define ll long long
 5 #define lson l, m, rt<<1
 6 #define rson m+1, r, rt<<1|1
 7 const int maxn = 1e6+10;
 8 using namespace std;
 9 ll flo[maxn<<2];
10 void PushUP(int rt){
11     flo[rt] = flo[rt<<1] + flo[rt<<1|1];
12 }
13 void build(int l, int r, int rt){
14     if(l == r){
15         scanf("%lld",&flo[rt]);
16         return;
17     }
18     int m = (l + r) >> 1;
19     build(lson);
20     build(rson);
21 }
22 void update(int L, int R, ll add, int l, int r, int rt){
23     if(L <= l && r <= R){
24         flo[rt] += add;
25         return;
26     }
27     int m = (l + r) >> 1;
28     if(m >= L) update(L, R, add, lson);
29     if(m < R) update(L, R, add, rson);
30     //PushUP(rt);
31 }
32 void query(int l, int r, int rt, ll k){
33     if(l == r){
34         printf("%lld ",flo[rt]+k);
35         return;
36     }
37     int m = (l + r) >> 1;
38     if(m >= l) query(lson,k+flo[rt]);
39     if(m < r) query(rson,k+flo[rt]);
40 }
41 int main()
42 {
43     int n, m;
44     while(cin>>n>>m){
45         memset(flo, 0, sizeof(flo));
46         build(1, n, 1);
47         ll a, b, c;
48         while(m--){
49             scanf("%d%d%d",&a,&b,&c);
50             update(a, b, c, 1, n, 1);
51         }
52         query(1, n, 1, 0);
53         printf("
");
54     }
55     return 0;
56 }

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 #define ll long long
 4 const int maxn = 1e5+10;
 5 ll a[maxn], b[maxn];
 6 int main(){
 7     int n, m;
 8     while(cin>>n>>m){
 9         memset(b, 0, sizeof(b));
10         for(int i = 1; i <= n; i++){
11             scanf("%lld",&a[i]);
12         }
13         for(int i = 1; i <= m; i++){
14             ll l, r, val;
15             scanf("%d%d%lld",&l,&r,&val);
16             b[l] += val;
17             b[r+1] -= val;
18         }
19         ll sum = 0;
20         for(int i = 1; i <= n; i++){
21             sum += b[i];
22             a[i] += sum;
23         }
24         for(int i = 1; i <= n; i++){
25             printf("%lld ",a[i]);
26         }
27         printf("
");
28     }
29     return 0;
30 }

qscoj128喵哈哈村的魔法源泉(模仿快速幂，好题)

喵哈哈村的魔法源泉（2）发布时间:2017年5月9日20:59  最后更新:2017年5月9日21:00  时间限制:1000ms  内存限制:128M描述喵哈哈村有一个魔法源泉，里面有无穷无尽的力量。但是前提是你能答出这样一个问题：给... 查看详情

喵哈哈村的魔法考试round#10(div.2)b

喵哈哈村与哗啦啦村的大战（二）发布时间:2017年3月27日09:25  时间限制:1000ms  内存限制:128M描述喵哈哈村因为和哗啦啦村争夺稀有的水晶资源，展开了激烈的战斗。喵哈哈村与哗啦啦村战斗的地图可以视为一个二... 查看详情

10喵哈哈村的魔法石

题目传送：描述传说喵哈哈村有三种神奇的魔法石：第一种魔法石叫做人铁石，拥有A的能量；第二种魔法石叫做地冈石，拥有B的能量；而第三种，则是最神奇的天玄石，拥有无可比拟的C的能量！但是有一天，沈宝宝太调皮了，... 查看详情

喵哈哈村的魔法考试round#3(div.2)abcde

.../qscqesze/p/6480284.html哗啦啦村的刁难(1)描述哗啦啦村作为喵哈哈村的对头，于是他们准备给喵哈哈村一个好看。哗啦啦村的头号长老——鱼先生，就提出了以下问题：给你三个木棍，问你这三个木棍，是否能够组成一个非退化的三... 查看详情

喵哈哈村的魔法考试round#10(div.2)a

喵哈哈村与哗啦啦村的大战（一）发布时间:2017年3月27日09:13  时间限制:1000ms  内存限制:128M描述喵哈哈村因为和哗啦啦村争夺稀有的水晶资源，展开了激烈的战斗！喵哈哈村里面有n个战士，这些战士每个人一开始... 查看详情

喵哈哈村的魔法考试round#14(div.2)

喵哈哈村的四月半活动（一）(水题)描述今天是四月十五日，是喵哈哈村一年一度的四月半活动，这次活动是由今日头条赞助。今日头条的乐乐同学在广场上出了一道题，谁答对，就能获得他的祝福哦。题目如下：勾股定理是初... 查看详情

2017-5-16-train:喵哈哈村的魔法考试round#19(div.2)

A.喵哈哈村的魔力源泉(水题)描述喵哈哈村有一个魔法源泉，里面有无穷无尽的力量。但是前提是你能答出这样一个问题：给你a,b,p，让你输出a*b%p的值。输入本题包含若干组测试数据。第一行三个整数a,b,p。满足：0<=a,b,p<=1e9... 查看详情

2017-5-20-train:喵哈哈村的魔法考试round#17(div.2)

A.喵哈哈村的秘境探险(数学)描述喵哈哈村的一堆人在前往北京的路上，发现了一个洞穴。由于好奇心大作，于是准备前往洞穴进行探险。但是有一些人并不愿意前往洞穴，于是他们决定玩以下游戏，来看是否能够去秘境探险：... 查看详情

2017-5-17-train:喵哈哈村的魔法考试round#18(div.2)

A.喵哈哈村的古怪石碑(签到题)描述喵哈哈村有个奇怪的石碑，上面浮现出了一个奇怪的问题：有一数列{an}，给出其前三项a1，a2，a3，以及要求的项的编号n，并且数列{an}只可能是等差数列或者是首项为1的等比数列，要求A输出第... 查看详情

喵哈哈村的魔法考试round#19(div.2)b

题目链接：http://qscoj.cn/problem/128/题意：给你a,b,p，让你输出a*b%p的值。0<=a,b,p<=1e18思路：两个longlong相乘然后modp,相乘以后可能会溢出,古有快速幂,现有快速乘法。 代码： 1#include<bits/stdc++.h>2usingnamespacestd;3typedeflongl... 查看详情

喵哈哈村的魔法考试round#19(div.2)c

描述喵哈哈村有一个魔法源泉，里面有无穷无尽的力量。但是前提是你能答出这样一个问题：小T打算在城市C开设一家外送快餐店。送餐到某一个地点的时间与外卖店到该地点之间最短路径长度是成正比的，小T希望快餐店的地址... 查看详情

qscoj喵哈哈村的打印机游戏区间dp

               点这里去看题区间dp，dp[l][r][d]代表从l到r的区间底色为d，具体看代码 第一次见到区间dp。。。两个小时对着敲了五遍终于自己敲懂了一遍ac #include<bits... 查看详情

喵哈哈村的括号序列

喵哈哈村的括号序列发布时间:2017年2月21日20:05  最后更新:2017年2月21日20:07  时间限制:1000ms  内存限制:128M描述喵哈哈村的括号序列和外界的括号序列实际上是一样的。众所周知"()"这样的，就是一个标准的括... 查看详情

喵哈哈村的修路游戏

链接：http://qscoj.cn/problem/51/喵哈哈村的扔硬币游戏发布时间:2017年3月21日20:00  最后更新:2017年3月21日20:01  时间限制:1000ms  内存限制:128M描述喵哈哈村的月亮同学很无聊，于是太阳同学给月亮同学出了个问题... 查看详情

喵哈哈村的排队

喵哈哈村的排队发布时间:2017年2月26日16:13  最后更新:2017年2月26日16:14  时间限制:1000ms  内存限制:128M描述有一堆喵哈哈村的村民们在排队，他们从队列的尾部开始标号，标号为1的村民站在最后面，标号为n... 查看详情

喵哈哈村的木星传说

链接：http://qscoj.cn/problem/72/喵哈哈村的木星传说（一）发布时间:2017年4月11日20:01  最后更新:2017年4月11日20:01  时间限制:1000ms  内存限制:128M描述喵哈哈村有一个挂在空中的木星爷爷，每天晚上都讲一些故事... 查看详情

qscoj喵哈哈村的魔法考试round#5(div.2)题解（前1，2，3题）ps：前三题在本人水平可掌控范围之内

题目链接：http://qscoj.cn/problem/30/第一题喵哈哈村的狼人杀大战(1)时间限制:1000ms  内存限制:128M 描述喵哈哈村最近热衷于玩一个叫做狼人杀的游戏！张小田今天她抽到的是民的身份，按照她的一贯玩法，她不会考虑发言... 查看详情

喵哈哈村的赛马比赛

喵哈哈村的赛马比赛发布时间:2017年2月21日20:05  最后更新:2017年2月21日20:07  时间限制:5000ms  内存限制:128M描述喵哈哈村一年一度的赛马比赛要开始了！沈宝宝和戴尔廖由于达成了某笔交易，成了好朋友，于... 查看详情