每日一题第三期3月2日：区区区间

题目链接：https://ac.nowcoder.com/acm/problem/200195

描述

给你一个长度为n的数组，进行m次操作。1 l r k代表把闭区间l~r中的数替换为以k为首项，公差为1的等差数列，即a[l]=k,a[l+1]=k+1...。2 l r则代表查询闭区间l~r的和。题目很明确是用线段树来写，维护一个带有懒惰标记的线段树即可，参考朝阳学长的做法https://blog.nowcoder.net/n/84adee5178c648a782c7a07ac4a85250
每次 查找/修改 遍历结点时将懒惰标记分成两块下推首项即可，每个结点的权值代表等差数列的和

#include <bits/stdc++.h>

#include <algorithm>
#include <cmath>
#include <iostream>
using namespace std;
#define sc(x) scanf("%lld", &(x))
#define pr(x) printf("%lld\n", (x))
#define mem(a, b) memset(a, b, sizeof(a))
#define ios ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define endl "\n"
#define int long long
const long long N = 1e6 + 7;
const double eps = 1e-6;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const long long mod = 1e9 + 7;
const int dir[][2] = {{0, 1}, {1, 0},  {0, -1}, {-1, 0},
                      {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
const int inf = 0x3f3f3f3f;
const int _inf = 0xc0c0c0c0;
const ll inf_ll = 0x3f3f3f3f3f3f3f3f;
int a[N];
int tree[N];
int tanlan[N];
int l, r;
int num;
int ans;
void buildtree(int node, int L, int R) {
    if (L == R) {
        tree[node] = a[L];
        return;
    }
    int mid = (L + R) >> 1;
    int l_node = node * 2;
    int r_node = node * 2 + 1;
    buildtree(l_node, L, mid);
    buildtree(r_node, mid + 1, R);
    tree[node] = tree[l_node] + tree[r_node];
}
int jisuan(int a, int n) { return (a + a + n - 1) * n / 2; }
void up(int node, int L, int R) {
    int mid = (R + L) >> 1;
    if (tanlan[node]) {
        int l_node = node * 2;
        int r_node = node * 2 + 1;
        tanlan[l_node] = tanlan[node];
        tanlan[r_node] = tanlan[node] + (mid - L + 1);
        tree[l_node] = jisuan(tanlan[l_node], mid - L + 1);
        tree[r_node] = jisuan(tanlan[r_node], R - mid);
        tanlan[node] = 0;
    }
}
void add(int node, int L, int R) {
    if (L >= l && R <= r) {
        tanlan[node] = num + L - l;
        tree[node] = jisuan(tanlan[node], R - L + 1);
        return;
    }
    int mid = (R + L) >> 1;
    int l_node = node * 2;
    int r_node = node * 2 + 1;
    up(node, L, R);
    if (mid >= l) add(l_node, L, mid);
    if (mid < r) add(r_node, mid + 1, R);
    tree[node] = tree[l_node] + tree[r_node];
}
int chaxun(int node, int L, int R) {
    if (L >= l && R <= r) return tree[node];
    up(node, L, R);
    int res = 0;
    int mid = (L + R) >> 1;
    int l_node = node * 2;
    int r_node = node * 2 + 1;
    if (l <= mid) res += chaxun(l_node, L, mid);
    if (r > mid) res += chaxun(r_node, mid + 1, R);
    return res;
}
signed main() {
    //ios;
    int n, k;
    cin >> n >> k;
    mem(tanlan, 0);
    mem(tree, 0);
    mem(a, 0);
    for (int i = 1; i <= n; i++) cin >> a[i];
    buildtree(1, 1, n);
    while (k--) {
        int op;
        cin >> op;
        cin >> l >> r;
        if (op == 1) {
            cin >> num;
            add(1, 1, n);
        } else {
            int ans = chaxun(1, 1, n);
            cout << ans << endl;
        }
    }
}