Lss233's.Blog()

TOJ 1175 - 线段树模板题

Lss233 -

这题也是线段树

单组数据，第一行一个正整数n。（1<=n<=10^5)

第二行n个数 a1,a2...an。（0<= |a[i]| <=10^7)

第三行一个整数m,表示m个操作。 （1<=m<=10^5)

接下来m行，每行第一个数表示操作类型，其余数表示操作对应的参数，对应题面。 （1<=l<=r<=n,0<=|v|<=10^7）

输入

单组数据，第一行一个正整数n。（1<=n<=10^5)

第二行n个数 a1,a2...an。（0<= |a[i]| <=10^7)

第三行一个整数m,表示m个操作。 （1<=m<=10^5)

接下来m行，每行第一个数表示操作类型，其余数表示操作对应的参数，对应题面。 （1<=l<=r<=n,0<=|v|<=10^7）

输出

对于每一个3操作，输出一行三个整数，表示区间和，最大值，最小值。

样例输入

5
1 2 3 4 5
7
1 1 1 -2
3 1 2
1 3 5 1
3 1 5
3 3 3
2 3 3 3
3 3 3

样例输出

1 2 -1
16 6 -1
4 4 4
3 3 3

题解

这题应该算是线段树的模板题了吧。最大值、最小值、求和、区间改值都有了。
所以特此记录一下。

代码

#include <bits/stdc++.h>
#define L(x) (x << 1)
#define R(x) (x << 1 | 1)
typedef long long ll;
const int MAX_N = 2e5 + 10;
struct leaf
{
    ll max, min, sum;
    leaf()
    {
        max = 0, min = 0, sum = 0;
    }
} tree[MAX_N * 4];
ll data[MAX_N], lazy_add[MAX_N * 4], lazy_set[MAX_N * 4];
bool is_lazy_set[MAX_N * 4];
void push_up(int k)
{
    tree[k].sum = tree[L(k)].sum + tree[R(k)].sum;
    tree[k].max = std ::max(tree[L(k)].max, tree[R(k)].max);
    tree[k].min = std ::min(tree[L(k)].min, tree[R(k)].min);
}
void push_down(int k, int a, int b)
{
    int m = (a + b) >> 1;
    if(is_lazy_set[k]) {
        lazy_add[L(k)] = lazy_add[R(k)] = 0;
        lazy_set[L(k)] = lazy_set[R(k)] = lazy_set[k];
        is_lazy_set[L(k)] = is_lazy_set[R(k)] = is_lazy_set[k];
        tree[L(k)].sum = (m - a + 1) * lazy_set[k];
        tree[L(k)].max = lazy_set[k];
        tree[L(k)].min = lazy_set[k];

        tree[R(k)].sum = (b - m) * lazy_set[k];
        tree[R(k)].max = lazy_set[k];
        tree[R(k)].min = lazy_set[k];
        is_lazy_set[k] = false;
    }
    if(lazy_add[k]) {
        lazy_add[L(k)] += lazy_add[k];
        lazy_add[R(k)] += lazy_add[k];
        tree[L(k)].sum += (m - a + 1) * lazy_add[k];
        tree[L(k)].max += lazy_add[k];
        tree[L(k)].min += lazy_add[k];

        tree[R(k)].sum += (b - m) * lazy_add[k];
        tree[R(k)].max += lazy_add[k];
        tree[R(k)].min += lazy_add[k];
        lazy_add[k] = 0;
    }
}
void build(int k, int l, int r)
{
    if (l == r)
    {
        tree[k].max = tree[k].min = tree[k].sum = data[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(L(k), l, mid);
    build(R(k), mid + 1, r);
    push_up(k);
}
void update(int k, int a, int b, int l, int r, int op, ll val)
{
    if (a <= l && r <= b)
    {
        if (op == 1) // add
        {
            tree[k].max += val;
            tree[k].min += val;
            tree[k].sum += val * (r - l + 1);
            lazy_add[k] += val;
        }
        else if (op == 2) // set
        {
            tree[k].max = val;
            tree[k].min = val;
            tree[k].sum = val * (r - l + 1);
            lazy_set[k] = val;
            lazy_add[k] = 0;
            is_lazy_set[k] = true;
        }
        return;
    }
    int mid = (l + r) >> 1;
    push_down(k, l, r);
    if (a <= mid)
    {
        update(L(k), a, b, l, mid, op, val);
    }
    if (mid < b)
    {
        update(R(k), a, b, mid + 1, r, op, val);
    }
    push_up(k);
}
leaf query(int k, int a, int b, int l, int r)
{
    if (a <= l && r <= b)
    {
        return tree[k];
    }
    push_down(k, l, r);
    int mid = (l + r) >> 1;
    leaf ans;
    if (a <= mid && mid < b)
    {
        leaf resA = query(L(k), a, b, l, mid);
        leaf resB = query(R(k), a, b, mid + 1, r);
        ans.max = std ::max(resA.max, resB.max);
        ans.min = std ::min(resA.min, resB.min);
        ans.sum = resA.sum + resB.sum;
        return ans;
    }
    if (a <= mid)
    {
        return query(L(k), a, b, l, mid);
    }
    if (mid < b)
    {
        return query(R(k), a, b, mid + 1, r);
    }
    return ans;
}
int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%lld", &data[i]);
    }
    build(1, 1, n);
    int m;
    scanf("%d", &m);
    while (m--)
    {
        int op, l, r;
        scanf("%d%d%d", &op, &l, &r);
        if (op < 3)
        {
            ll val;
            scanf("%lld", &val);
            update(1, l, r, 1, n, op, val);
        }
        else
        {
            leaf res = query(1, l, r, 1, n);
            printf("%lld %lld %lld\n", res.sum, res.max, res.min);
        }
    }
}