lightoj1164

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

27 8月 2015

1164 - Horrible Queries

0 x y v - you have to add v to all numbers in the range of x to y (inclusive), where x and y are two indexes of the array.World is getting more evil and it's getting tougher to get into the Evil League of Evil. Since the legendary Bad Horse has retired, now you have to correctly answer the evil questions of Dr. Horrible, who has a PhD in horribleness (but not in Computer Science). You are given an array of n elements, which are initially all 0. After that you will be given q commands. They are -

1 x y - output a line containing a single integer which is the sum of all the array elements between x and y (inclusive).

The array is indexed from 0 to n - 1.

Input

Input starts with an integer T (≤ 5), denoting the number of test cases.

Each case contains two integers n (1 ≤ n ≤ 10⁵) and q (1 ≤ q ≤ 50000). Each of the next q lines contains a task in one of the following form:

0 x y v (0 ≤ x ≤ y < n, 1 ≤ v ≤ 1000)

1 x y (0 ≤ x ≤ y < n)

Output

For each case, print the case number first. Then for each query '1 x y', print the sum of all the array elements between x and y.

Sample Input

Output for Sample Input

210 50 0 9 101 1 6

0 3 7 2

0 4 5 1

1 5 5

20 3

0 10 12 1

1 11 12

1 19 19

Case 1:6013Case 2:

Note

Dataset is huge. Use faster i/o methods.

题目类型：线段树

算法分析：线段树的成段更新和区间求和问题，直接按照题目的要求求解即可

#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 = 7;


const int maxn = 100000 + 66;
long long lazy[maxn<<2];
long long sum[maxn<<2];

int n, q;

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 t, flag = 1;
    scanf ("%d", &t);

    while (t--)
    {
        printf ("Case %d:\n", flag++);


        scanf ("%d%d", &n, &q);

        memset (sum, 0, sizeof (sum));
        memset (lazy, 0, sizeof (lazy));

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

            if (cmd == 0)
            {
                int val_a, val_b, val;
                scanf ("%d%d%d", &val_a, &val_b, &val);
                val_a++, val_b++;
                UpDate (1, 1, n, val_a, val_b, val);
            }

            else
            {
                int val_a, val_b;
                scanf ("%d%d", &val_a, &val_b);
                val_a++, val_b++;
                printf ("%lld\n", Query (1, 1, n, val_a, val_b));
            }
        }
    }

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

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

#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 = 7;

const int maxn = 100000 + 66;

long long lazy[maxn<<2];

long long sum[maxn<<2];

int n, q;

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 t, flag = 1;

scanf ("%d", &t);

while (t--)

{

printf ("Case %d:\n", flag++);

scanf ("%d%d", &n, &q);

memset (sum, 0, sizeof (sum));

memset (lazy, 0, sizeof (lazy));

int i;

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

{

int cmd;

scanf ("%d", &cmd);

if (cmd == 0)

{

int val_a, val_b, val;

scanf ("%d%d%d", &val_a, &val_b, &val);

val_a++, val_b++;

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

}

else

{

int val_a, val_b;

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

val_a++, val_b++;

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

}

return 0;

}

随机文章

超客的水墨烟雨

lightoj1164

Input

Output

Sample Input

Output for Sample Input

Note

随机文章

分类目录

标签云

书签

近期评论

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