2022 天梯赛选拔赛

Problem N. 云烟科技争锋(30分)

在云烟强有力的公司团队改革下，果冻的公司由危转安。云烟不满足于游戏产业，他看到了科学+魔法带来的无限希望，于是他带着果冻、禾枫一同大兴科研，希望公司转型开拓更多的赛道，于是，云烟成立了大量的子公司。

现共有 nn 家子公司，编号从 11 到 nn 递增。第 ii 家公司研究的领域的收益期望为 aia_i ，现在云烟有 mm 次操作：

  1. 操作 11 ：更改所有收益期望值为 xx 的子公司的收益期望值，将这些子公司的收益期望值均改为 yy
  2. 操作 22 ：查询编号在区间 [x,y][x,y] 的所有子公司的收益期望之和

输入

输入一行两个整数 n,m(1≤n,m≤105)n,m(1\le n,m\le10^5) ，子公司数和操作数

接下来输入一行 nn 个整数，第 ii 个整数 aia_i 代表编号为 ii 的子公司初始收益期望值为 ai(1≤ai≤109)a_i(1\le a_i\le10^9)

接下来输入 mm 行，每行输入三个整数 c,x,y(1≤c≤2)c,x,y(1\le c\le 2)

  • 若 c=1c=1 ，代表执行操作 11 ，1≤x,y≤1091\le x,y\le 10^9
  • 若 c=2c=2 ，代表执行操作 22 ，1≤x≤y≤n1\le x\le y\le n

输出

对于每个操作 22 ，输出一行一个整数代表查询结果

样例

标准输入 复制文本 
4 7
20 20 200 5
2 1 4
1 20 5
2 2 4
1 10 40
2 2 4
1 5 200
2 1 4
标准输出 复制文本 
245
210
210
800

登录以提交代码。
单点时限 2 秒
内存限制 512 MB
提交 12
通过 0

A B C D E F G H I J K L M N O

题目存在部分分，请使用合适的做题策略答题