QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 256 MB Total points: 100
[+5]

# 7490. 我回来了

Statistics

题目描述

珂朵莉在玩炉石传说的时候总是打不出教科书般的亵渎,于是他重新写了一个炉石传说’,并且将亵渎的描述改为:“等概率随机在 [L,R] 中选出一个整数作为伤害值 d,对所有随从造成 d 点伤害,如果有随从死亡,则再次施放该法术,但伤害值不重新随机;如果没有随从死亡,则停止释放”,还去掉了场面上随从上限和亵渎最多触发14次的限制。

珂朵莉不知道这个改版亵渎的效果怎么样,于是他打算进行一些测试,其中共进行 m 次如下类型的操作:

  1. 在场面上加入一个血量为 h 的随从,这里随从的血量都不能超过 n
  2. 给定 L,R,询问亵渎期望触发多少次;

珂朵莉只会做操作1,于是他就把操作2交给你啦。

输入格式

第一行两个由空格分隔的整数 nm

接下来 m 行,每行表示一次操作,操作1表示为 1h,操作2表示为 2LR

输出格式

为避免输出小数,对每次操作2,输出一个整数表示期望值与 (RL+1) 的乘积。

样例 #1

样例输入 #1

10 10
2 7 9
1 6
2 7 10
1 10
1 7
2 7 10
1 7
1 1
2 6 7
1 4

样例输出 #1

3
8
11
6

提示

Idea:oscar,Solution:ccz181078,Code:ccz181078,Data:nzhtl1477

对于 100% 的数据,保证: 1n105,每次1操作有 1hn,每次2操作有 1LRn1m106; 以上所有数值均为整数。