poj3468

maksyuki 发表于 oj 分类，标签: 数据结构-线段树

15 9月 2015

A Simple Problem with Integers

You have N integers, A₁, A₂, ... , A_N. You need to deal with two kinds of operations. One type of operation is to add some given number to each number in a given interval. The other is to ask for the sum of numbers in a given interval.

Input

The first line contains two numbers N and Q. 1 ≤ N,Q ≤ 100000.
The second line contains N numbers, the initial values of A₁, A₂, ... , A_N. -1000000000 ≤ A_i ≤ 1000000000.
Each of the next Q lines represents an operation.
"C a b c" means adding c to each of A_a, A_a₊₁, ... , A_b. -10000 ≤ c ≤ 10000.
"Q a b" means querying the sum of A_a, A_a₊₁, ... , A_b.

Output

You need to answer all Q commands in order. One answer in a line.

Sample Input

10 5
1 2 3 4 5 6 7 8 9 10
Q 4 4
Q 1 10
Q 2 4
C 3 6 3
Q 2 4

Sample Output

Hint

The sums may exceed the range of 32-bit integers.

Source

POJ Monthly--2007.11.25, Yang Yi

题目类型：线段树

算法分析：这是一道线段树成段更新和区间求和的问题，要使用lazy标记，注意结果可能超过int范围，所以应该使用long long来存储结果

#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>

#define lson rt << 1, l, m
#define rson rt << 1 | 1, m + 1, r
using namespace std;

const int INF = 0x7FFFFFFF;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int MOD = 10000007;

const int maxn = 100000 + 66;

long long lazy[maxn<<2];
long long sum[maxn<<2];

void PushUp (int rt)
{
	sum[rt] = sum[rt<<1] + sum[rt<<1|1];
}

void PushDown (int rt, int l, int m, int r)
{
    if (lazy[rt])
    {
        lazy[rt<<1] += lazy[rt];
        lazy[rt<<1|1] += lazy[rt];
        sum[rt<<1] += lazy[rt] * (m - l + 1);
        sum[rt<<1|1] += lazy[rt] * (r - m);
        lazy[rt] = 0;
    }
}

void Build (int rt, int l, int r)
{
    lazy[rt] = 0;

    if (l == r)
    {
        scanf ("%lld", &sum[rt]);
        return ;
    }

    int m = (l + r) >> 1;
    PushDown (rt, l, m, r);

	Build (lson);
	Build (rson);
	PushUp (rt);
}

void UpDate (int rt, int l, int r, int L, int R, int add)
{
	if (L <= l && r <= R)
    {
		lazy[rt] += add;
		sum[rt] += add * (r - l + 1);
		return ;
	}

	int m = (l + r) >> 1;
    PushDown (rt, l, m, r);

    if (L <= m)
        UpDate (lson, L, R, add);

    if (R > m)
        UpDate (rson, L, R, add);

	PushUp (rt);
}

long long Query (int rt, int l, int r, int L, int R)
{
    if (L <= l && r <= R)
    {
        return sum[rt];
    }

    int m = (l + r) >> 1;
    PushDown (rt, l, m, r);
    long long ans = 0;

    if (L <= m)
        ans += Query (lson, L, R);

    if (R > m)
        ans += Query (rson, L, R);

return ans;
}


int main()
{
//    freopen ("aaa.txt", "r", stdin);

    int n, q;
    while (scanf ("%d%d", &n, &q) != EOF)
    {
        Build (1, 1, n);

        int i, val_a, val_b, val;
        char cmd[6];

        for (i = 0; i < q; i++)
        {
            scanf ("%s%d%d", cmd, &val_a, &val_b);

            if (cmd[0] == 'Q')
                printf ("%lld\n", Query (1, 1, n, val_a, val_b));


            else
            {
                scanf ("%d", &val);
                UpDate (1, 1, n, val_a, val_b, val);
            }
        }
    }

return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

#define lson rt << 1, l, m

#define rson rt << 1 | 1, m + 1, r

using namespace std;

const int INF = 0x7FFFFFFF;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int MOD = 10000007;

const int maxn = 100000 + 66;

long long lazy[maxn<<2];

long long sum[maxn<<2];

void PushUp (int rt)

{

sum[rt] = sum[rt<<1] + sum[rt<<1|1];

}

void PushDown (int rt, int l, int m, int r)

{

if (lazy[rt])

{

lazy[rt<<1] += lazy[rt];

lazy[rt<<1|1] += lazy[rt];

sum[rt<<1] += lazy[rt] * (m - l + 1);

sum[rt<<1|1] += lazy[rt] * (r - m);

lazy[rt] = 0;

}

void Build (int rt, int l, int r)

{

lazy[rt] = 0;

if (l == r)

{

scanf ("%lld", &sum[rt]);

return ;

}

int m = (l + r) >> 1;

PushDown (rt, l, m, r);

Build (lson);

Build (rson);

PushUp (rt);

}

void UpDate (int rt, int l, int r, int L, int R, int add)

{

if (L <= l && r <= R)

{

lazy[rt] += add;

sum[rt] += add * (r - l + 1);

return ;

}

int m = (l + r) >> 1;

PushDown (rt, l, m, r);

if (L <= m)

UpDate (lson, L, R, add);

if (R > m)

UpDate (rson, L, R, add);

PushUp (rt);

}

long long Query (int rt, int l, int r, int L, int R)

{

if (L <= l && r <= R)

{

return sum[rt];

}

int m = (l + r) >> 1;

PushDown (rt, l, m, r);

long long ans = 0;

if (L <= m)

ans += Query (lson, L, R);

if (R > m)

ans += Query (rson, L, R);

return ans;

}

int main()

{

// freopen ("aaa.txt", "r", stdin);

int n, q;

while (scanf ("%d%d", &n, &q) != EOF)

{

Build (1, 1, n);

int i, val_a, val_b, val;

char cmd[6];

for (i = 0; i < q; i++)

{

scanf ("%s%d%d", cmd, &val_a, &val_b);

if (cmd[0] == 'Q')

printf ("%lld\n", Query (1, 1, n, val_a, val_b));

else

{

scanf ("%d", &val);

UpDate (1, 1, n, val_a, val_b, val);

}

return 0;

}

poj3320

poj3641

超客的水墨烟雨

poj3468

分类目录

标签云

书签

近期评论

2025年4月
一	二	三	四	五	六	日
« 6月
	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