Dotcpp  >  编程题库  >  蓝桥杯2016年第七届真题-圆圈舞
题目 1836:

蓝桥杯2016年第七届真题-圆圈舞

时间限制: 3s 内存限制: 192MB 提交: 102 解决: 66

题目描述

春天温暖的阳光照耀着大地,正是草原上的小动物们最快乐的时候。小动物们在草原上开了一个舞会,欢度这美好的时光。

舞会上最重要的一个环节就是跳圆舞曲,n只小动物手拉手围成一大圈,随着音乐跳起来。在跳的过程中,小动物们可能会变换队形。它们的变换方式是动物A松开自己右手,动物B松开自己的左手,动物A和B手拉到一起,而它们对应的松开的手(如果有的话)也拉到一起。

例如,假设有10只小动物,按顺序围成一圈,动物1的右手拉着动物2的左手,动物2的右手拉着动物3的左手,依次类推,最后动物10的右手拉着动物1的左手。如果通过动物2和8变换队形,则动物2的右手拉着动物8的左手,而对应的动物3的左手拉着动物7的右手,这样形成了1-2-8-9-10和3-4-5-6-7两个圈。如果此时通过动物2和6变换队形,则将形成1-2-6-7-3-4-5-8-9-10一个大圈。注意,如果此时通过动物1和2变换队形,那么队形不会改变,因为动物1的右手和动物2的左手松开后又拉到一起了。

在跳舞的过程中,每个动物i都有一个欢乐值Hi和一个感动值Fi。
如果两个动物在一个圈中,欢乐值会彼此影响,产生欢乐能量。如果两个动物i, j(i≠j)在同一个大小为t的圈中,而动物i在动物j右手的第p个位置(动物j右手的第1个位置就是动物j右手所拉着的动物,而第2个位置就是右手第1个位置的动物右手拉着的动物,依次类推),则产生的欢乐能量为(t-p)*Hj*Fi。在跳舞的过程中,动物们的欢乐值和感动值有可能发生变化。

圆舞曲开始的时候,所有的动物按编号顺序围成一个圈,动物n右手的第i个位置正好是动物i。现在已知小动物们变换队形的过程和欢乐值、感动值变化的过程,求每次变换后所有动物所产生的欢迎能量之和。

输入格式

输入的第一行包含一个整数n,表示动物的数量。
接下来n行,每行两个用空格分隔的整数Hi, Fi,按编号顺序给出每只动物的欢乐值和感动值。
接下来一行包含一个整数m,表示队形、欢乐值、感动值的变化次数。
接下来m行,每行三个用空格分隔的整数k, p, q,当k=1时,表示小动物们通过动物p和动物q变换了队形,当k=2时,表示动物p的欢乐值变为q,当k=3时,表示动物p的感动值变为了q。

输出格式

输出m行,每行一个整数,表示每次变化后所有动物产生的能量之和。
答案可能很大,你需要计算答案除以1000000007的余数。

样例输入

10
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
9
1 2 8
1 2 6
2 8 10
3 5 10
1 1 2
1 2 1
2 5 5
1 4 8
1 4 5

样例输出

100
450
855
1341
1341
811
923
338
923

提示

零基础的同学可以先学习基础,教程见:  C语言教程C++教程编译器教程数据结构教程Python教程单片机教程

视频教学见视频网课

标签