学习笔记_ codevs1081 线段树练习2 [重口味线段树(区间修改)]

华而不实的zkw线段树

懵逼的 题目

传送至 Codevs
(话说那些水过去的smg???就我一个辣鸡老老实实用了线段树???人与人之间基本的信任嘞???)

扯淡的 题解

昨天(其实好像还有前天?)水了五道搜索…(已经成为了一只咸宽嫂…)
然后…就啥都不会了QAQ我好菜啊QAQ
emm…上一篇文(kou)章(hu)讲了重口味的建树/区间查询/单点修改…这篇就讲讲区间修改咯QAQ
emm…好像网上讲重口味区间修改的很少啊….
重口味区间修改的巧妙在于不下传标记,而是在”回溯”的时候根据标记来修改返回值,了解了这个就好办辣QAQ修改和普通线段树一样,打标记,查询的时候再根据标记调整
修改的时候与区间查询操作极为相似…因为都是要求”不漏 不重”嘛

沙茶的 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
// codevs 1081.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#define MAXN (100000 + 5)
using namespace std;
struct xds
{
int zh;
int lz;
}a[8 * MAXN];
int n;
void js();
void xg(int, int, int);
int cx(int);
int main()
{
int srn;
cin >> srn;
n = 1;
while (n < srn) n <<= 1;
for (int i = 1; i <= srn; i++)
{
cin >> a[n + i].zh;
a[srn + i].lz = 0;
}
js();
/*for (int i = 1; i <= n + srn + 1; i++)
{
cout << a[i].zh << " ";
}
puts("");*/
int m;
cin >> m;
for (int i = 1; i <= m; i++)
{
int e, srx, sry, srz;
cin >> e;
if (e == 1)
{
cin >> srx >> sry >> srz;
xg(srx, sry, srz);
}
else
{
cin >> srx;
cout << cx(srx) << endl;
}
}
return 0;
}
void js()
{
for (int i = n - 1; i >= 1; i--)
{
a[i].zh = a[i << 1].zh + a[(i << 1) | 1].zh;
a[i].lz = 0;
}
}
int cx(int x)
{
x += n;
int re = a[x].zh;
while (x)
{
re += a[x].lz;
x >>= 1;
}
return re;
}
void xg(int l, int r, int z)
{
for (int i = l + n - 1, j = r + n + 1; (i ^ j) != 1; i >>= 1, j >>= 1)
{
if (!(i & 1))
a[i ^ 1].lz += z;
if (j & 1)
a[j ^ 1].lz += z;
}
}

By 好菜的 Cansult
又及: 明天好像要淘汰人啊我好方啊
qwq