lightoj1183

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

27 8月 2015

1183 - Computing Fast Average

1 i j v - change the value of the elements from i^th index to j^th index to v.Given an array of integers (0 indexed), you have to perform two types of queries in the array.

2 i j - find the average value of the integers from i^th index to j^th index.

You can assume that initially all the values in the array are 0.

Input

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

Each case contains two integers: n (1 ≤ n ≤ 10⁵), q (1 ≤ q ≤ 50000), where n denotes the size of the array. Each of the next q lines will contain a query of the form:

1 i j v (0 ≤ i ≤ j < n, 0 ≤ v ≤ 10000)

2 i j (0 ≤ i ≤ j < n)

Output

For each case, print the case number first. Then for each query of the form '2 i j' print the average value of the integers from i to j. If the result is an integer, print it. Otherwise print the result in 'x/y' form, where x denotes the numerator and y denotes the denominator of the result and x and y are relatively prime.

Sample Input

Output for Sample Input

110 61 0 6 62 0 1

1 1 1 2

2 0 5

1 0 3 7

2 0 1

Case 1:616/37

Note

Dataset is huge. Use faster i/o methods.

题目类型：线段树+Lazy-Tag

算法分析：直接使用Lazy标记的线段树求解即可，注意多组数据之间要初始化lazy数组和sum数组！！！

#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>
using namespace std;

const int INF = 0x7FFFFFFF;
const int MOD = 7;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int maxn = 1e5 + 66;

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

long long sum[maxn<<2], lazy[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] != -1)
    {
        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] = -1;
    }
}

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

    int m = (l + r) >> 1;
    PushDown (rt, l, m, r);
    if (L <= m)
        UpDate (lson, L, R, vv);

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

    PushUp (rt);
}

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

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

    long long res = 0;
    if (L <= m)
        res += Query (lson, L, R);

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

    return res;
}

long long gcd (long long a, long long b)
{
    if (b == 0)
        return a;

    return gcd (b, a % b);
}

/*
    Case 1:
    23/2
    Case 2:
    9/2
    Case 3:
    622/3
*/

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

    int t, flag = 1;
    scanf ("%d", &t);

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

        long long n, q;
        scanf ("%lld%lld", &n, &q);

        memset (sum, 0, sizeof (sum));
        fill (lazy, lazy + (maxn << 2), -1);

        for (int i = 1; i <= q; i++)
        {
            long long oper, a, b, c;
            scanf ("%lld%lld%lld", &oper, &a, &b);

            if (oper == 2)
            {
                long long tt = Query (1, 0, n - 1, a, b);

                if (tt % (b - a + 1) == 0)
                    printf ("%lld\n", tt / (b - a + 1));

                else
                {
                    long long aa = gcd (tt, (b - a + 1));
                    printf ("%lld/%lld\n", tt / aa, (b - a + 1) / aa);
                }

            }

            else
            {
                scanf ("%lld", &c);
                UpDate (1, 0, n - 1, a, b, c);
            }
        }
    }
    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

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

using namespace std;

const int INF = 0x7FFFFFFF;

const int MOD = 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 1e5 + 66;

#define lson rt << 1, l, m

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

long long sum[maxn<<2], lazy[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] != -1)

{

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] = -1;

}

void UpDate (int rt, int l, int r, long long L, long long R, long long vv)

{

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

{

lazy[rt] = vv;

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

return ;

}

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

PushDown (rt, l, m, r);

if (L <= m)

UpDate (lson, L, R, vv);

if (R > m)

UpDate (rson, L, R, vv);

PushUp (rt);

}

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

{

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

return sum[rt];

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

PushDown (rt, l, m, r);

long long res = 0;

if (L <= m)

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

if (R > m)

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

return res;

}

long long gcd (long long a, long long b)

{

if (b == 0)

return a;

return gcd (b, a % b);

}

Case 1:

23/2

Case 2:

9/2

Case 3:

622/3

int main()

{

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

int t, flag = 1;

scanf ("%d", &t);

while (t--)

{

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

long long n, q;

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

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

fill (lazy, lazy + (maxn << 2), -1);

for (int i = 1; i <= q; i++)

{

long long oper, a, b, c;

scanf ("%lld%lld%lld", &oper, &a, &b);

if (oper == 2)

{

long long tt = Query (1, 0, n - 1, a, b);

if (tt % (b - a + 1) == 0)

printf ("%lld\n", tt / (b - a + 1));

else

{

long long aa = gcd (tt, (b - a + 1));

printf ("%lld/%lld\n", tt / aa, (b - a + 1) / aa);

}

else

{

scanf ("%lld", &c);

UpDate (1, 0, n - 1, a, b, c);

}

return 0;

}

lightoj1174

lightoj1197

超客的水墨烟雨