luogu#P5636. 【CSGRound1】病毒
【CSGRound1】病毒
题目背景
A 国有 座城市,这 座城市排成一排(编号 到 ),A国的人们幸福快乐地生活着,人口呈增长很快。因此,到了天下第一的fkc IOI捧杯那年(2020年),A国的人已经多到数不清了,我们不妨假设 A 国这 座城市每座城市中的人口都有无限个。A 国的风向很特别,始终是从 城市吹向 城市。A 国没有首都,在发生状况时,每个城市的政府都不会去支援其他城市。
题目描述
然而,在 fkc 捧杯后不久,邪恶的B国国王X制造了傻逼病毒希望以此来摧毁 A 国。A 国遭受了重大的灾难。傻逼症分一期和二期。感染了一期傻逼症的人会觉得自己是傻逼,而且希望只有自己能被称作傻逼,因此会经常大打出手,扰乱社会秩序。傻逼症二期的病人还会产生一系列的精神疾病,而且具有较强传染性。X会使用傻逼风暴来传染傻逼症,傻逼风暴会导致各种通讯工具和设备在短时间内瘫痪,因此,如果在i城爆发傻逼风暴,那么i城在傻逼风暴期间政府无法发挥很大的作用,我们不妨认为i城在傻逼风暴期间会处于无政府状态。
如果 城市爆发 级傻逼风暴 ,会导致 城市接下来一秒有一个普通人感染二期傻逼症,如果第一秒末感染了二期傻逼症但未被隔离的人有 个,那么第二秒感染一期傻逼症的人会增加 个,感染二期傻逼症的人会增加 个。(, 是给定常数)。然后如果 为 那么该城市的傻逼风暴就会停止,政府设备又会恢复。否则该城市第三秒会继续爆发 级傻逼风暴(期间政府不会恢复)。
X每次会在第 个城市投掷 级风暴种子,由于风向原因, 城市会爆发 级傻逼风暴,沿风向过去后的下一个城市会爆发 级傻逼风暴,再沿风向过去后的下一个城市会爆发 级傻逼风暴……直至爆发的傻逼风暴等级小于 或者再沿风向下去没有城市了。
当然,A 国各个城市的政府十分强大,不会束手就擒于傻逼症的攻击,他们会通过隔离病人以起到拖延傻逼症的蔓延速度。大佬们能在瞬间找到所有感染了傻逼症的人并将他们隔离。但是很无奈,傻逼风暴会暂时使这些设备失灵。
但是,X的风暴种子可以无限生产,无限释放。A 国政府只使用隔离法显然不是个明智的选择。于是 A 国的一些大佬开始夜以继日地尝试着研发能控制傻逼症的药物。功夫不负有心人,A 国终于研发出了治疗法术。A 国组建了联合政府,可以在城市i投放k级治疗法术,这样子,对于所有的 城市,所有已被隔离的一期傻逼病人变成普通人,二期傻逼症病人变成一期傻逼症病人。
当然,X也十分强大,他还研制出了一种增强法术来对抗治疗法术。增强法术可使傻逼病毒更加快速地寻找宿主细胞进行繁殖,从而加重傻逼症,增加传染性。X每次会在城市 投放 级增强法术,那么对于所有 的城市,所有的一期傻逼症患者变成二期傻逼症患者。而且短期内增强的傻逼病毒可依附在空气中传播,所以如果当前该城市一共有 个傻逼症患者,那么在增强法术作用效果结束之前,该城市又会有一共 个普通人变成一期傻逼症患者。
由于本次事件事态十分严重,A 国联合政府的临时主席想要尽快知道患有傻逼症的病人有多少个,所以他找到了你来帮助他尽快算出答案。
所以现在给定一些事件,每一个事件都在上一个事件结算完毕之后发生:
- 邪恶的 B 国国王X在城市 投放了 级风暴种子。
- A 国联合政府在城市 投放了 级治疗法术。
- X 在城市 投放了 级增强法术。
- A 国联合政府想知道对于所有的 城市,一共有多少个一期傻逼症病人。
- A 国联合政府想知道对于所有的 城市,一共有多少个二期傻逼症病人。
一开始 A 国没有人感染傻逼症,请对于每一个 事件给出一个 A 国联合政府想要的答案,因为答案可能很大,所以你只要输出对 取模后的答案即可。
输入格式
第一行依次输入 个正整数 。 表示一共有多少个事件。
接下来 行,每行表示一个事件。
每行第一个数字 表示事件类型。
- 如果 ,表示投放风暴种子,接下来两个数 如题目所述。
- 如果 ,表示投放治疗法术,接下来两个数 如题目所述。
- 如果 ,表示投放增强法术,接下来两个数 如题目所述。
- 如果 ,表示询问一期傻逼症,接下来两个数 如题所述。
- 如果 ,表示询问二期傻逼症,接下来两个数 如题所述。
输出格式
如题所述,每个询问结果占一行。
5 4 2 3
1 3 2
1 4 2
4 1 2
5 2 4
2
48
10 8 2 8
1 7 4
3 1 4
5 1 3
2 3 5
1 6 3
5 5 8
3 6 6
4 4 7
0
909
94680
6 6 3 4
1 5 6
5 1 3
3 2 4
5 3 6
3 1 5
5 2 3
965
42365
13048
提示
样例 1 第一个事件中城市 爆发 级傻逼风暴,城市 爆发 级傻逼风暴。以城市 为例,首先产生一个二期,然后增加 个一期,再增加 个二期,然后风暴变为 级,再增加 个二期,那么当前有 个二期,那么又增加了 个一期和 个二期。所以在结算之后城市 有 个二期, 个一期,城市 有 个二期, 个一期。这些患者均被隔离,然后第二个事件城市 增加了 个二期, 个一期,城市 增加了 个二期,个一期。对于第一个询问显然是 。对于第二个询问,结算之后城市 有 个二期,城市 有 个二期,城市 有 个二期,加起来是 。
本题一共五个点。
对于所有数据,,。
第一个点:,。
第二个点:,。
第三个点:,,特殊性质:第一个事件为事件 ,之后只有事件 和事件 。
第四个点:,,特殊性质:没有事件 和事件 。
第五个点:,。