Logo __vector__ 的博客

博客

标签
暂无

Codeforces Round 909 (Div. 3)

本文章由 WyOJ Shojo 从洛谷专栏拉取,原发布时间为 2023-11-19 01:13:47

输麻了,G 的正确代码差 1s 交上,F 干脆没做。
总之手速还是不行。Div.3 没啥难题, AK 难度就在于手速。

A

如果第一次 Vanya 没赢,那么 Vova 就可以重置,让他永远不赢。

B

参考 $n$ 的最大因子个数。
暴力能过。

C

设 $dp_i$ 表示右端点为 $i$ 的最大大小。

若 $a_i$ 和 $a_{i-1}$ 奇偶不同,$dp_i = \max(a_i,dp_{i-1}+a_i)$
否则,$dp_i = a_i$

最后答案是 $\max(dp_1,dp_2,\cdots,dp_n)$

D

设 $pw_i$ 为 $a_i$ 的质因数分解中 $2$ 的出现次数。
设 $bs_i$ 为 $\frac{a_i}{2^{pw_i}}$。

由小学数学可以推导得知,$i,j$ 能配对,当且仅当 $pw_i - a_i = pw_j - a_j$。

然后 map 统计一下就好了。

E

最终要求没有任意一个 $i$ 使得 $a_i \gt a_{i+1}$。

考虑每次操作的影响。

如果 $a_i \gt a_{i+1}$,那么它本质上消除了一对不合法的数对。

否则相当于不改变。

依次操作下来,当最后一个不合法的 $i$ 被执行操作,排序也就完成了。
设最后一个不合法的 $i$ 为 $lst$。

考虑 $[1,lst]$ 之间每个 $i$ 被执行的影响。

第 $i$ 个,如果跳出了 $[1,lst]$ 的范围,那么没啥事。
如果没跳出(只要是没跳到 $lst$ 后面就算),那么稍稍想一下依赖关系,必然是陷入了无限循环,无解。

那么如何判断无限循环呢?

只要有 $[1,lst]$ 任意一个 $i$ 操作之后位置不改变,那么一定陷入无限循环,从而间接导致其他的 $i$ 跳不出去。

F

默认根是 $1$。

为了方便实现,我们可以仅仅用两条链构造出两个距离为 $d_i$ 的叶子。

先根据 $d_1$ 构造出大概是这样的两条链(从 $1$ 出发):

第一条链长度固定是 $1$,而第二条链的长度则根据 $d_i$ 进行变化,这个例子中,$d_i = 4$。

剩下的节点干什么呢?因为第二天链的长度需要时刻变化,所以我们还是从 $1$ 出发,新建第三条链,进行存储。

大概长这样($n=8,d_i=4$)

第 $3$ 条链是 $1,6,7,8$ 组成的。

需要适应 $d_i$ 时,直接配合第三条链进行切割/接尾操作就行。

我为了方便开了 $3$ 个 std::list

G

我们可以将这个问题转化为一个更清新的问题:

给定一个数列 $p$,并推导得到一个数列 $p{'}$。

设 $size_i$ 为 $i$ 为根的子树大小,$dfn_i$ 是 $i$ 的 dfs 序。

$p{'}_i$ 是节点 $p_i$ 的 dfs 序。

每次询问给定 $l,r,x$,求是否存在 $i$,使得 $l \le i \le r$,且 $dfn_x \le p'_i \le dfn_x + size_x - 1$。

这种操作,log 数据结构似乎不大好做,自然联想到优雅的暴力——分块。
具体的,每个块预处理哪些 $p'$ 值出现过,并开桶记录(由于任意 $p'_i$ 不会超过 $n$,所以可以用桶)

接下来每个块就可以 $O(1)$ 判断某个值域区间是否有数存在了。

预处理复杂度 $O(n \sqrt n)$,查询复杂度 $O(q \sqrt n)$。

2021.4.7 ===> 2023.11.19

本文章由 WyOJ Shojo 从洛谷专栏拉取,原发布时间为 2023-11-19 23:15:32

记录在 YTEZ 打 OI 的大约两年半,非 AFO。

下次发这种类型 blog 就是退役之后了。

2021.4.7 --> CSP-J2021

2021 4 月那会刚刚开始学 OI。

在此之前参加过有道小图灵的入门选拔比赛并侥幸 ak,所以自信地不得了。
我第一次来到 YTEZ 机房,当时安排了一个靠右的座位。

还记得范教练问:“你学过数据结构吗?”

我:“学过一些”(我内心以为 struct,class 那些就是全部数据结构)

上来看洛谷的题目,我发现从红到黑分成了一些等级,由于过分自信,我一开始就随机点了一道黑题,然后发现根本读不懂(周围人:“刚来就做黑题?”)

我想着,黑题不行绿题,绿题总会吧,然后我连续开了数道绿题,仍然没有能读懂的。

被现实打击之后,就开了道橙题。

经过半天思考的结果:

充分认识到了自己的菜。

不久,我在清北学堂参加了打 OI 之后的第一场比赛。

当时 T1 是个有基本常识的人都会做的题,但我却仅仅拿到 40分。

而后面题,其中一道我写了个完全错的做法,东凑西凑过了样例,然后爆零,另一道写了 10 分,还有一道 0 分。

当时战绩如下:

当时没怎么在意,因为教练说 zhqwq 大佬的第一场比赛是 0 分

然后又开了几道红题,没有一道会的。

于是我拿 A+B problem 凑数,写的时候尽力掩盖着题目名称,还是不幸被 ysy 大佬看见了,悲。

后面教练进行分组,我分到了 2 组,平时范教练会讲题,并让我们做完并提交题解和 AC 证明,时常会有学生讲题。


(2 组后来渐渐不再说话了,但我至今仍留在群里)

不过似乎并没有防作弊措施,我看到了有人抄我的题解和代码,但是我不想举报,这说明至少有人看得起我。

大概两个月后,第一次点开 codeforces。

当时感觉就是很有神秘感。

随后在 YTEZ 机房内打了第一次(虚拟参赛) CF。

Div.3 A 我用时 1h,2 发罚时才勉强通过。

就这,当时的我高兴的发出了猪叫。

然后 Div.3 B 用时 25min,猜了个结论过了。

Div.3 C 我死活解不出来(一直和样例不一样)

赛后知道有个东西叫 Special Judge。

一看排行榜,我垫底了。

后来又组织了很多场 vp 训练,统一时间,赛后要求汇报成绩,是否诚信全靠自觉。

接下来 vp 了很多场 Div.3,可是别人都 ABCD+,至少也是 ABC,我却一直只能做出 AB,信心受到很大打击。

我就通过打一场 CF 就补完所有题的方式进行训练,可是训练了 1 个月也没有任何效果。

接下来集体 vp Div.2,别人最差的也是 A-AB,我却场场爆零,开始怀疑自己智商了。

跟教练汇报成绩时我想钻墙缝里去。

后来被我爸强制下军令状了,再爆零两场就 AFO。

为了不 AFO,我想到了个方法在不作弊的情况下不爆零。

因为比赛是从近期数十场比赛里面选择的,我就疯狂刷题,刷近几十场 CF 的题。这样撞上做过的就不算作弊。

结果接下来一次 vp Div.2 仍然爆零。

最后一次机会,被 vp 的场次刚好被我刷过,惊险。

这可能也是到现在我打其他重要的比赛都不如打任意一场 CF 紧张的原因,现在仍然心有余悸。

过了一小段时间,教练通知将进行选拔,通过选拔的去报名 CSP-J,挂掉的去参加 CSP-X,鉴于我 vp 的这些 CF 场次的 ”精彩“表现,我没有想过选上。

后来转机还是出现了。

参加了一些模拟赛,意外的都取得了较为不错的成绩。

然后信心就有了,继续干,成绩不断提高,最终通过选拔。

CSP-J 赛前甚至有的模拟赛破天荒的拿到 rk1,2。

那段时间过的还是比较快乐的,当时 YTEZ 非常流行 fake 风气,现在想想挺有趣的。当时也没有任何奖项,纯粹的以打比赛为乐趣源泉。

我都以为稳 1= 了,然而挂了。

T1 红题做不出,T2 暴力还写挂,T3 苦写写不出,T4 CE也爆零。

总挂分 70pts,拿到了低分二等奖。

当时哭了一晚上。

随后参加了期中考试,rk9,挺意外的。

CSP-J2021 --> NOIP2022

就当作了一个新的起点,那段时间,心里想起来这个事就难受,之后刷了几个月的题。

然后是 NOI Online,入门&提高都寄了,而且不是一般的惨。

又是一次较大的打击。

没过多久以非正式选手参加 SD 省选,打了几个暴力就跑了,后来听人说我的分数是全省 60 多名,但感觉纯粹胡扯。

后面又遇到了可怕的瓶颈:CF 被卡死在 rating = 1000,无论如何摆脱不了。

后来参加了 SDSC2022 的高级算法班。

这期间同样是很快乐的,风景还算不错的校园里面,人来人往的,有成群结队的参营选手,还有原本就在这个学校的大学生。

雨天就更有趣了。

当时由于不服失败的干劲,每天晚上都学到很晚,然后被宿舍其他人称为卷王,当然我不配。

我 CF 第一次突破就在于这期间的一场比赛,经过 6 次罚时,终于在最后 5min,第一次通过 Div.2 D,狂喜,叫声还把旁边人吵醒了,这里表示歉意:(

这段时间一个值得说的事:一场 Codeforces Div.3 比赛中 hack 掉了 cxm 大佬的 E 题,只是我当时不知道他,他那时也只是个 Specialist。

后续还参加了编程兔,但是为什么它没有自己的 OJ !!!!!/fn

随着 10 月的临近,我参加了一场又一场的模拟赛, 感受到了水平较 2021 年的巨大提升。

我满怀期待的准备,希望从 CSP-S 拿一个蓝色的钩子,然而等来的却是 CSP-S 取消的消息。

气得要死。

不过好消息是,全员都获得了 NOIP 资格。

最后 7 天,前往 pyyz 集训。

这次更多的是紧张,怕一题不会,怕没有省一。

最后两天,强压着紧张,全天打游戏。

比赛当天早上反而没那么紧张,平稳地写掉一个又一个 subtask,最后得到 123pts,省一。

得知省一后,也就一小会的高兴,然后平静下来。

NOIP2022 --> CSP-S2023

打完 NOIP,我却不知道该干什么了。

没人给我一个明确的刷题计划,包括题单我也没有。

我只能是一个一个刷算法,CF 打得也很少。

就这么,到了 SDOI2023 前夕,我甚至感觉水平一点都没有提升。

然而 SDOI 出的题刚好符合我的强项,再加上我采用激进策略,以及良好心态,拼尽全力打了 9h 竟压着进 3 倍队线。

这次明明只是超常发挥,并没有水平提升,但我被这次的成果蒙蔽了,以为自己那点破水平真的上升了,然后到 Thusc 前我都放松状态了。

然后 Thusc Day1 正常 pretest 赛制比赛,一题不会,爆了。
Day2 我很多问题甚至看不懂问题,爆了。

然后没约。

但由于 YTEZ 总共就 6 个省选成绩较高的进入 Thusc,而 YTEZ OIer 总人数听说在 100 以上,所以也没啥丢人的。

后来.....参加了 HaoBa,并选入提高 B 班。

听下来几节课的效果就是:看到评分 2000+ 的题不再直接跳过,甚至能做出一部分,可即使这样,CF 不管怎么打,等级分就是上不去,而赛时死活做不出的题,第二天一眼秒的事属于家常便饭。

然后度过了一个相对平静的时期。

曾经打 CF 看到的一个用户,我觉得有趣就在 CF 上关注了他(当时我甚至不知道他的国籍),没想到在南京训练时碰面了。

他是 lsxhyyds,chb。

很快就迎来了 CSP-S2023。

我赛前有十足的信心,还说这次说不定全员 1=(可惜我拖后腿了)

结果 被T1薄纱,T2分析错误,T3 65分挂成 0 ,T4 没写。

然后爆炸了。

我还寄希望于 NOIP 翻盘。

又训练了十几天。

然后,CCF 政策刚好变更,山东省从以前的有分就能进 noip 改成了 130 分进。

我在外网匿名疯狂问候 CCF,却无可奈何。

noip 看了题目,会的分总共是 287 分,可惜这次没去参加。

The end

Goodbye,@OMG_78 @快乐的大童 @cancan123456 @cancan12345 @GS128 @Anonyme 等等

Codeforces Round 908 (Div. 2) Editorial

本文章由 WyOJ Shojo 从洛谷专栏拉取,原发布时间为 2023-11-25 20:54:22

A

可以枚举所有可能的方案。

B

将所有 $a_i$ 值相同的 $i$ 组成一个连通块,那么需要两个连通块即可完成构造。

C

可以将操作进行逆转,并且逆转之后的情况是唯一的。

如果遇到循环就退出,循环节最长为 $n$。

D

首先降序排列 $b$,然后依次插入。

现在,试图设法让每次插入后答案都不变。

首先考虑插入位置左边,先假定插入的值小于等于左边的所有数,那么自然就能想到,只要插在第一个小于它的数左边,就能使答案不变。

双指针。

E

自然想到枚举 $len$。

问题是,$len$ 的取值范围可能很大。

但是,注意 $len$ 很大对应的是答案很可能为 $0$。

事实上,当 $\sum {r_i} - \sum {l_i} \ge \sum n_i$ 时,答案一定为 $0$。

而 $\sum n_i \le 10^5$。

然后就可以枚举了。

至于每个 $len$ 对应的答案,我的做法:

  • 第一步,每个 multiset 都要选择 $l_i$ 个,优选选择非 $len$ 的数值,如果实在不行,再取数字 $len$。记录这一部分必须选择的数字 $len$ 总数。
  • 第二步,由于需要再从所有 multiset 中选择 $len - \sum l_i$ 个数字,这一步需要统计所有 multiset 中第一步尚未选择且非 $len$ 数值的总数(即优先选择,不会对答案产生影响的数字总数),据此计算出必须选择的数字 len 总数(最终答案)。

需要扫一遍预处理。

CSP-S2023 游记 - 挂分最惨的一次

本文章由 WyOJ Shojo 从洛谷专栏拉取,原发布时间为 2023-09-10 14:15:13

预告

T3 挂 0,估分从 7 级线上直降 2=。

9.9 及之前

所以本来每天家里只用写半个点作业,硬是拖到 9:00 才能写完。

剩下时间刷 HaoBa 的 vjudge contest,或者打 CF/AT 现场赛。

zhengruioi 的模拟赛感觉比前几年水的多。

9.10

看到了准考证号,SD-S03101

9.11-9.16

继续正常刷题。

9.16 CSP-S1

上午 vp 了场 CF Div.3

ABCD 比较迅速,E 题降智很久才过。

*2000 的 F 题看上去不太好做,就写 *2200 的 G 题。

直接会了,写了 20min,然而在比赛最后 10min 被叫去打 CSP 了,悲。

看到很多人。

进去之后还有 1h,就各种摆烂。

包括但不限于,差分的前缀和的 $O(log^3)$ 解法。

还有就是看 lhx 写英语作业。

比赛开始。

完全没有复赛的紧张感。

就一题一题做,遇到染色那题,CCF 没说怎样染色合法,就乱选了一个。(错了)

还有道题没注意 unsigned short 自然溢出,算了半天才找出问题所在。

后面读程序,对于给了待解决任务的题目,我先把待解决任务解决,然后填空。

然后迅速干掉了第一个阅读程序。

第二个看不懂在干什么,蒙了 3 题。

第三个我会了做法,同样是 $O(n \log n )$分治,但是我的处理方法和给定程序截然不同,愣住了。

然后按照感觉进行选择。

我看到 if(l+1==r) return; 感觉挺奇怪,发现是左闭右开。

然后我脑子被宇宙射线轰击,选了 B。

然后结束了。

和 pt 对了对前面题的答案,发现不少不一样的,/jk。

回家发现记漏了后面一部分题答案。

剩下的题总共扣了 6pts。

如果运气极好,90+。

但也就 80 的期望分数,但原始答案的成绩绝对不低于 70。

9.21

打 Div.4,翻大车,但是 unrated 选手。

9.22

看了下那些强省的分数线,我看到的里面,S 组似乎没有超过 65 的。

看来没翻车,毕竟去年 noip 打出了强省省一的分数,今年过不了初赛分数线就太丢人了,

9.23

ABC321 回归青名(之前 AGC 爆零掉了下去)

9.26

CF Div.3 靠着手速上蓝成功,虽说 F 题失误了但还是完成了 flag。

9.27

去南京参加 HaoBa 集训。

第一天去南京的中山陵逛了逛。

然后两天一场模拟。

本来就菜,还各种挂分。

CF 还打得稀烂。

无法想象一个一年前平平无奇的,今年场场切 CF 3000+/ NOI+,把我踩在脚底下摩擦。

10.7

归程。

10.8

然而。。。。没有去上学。
停到赛前。

上午 HaoBa 模拟赛,被创飞了。

下午 CF Div.2,只过了 ABCD 还有巨大罚时,排名 886/9k。

然后无缝衔接,ARC,只过了 AB + 巨大罚时,排名 987/4319。

然而 CF 和 Atc 都小涨分。

10.9

CF Div.2 打得还行。

拥有了第二个 Expert 账号,啥时候能上紫啊。

10.20

出发。
在车上颓了会 MC。

开创造击杀了 Ender_dragon,就为了看终末诗,感觉写的很夸张。。。。。。感觉英文版的 “诗”和日常课本里面的中文诗风格区别挺大的。

然后颓 hornex.pro,单人打到 wv56。

然后 4 人组队到了 wv64。

中途:

不得不说饭真的很好吃。

10.21

上午开了几个纪录片。
顺便打会 hornex.pro。

出了 j 组题目后,看了看,把 T3,T4 做了。

下午 1:00 集合,有点小紧张。

广场上拍照,集体喊:“二中信竞,原神启动。”

然后就进场了。

打了个板子,静等开始。

先看 T4,感觉不太会做,扔了。

然后看 T1,感觉一眼题,先扔了。

然后看 T2,感觉可能不太好做,推了 5min 先扔了。

看 T3,是个大模拟,读完题,感觉前 13 个点是送的。

感觉 T1 最好写,先写了 T1。

写完一测,WA on sample2。

慌了,但是算了算,只有 8 种,但为什么答案是 10?????

我怀疑是不是 “幅度” 理解错了。

然后改了改,但答案算多了。

很慌。

不停地查错,但找不出来。

被迫去写 T2T3 暴力,但是用时不多,写完了。

要命的是都没有对应数据范围的大样例,只好自己造。

返回了继续看 T1,还是不知道为什么错。

比赛结束。

凉了。

T2,T4 都是原题。。。。。。。。

T2 还出现在了 9.5 HaoBa vjudge 题单里面,但我也不后悔当时没做,当时待做题目太多了,谁能想到这就是原题。

回来路上是在心有不甘,但没办法。

只能等 NOIP 翻盘了。

等一下,能不能进 noip 还不好说。

总之,做好了最坏打算。

T1 小图灵测了 80,后面不知道,总体上寄了。

庆幸没有被过多的往伤口上撒盐。

2023.10.22

T3 0分。
T3 0分。
T3 0分。
T3 0分。
T3 0分。
T3 0分。
T3 0分。
T3 0分。
T3 0分。
T3 0分。
T3 0分。
T3 0分。
T3 0分。
T3 0分。
T3 0分。
T3 0分。
T3 0分。
T3 0分。
T3 0分。
T3 0分。
T3 0分。
T3 0分。
T3 0分。
T3 0分。
T3 0分。
T3 0分。
T3 0分。
T3 0分。
T3 0分。

CSP-S2021 2023 年再度复盘

本文章由 WyOJ Shojo 从洛谷专栏拉取,原发布时间为 2023-09-15 00:00:43

做法应该忘得差不多了,那就复盘一下检验实力变化。

记录一下经历,懒得实现做法,做法正确性明天跟题解核对。

廊桥分配

要发现一个关键性质,然后就做出来了。

回文

菜死了,没做出来,预计 40pts。

括号序列

看上去像是个 CF 风格的 dp。

设左括号是 +1,右括号 -1,星号 0。
设 $dp_{i,j,k}$ 表示到 $i$ 位,前缀和是 $j$,已经有连续 $k$ 个星号。

然后似乎做出来了。

如果不幸假了,再不济也可以打个朴素暴力。

预计得分 15 或 100。

交通规划

只会朴素暴力。

ZR 截图留念

本文章由 WyOJ Shojo 从洛谷专栏拉取,原发布时间为 2023-09-17 14:47:15

这次本来估计最多涨 100。

由于可能是系统 bug 的原因,所有人的 rating delta 似乎加上了一个比较大的数,也可能是乘二。

然后我就获得了 1900+

现在发现 rating 即将重新计算。

截图留念,以后可能再也无法达到这个 rating 了。

Codeforces Round 898 (Div. 4)

本文章由 WyOJ Shojo 从洛谷专栏拉取,原发布时间为 2023-09-22 23:13:04

Out of competition。

打得稀烂,罚时拉满。

H 题 dfs 参数传错,wa on 2 到结束也没看出来。

A

把样例抄下来就行了。

B

$O(n)$ 枚举。

C

设横向深度为 $dep_x$,纵向深度为 $dep_y$。

$score = \min(dep_x,dep_y)$

D

$dp_i$ 代表 $i$ 结尾,清理完的最小花费。

转移考虑最后 $k$ 个是否使用清理。

对于不足 $k$ 个元素的区间,如果需要清理,答案为 $1$,赛时我在这里写错,吃了一发罚时。

E

二分板子题,赛时没开 long long 寄了两发。

F

枚举每个点作为右端点,计算出左端点最远能到哪里。

然后对每个点,算左端点,可以用二分或双指针,前者 $O(n \log n)$,后者 $O(n)$。

G

显然答案最多是 $A$ 的个数。

一个点作为 $B$,前面或后面的所有 $A$ 都可以被干掉,代价是干掉前面或后面后自己失效。

设 $pre_i$ 是区间 $[1,i]$ $A$ 的数量,$suf_i$ 是区间 $[i,n]$ $B$ 的数量。

可以枚举所有 $B$ 的位置,计算 $ans = \max_{1 \le i \le n} max(pre_i,suf_i)$。

然后对于所有 $B$ 的位置 $i$ ,考虑它的下一个 $B$ 的位置 $j$,计算 $max_{1 \le i \lt j \le n} (pre_i + suf_j) $,并对 $ans$ 取 max。

H

显然只有到环上才安全。

先把环找出来。

对于环外的点,到环上显然只有一条路径。

可以计算出 Valeriu 到环上的耗时,以及第一个到达的环上点。

如果 Marcel 不能在 Valeriu 到达环上之前(可以是同时到达)堵住这个环, Valeriu 必胜。

两次 dfs 找出环,两次 dfs 算出 Marcel 堵环耗时和 Valeriu 逃生耗时就好了。

我这个是比较麻烦的做法。

ABC321

本文章由 WyOJ Shojo 从洛谷专栏拉取,原发布时间为 2023-09-24 08:29:41

ABCD 秒杀,E 题经历 4 发罚时,95min 时通过。
然后从 ABCD 区头部到了 ABCDE 区尾部,performance+=60。

赛后读了 F,发现是个 jb 题。

A

模拟。

B

二分。

C

321-like 数量很少,直接搜。

D

前缀和+二分

E

考虑贡献分开计算。

F

加 $x$ 就 dp。
减 $x$ 消除对应 dp 影响。

Codeforces Round 900 (Div. 3)

本文章由 WyOJ Shojo 从洛谷专栏拉取,原发布时间为 2023-09-27 11:24:46

过了 5 题,F 题会正解没调出来。

在等 System Test 结果,届时若不 FST,就上蓝了。

若没 FST 再来填坑。

P7453

本文章由 WyOJ Shojo 从洛谷专栏拉取,原发布时间为 2023-10-01 23:00:16

题解:

#include <bits\/stdc++.h>
using namespace std;
#define FOR(i, a, b) for (int i = a; i <= b; i++)
#define REP(i, a, b) for (int i = a; i >= b; i--)
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 250005;
const ll mod = 998244353;
ll qpow(ll a, ll b)
{
    ll ret = 1;
    while (b)
    {
        if (b & 1)
            ret = ret * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ret;
}
ll inv(ll a)
{
    return qpow(a, mod - 2);
}
int n, m;
ll a[maxn], b[maxn], c[maxn];
struct Matrix
{
    ll mp[3][3];
    void init()
    {
        memset(mp, 0, sizeof mp);
    }
    void unit()
    {
        memset(mp, 0, sizeof mp);
        mp[0][0] = mp[1][1] = mp[2][2] = 1;
    }
    bool isunit()const
    {
        if (mp[0][0] != 1)
            return 0;
        if (mp[0][1] != 0)
            return 0;
        if (mp[0][2] != 0)
            return 0;
        if (mp[1][0] != 0)
            return 0;
        if (mp[1][1] != 1)
            return 0;
        if (mp[1][2] != 0)
            return 0;
        if (mp[2][0] != 0)
            return 0;
        if (mp[2][1] != 0)
            return 0;
        if (mp[2][2] != 1)
            return 0;
        return 1;
    }
    bool iszero()const
    {
        if (mp[0][0] != 0)
            return 0;
        if (mp[0][1] != 0)
            return 0;
        if (mp[0][2] != 0)
            return 0;
        if (mp[1][0] != 0)
            return 0;
        if (mp[1][1] != 0)
            return 0;
        if (mp[1][2] != 0)
            return 0;
        if (mp[2][0] != 0)
            return 0;
        if (mp[2][1] != 0)
            return 0;
        if (mp[2][2] != 0)
            return 0;
        return 1;
    }
    Matrix operator+(const Matrix &b) const
    {
        Matrix res;
        res.mp[0][0] = mp[0][0] + b.mp[0][0];
        res.mp[0][0] %= mod;
        res.mp[0][1] = mp[0][1] + b.mp[0][1];
        res.mp[0][1] %= mod;
        res.mp[0][2] = mp[0][2] + b.mp[0][2];
        res.mp[0][2] %= mod;
        res.mp[1][0] = mp[1][0] + b.mp[1][0];
        res.mp[1][0] %= mod;
        res.mp[1][1] = mp[1][1] + b.mp[1][1];
        res.mp[1][1] %= mod;
        res.mp[1][2] = mp[1][2] + b.mp[1][2];
        res.mp[1][2] %= mod;
        res.mp[2][0] = mp[2][0] + b.mp[2][0];
        res.mp[2][0] %= mod;
        res.mp[2][1] = mp[2][1] + b.mp[2][1];
        res.mp[2][1] %= mod;
        res.mp[2][2] = mp[2][2] + b.mp[2][2];
        res.mp[2][2] %= mod;
        return res;
    }
    Matrix operator*(const Matrix &b) const
    {
        Matrix res;
        res.init();
        res.mp[0][0] += mp[0][0] * b.mp[0][0];
        res.mp[0][1] += mp[0][0] * b.mp[0][1];
        res.mp[0][2] += mp[0][0] * b.mp[0][2];
        res.mp[0][0] += mp[0][1] * b.mp[1][0];
        res.mp[0][1] += mp[0][1] * b.mp[1][1];
        res.mp[0][2] += mp[0][1] * b.mp[1][2];
        res.mp[0][0] += mp[0][2] * b.mp[2][0];
        res.mp[0][1] += mp[0][2] * b.mp[2][1];
        res.mp[0][2] += mp[0][2] * b.mp[2][2];
        res.mp[1][0] += mp[1][0] * b.mp[0][0];
        res.mp[1][1] += mp[1][0] * b.mp[0][1];
        res.mp[1][2] += mp[1][0] * b.mp[0][2];
        res.mp[1][0] += mp[1][1] * b.mp[1][0];
        res.mp[1][1] += mp[1][1] * b.mp[1][1];
        res.mp[1][2] += mp[1][1] * b.mp[1][2];
        res.mp[1][0] += mp[1][2] * b.mp[2][0];
        res.mp[1][1] += mp[1][2] * b.mp[2][1];
        res.mp[1][2] += mp[1][2] * b.mp[2][2];
        res.mp[2][0] += mp[2][0] * b.mp[0][0];
        res.mp[2][1] += mp[2][0] * b.mp[0][1];
        res.mp[2][2] += mp[2][0] * b.mp[0][2];
        res.mp[2][0] += mp[2][1] * b.mp[1][0];
        res.mp[2][1] += mp[2][1] * b.mp[1][1];
        res.mp[2][2] += mp[2][1] * b.mp[1][2];
        res.mp[2][0] += mp[2][2] * b.mp[2][0];
        res.mp[2][1] += mp[2][2] * b.mp[2][1];
        res.mp[2][2] += mp[2][2] * b.mp[2][2];
        res.mp[0][0] %= mod;
        res.mp[0][1] %= mod;
        res.mp[0][2] %= mod;
        res.mp[1][0] %= mod;
        res.mp[1][1] %= mod;
        res.mp[1][2] %= mod;
        res.mp[2][0] %= mod;
        res.mp[2][1] %= mod;
        res.mp[2][2] %= mod;
        return res;
    }
    Matrix operator*(const ll &b)
    {
        Matrix res;
        res.mp[0][0] = mp[0][0] * b;
        res.mp[0][0] %= mod;
        res.mp[0][1] = mp[0][1] * b;
        res.mp[0][1] %= mod;
        res.mp[0][2] = mp[0][2] * b;
        res.mp[0][2] %= mod;
        res.mp[1][0] = mp[1][0] * b;
        res.mp[1][0] %= mod;
        res.mp[1][1] = mp[1][1] * b;
        res.mp[1][1] %= mod;
        res.mp[1][2] = mp[1][2] * b;
        res.mp[1][2] %= mod;
        res.mp[2][0] = mp[2][0] * b;
        res.mp[2][0] %= mod;
        res.mp[2][1] = mp[2][1] * b;
        res.mp[2][1] %= mod;
        res.mp[2][2] = mp[2][2] * b;
        res.mp[2][2] %= mod;
        return res;
    }
};
struct SegmentTree
{
    Matrix val[maxn << 2];
    Matrix mul[maxn << 2];
    Matrix add[maxn << 2];
    int L[maxn << 2], R[maxn << 2];
    int len(int pos)
    {
        return R[pos] - L[pos] + 1;
    }
    void pushup(int pos)
    {
        val[pos].mp[0][0]=val[pos<<1].mp[0][0]+val[pos<<1|1].mp[0][0];
        val[pos].mp[0][1]=val[pos<<1].mp[0][1]+val[pos<<1|1].mp[0][1];
        val[pos].mp[0][2]=val[pos<<1].mp[0][2]+val[pos<<1|1].mp[0][2];
        val[pos].mp[0][0]%=mod;
        val[pos].mp[0][1]%=mod;
        val[pos].mp[0][2]%=mod;
    }
    void Add(int pos, ll _val, int id)
    {
        Matrix ml, ad;
        if (id == 1)
        {
            ml.init();
            ml.mp[0][0] = ml.mp[1][0] = ml.mp[1][1] = ml.mp[2][2] = 1;
            ad.init();
        }
        else if (id == 2)
        {
            ml.init();
            ml.mp[0][0] = ml.mp[1][1] = ml.mp[2][1] = ml.mp[2][2] = 1;
            ad.init();
        }
        else if (id == 3)
        {
            ml.init();
            ml.mp[0][0] = ml.mp[1][1] = ml.mp[2][2] = ml.mp[0][2] = 1;
            ad.init();
        }
        else if (id == 4)
        {
            ml.unit();
            ad.init();
            ad.mp[0][0] = _val;
        }
        else if (id == 5)
        {
            ml.init();
            ml.mp[0][0] = 1;
            ml.mp[1][1] = _val;
            ml.mp[2][2] = 1;
            ad.init();
        }
        else if (id == 6)
        {
            ml.init();
            ml.mp[0][0] = 1;
            ml.mp[1][1] = 1;
            ad.init();
            ad.mp[0][2] = _val;
        }
        val[pos] = val[pos] * ml;
        val[pos] = val[pos] + ad * len(pos);
        mul[pos] = mul[pos] * ml;
        add[pos] = add[pos] * ml;
        add[pos] = add[pos] + ad;
    }
    void pushdown(int pos)
    {
        if (!mul[pos].isunit())
        {
            val[pos << 1] = val[pos << 1] * mul[pos];
            mul[pos << 1] = mul[pos << 1] * mul[pos];
            add[pos << 1] = add[pos << 1] * mul[pos];
            val[pos << 1 | 1] = val[pos << 1 | 1] * mul[pos];
            mul[pos << 1 | 1] = mul[pos << 1 | 1] * mul[pos];
            add[pos << 1 | 1] = add[pos << 1 | 1] * mul[pos];
            mul[pos].unit();
        }
        if (!mul[pos].iszero())
        {
            val[pos << 1] = val[pos << 1] + add[pos] * len(pos << 1);
            add[pos << 1] = add[pos << 1] + add[pos];
            val[pos << 1 | 1] = val[pos << 1 | 1] + add[pos] * len(pos << 1 | 1);
            add[pos << 1 | 1] = add[pos << 1 | 1] + add[pos];
            add[pos].init();
        }
    }
    void build(int pos, int l, int r)
    {
        L[pos] = l, R[pos] = r;
        mul[pos].unit();
        add[pos].init();
        if (l == r)
        {
            val[pos].init();
            val[pos].mp[0][0] = a[l];
            val[pos].mp[0][1] = b[l];
            val[pos].mp[0][2] = c[l];
            return;
        }
        int mid = (l + r) >> 1;
        build(pos << 1, l, mid);
        build(pos << 1 | 1, mid + 1, r);
        pushup(pos);
    }
    void chg(int pos, int l, int r, ll _val, int id)
    {
        if (R[pos] < l || L[pos] > r)
            return;
        if (L[pos] >= l && R[pos] <= r)
        {
            Add(pos, _val, id);
            return;
        }
        pushdown(pos);
        int mid = (L[pos] + R[pos]) >> 1;
        if (mid >= l)
            chg(pos << 1, l, r, _val, id);
        if (mid < r)
            chg(pos << 1 | 1, l, r, _val, id);
        pushup(pos);
    }
    Matrix query(int pos, int l, int r)
    {
        if (R[pos] < l || L[pos] > r)
        {
            Matrix res;
            res.init();
            return res;
        }
        if (L[pos] >= l && R[pos] <= r)
        {
            return val[pos];
        }
        pushdown(pos);
        int mid = (L[pos] + R[pos]) >> 1;
        Matrix res;
        res.init();
        if (mid >= l)
            res = res + query(pos << 1, l, r);
        if (mid < r)
            res = res + query(pos << 1 | 1, l, r);
        return res;
    }
} SGT;
int main()
{
    scanf("%d", &n);
    FOR(i, 1, n)
    {
        scanf("%lld%lld%lld", &a[i], &b[i], &c[i]);
    }
    SGT.build(1, 1, n);
    scanf("%d", &m);
    while (m--)
    {
        int op, l, r;
        ll v;
        scanf("%d%d%d", &op, &l, &r);
        if (op == 1)
        {
            SGT.chg(1, l, r, -1, 1);
        }
        else if (op == 2)
        {
            SGT.chg(1, l, r, -1, 2);
        }
        else if (op == 3)
        {
            SGT.chg(1, l, r, -1, 3);
        }
        else if (op == 4)
        {
            scanf("%lld", &v);
            SGT.chg(1, l, r, v, 4);
        }
        else if (op == 5)
        {
            scanf("%lld", &v);
            SGT.chg(1, l, r, v, 5);
        }
        else if (op == 6)
        {
            scanf("%lld", &v);
            SGT.chg(1, l, r, v, 6);
        }
        else if (op == 7)
        {
            Matrix ans = SGT.query(1l, l, r);
            printf("%lld %lld %lld\n", ans.mp[0][0], ans.mp[0][1], ans.mp[0][2]);
        }
    }
    return 0;
}  
共 320 篇博客