题目链接:https://ac.nowcoder.com/acm/contest/892/D
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 65536K，其他语言131072K
64bit IO Format: %lld

题目描述

给你一个长度为n的序列，初始为1,2,3...n，对其进行m次操作。
操作有两种：

1 l r 表示将区间[l,r]用 [1,2...r-l+1] 覆盖
2 l r 查询[l,r]的区间和

输入描述

第一行包含2个数字，n,m（1 <= n,m <= 1e5）
接下来包含m行，格式如题面所示

输出描述

对于每个操作2，输出一行一个整数表示答案

输入

10 5
2 1 10
1 3 6
2 1 10
1 1 10
2 1 10

输出

55
47
55

解题思路

线段树，对于操作1 l r，就是将[l, r]中的值变成i-l+1，然后按照线段树模板计算就行了。

Accepted Code:

/* 
 * @Author: lzyws739307453 
 * @Language: C++ 
 */
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
struct edge {
    long long val, Mark;
}segTree[MAXN << 2];
void Create(int root, int left, int right) {
    segTree[root].Mark = 0;
    if (left == right) {
        segTree[root].val = left;
        return ;
    }
    int mid = left + ((right - left) >> 1);
    Create(root << 1, left, mid);
    Create(root << 1 | 1, mid + 1, right);
    segTree[root].val = segTree[root << 1].val + segTree[root << 1 | 1].val;
}
void PushDown(int root, int left, int right, long long val) {
    int l = right - left + 1;
    segTree[root].Mark = val;
    segTree[root].val = ((2 * val + l - 1) * l) >> 1;
}
void pushDown(int root, int left, int right) {
    if (segTree[root].Mark != 0) {
        int mid = left + ((right - left) >> 1);
        PushDown(root << 1, left, mid, segTree[root].Mark);
        PushDown(root << 1 | 1, mid + 1, right, segTree[root].Mark + mid + 1 - left);
        segTree[root].Mark = 0;
    }
}
void Update(int root, int Q_left, int Q_right, int left, int right, long long val) {
    if (Q_left <= left && Q_right >= right) {
        segTree[root].Mark = val;
        int l = right - left + 1;
        segTree[root].val = ((2 * val + l - 1) * l) >> 1;
        return ;
    }
    pushDown(root, left, right);
    int mid = left + ((right - left) >> 1);
    if (Q_right <= mid)
        Update(root << 1, Q_left, Q_right, left, mid, val);
    else if (Q_left > mid)
        Update(root << 1 | 1, Q_left, Q_right, mid + 1, right, val);
    else {
        Update(root << 1, Q_left, mid, left, mid, val);
        Update(root << 1 | 1, mid + 1, Q_right, mid + 1, right, val + mid - Q_left + 1);
    }
    segTree[root].val = segTree[root << 1].val + segTree[root << 1 | 1].val;
}
long long Query_(int root, int Q_left, int Q_right, int left, int right) {
    if (Q_left <= left && Q_right >= right)
        return segTree[root].val;
    pushDown(root, left, right);
    int mid = left + ((right - left) >> 1);
    if (Q_right <= mid)
        return Query_(root << 1, Q_left, Q_right, left, mid);
    else if (Q_left > mid)
        return Query_(root << 1 | 1, Q_left, Q_right, mid + 1, right);
    else return Query_(root << 1, Q_left, mid, left, mid) +
            Query_(root << 1 | 1, mid + 1, Q_right, mid + 1, right);
}
int main() {
    int n, m, left, right, Judge;
    scanf("%d%d", &n, &m);
    Create(1, 1, n);
    while (m--) {
        scanf("%d%d%d", &Judge, &left, &right);
        if (Judge - 1)
            printf("%lld\n", Query_(1, left, right, 1, n));
        else Update(1, left, right, 1, n, 1);
    }
    return 0;
}