圆圈舞

春天温暖的阳光照耀着大地，正是草原上的小动物们最快乐的时候。小动物们在草原上开了一个舞会，欢度这美好的时光。
　　
舞会上最重要的一个环节就是跳圆舞曲，n只小动物手拉手围成一大圈，随着音乐跳起来。在跳的过程中，小动物们可能会变换队形。
它们的变换方式是动物A松开自己右手，动物B松开自己的左手，动物A和B手拉到一起，而它们对应的松开的手（如果有的话）也拉到一起。
　　
例如，假设有10只小动物，按顺序围成一圈，动物1的右手拉着动物2的左手，动物2的右手拉着动物3的左手，依次类推，最后动物10的右手拉着动物1的左手。
如果通过动物2和8变换队形，则动物02的右手拉着动物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)HjFi。在跳舞的过程中，动物们的欢乐值和感动值有可能发生变化。
　　
圆舞曲开始的时候，所有的动物按编号顺序围成一个圈，动物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
　
【数据规模与约定】
对于20%的数据，2<=n,m<=100。
对于30%的数据，2<=n,m<=1000。
另有20%的数据，只有k=1的操作且Hi,Fi均为1。
另有20%的数据，只有k=1或2的操作且Fi均为1。
对于100%的数据，2<=n,m<=100000，0<=Hi,Fi<=10^{9，1<=k<=3，k=1时1<=p,q<=n且p≠q，k=2或3时1<=p<=n且0<=q<=10}9。
　
资源约定：
峰值内存消耗 < 256M
CPU消耗 < 5000ms
　
请严格按要求输出，不要画蛇添足地打印类似：“请您输入…” 的多余内容。
　
所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。
注意：不要使用package语句。不要使用jdk1.7及以上版本的特性。
注意：主类的名字必须是：Main，否则按无效代码处理。

因为蓝桥杯官网没有提供这道题的测试用例，所以我是在dotcpp上测试的，虽然AC了，但是不知道会不会有哪里有问题。。
代码仅供参考，萌新第一次发文欢迎dalao指点（没错我不会打markdown）

import java.util.LinkedList;
import java.util.Scanner;

public class D6 {
	//	存放各个数的情况，[n][0]代表欢乐值,[n][1]代表感动值,[n][2]代表所在圈
	static int[][] arr;
	//	保存所有圈的情况
	static LinkedList<LinkedList<Integer>> lists = new LinkedList<LinkedList<Integer>>();
	public static void main(String[] args) {
		/*
		 * 大致思路：
		 * ①链表lists存放所有圈，初始有一个list，值为1-9
		 * 	10个数，数组arr[n+1][3]存放欢乐值和感动值，以及所在圈数
		 * ②获取m行
		 * 	第一个数为1，先变圈
		 * 	第一个数为2，改变欢乐值
		 * 	第一个数为3，改变感动值
		 * 执行完上一次操作后进行计算欢乐能量
		 * 
		 * ③如何变圈，有两个参数(i,j)：
		 * 	获得arr[i][2]与arr[j][2]，分别为ii，jj为所在圈
		 * 	当ii==jj，即两个数在同一个圈
		 * 		一直挪动第一个到最后，直到第一个等于i，然后直到遇见j之前，将所有的数放到新的链表里面，并加入所有圈的lists
		 * 	当ii!=jj，即两个数不在同一个圈
		 * 		将其中一个，例如含有j的链表B，一直挪动第一个到最后，直到第一个等于j，将此时的链表B插入到链表A（含有i的链表）
		 * 		中i之后
		 * ④计算欢乐能量
		 * 	遍历lists中的list
		 * 	记录list的大小size，操作size次
		 * 	移动第一个数到链表末尾
		 * 	循环链表中的[1,size-1]区间中的数
		 * 	欢乐能量+=(size-p)*(当前位置的欢乐值)*(正在遍历的位置的感动值) p=当前的索引
		 * 	返回欢乐能量
		 */
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		arr = new int[n + 1][3];
		LinkedList<Integer> initList = new LinkedList<Integer>();
		for (int i = 1; i <= n; i++) {
			// 0为欢乐值 1为感动值
			arr[i][0] = scanner.nextInt();
			arr[i][1] = scanner.nextInt();
			initList.add(i);
		}
		// 添加初始链表
		lists.add(initList);
		int m = scanner.nextInt();
		for (int i = 0; i < m; i++) {
			int k = scanner.nextInt(), p = scanner.nextInt(), q = scanner.nextInt();
			if (k == 1) {
				// 变换队形
				change(p, q);
			} else if (k == 2) {
				// 改变欢乐值
				arr[p][0] = q;
			} else if (k == 3) {
				// 改变感动值
				arr[p][1] = q;
			}
			// 计算欢乐能量
			caculate();
		}
	}

	private static void caculate() {
		long sum = 0;
		// 遍历lists中的list
		for (LinkedList<Integer> list : lists) {
			int size = list.size();
			int temp = size;
			// 记录list的大小size，操作size
			while (temp-- > 0) {
				// 移动第一个数到链表末尾
				list.add(list.remove());
				// 循环链表中的[1,size-1]区间中的数
				for (int i = 1; i < size; i++) {
					// 欢乐能量+=(size-当前索引)*(当前位置的欢乐值)*(正在遍历的位置的感动值)
					sum = (sum + (size - i) * arr[list.get(0)][0] * arr[list.get(i)][1]) % 1000000007;
				}
			}
		}
		// 输出结果
		System.out.println(sum);
	}

	private static void change(int i, int j) {
		// 记录i所在的圈
		int ii = arr[i][2];
		// 记录j所在的圈
		int jj = arr[j][2];
		if (ii == jj) {
			// 如果两个数字在同一个圈内

			LinkedList<Integer> linkedList = lists.get(ii);
			// 一直挪动第一个到最后，直到第一个等于i
			while (linkedList.getFirst() != i) {
				linkedList.add(linkedList.remove());
			}
			// 然后直到遇见j之前，将所有的数放到新的链表里面
			LinkedList<Integer> newLinkedList = new LinkedList<Integer>();
			while (linkedList.get(1) != j) {
				newLinkedList.add(linkedList.remove(1));
			}
			// 如果新链表不为空，将其放入所有圈的lists
			if (!newLinkedList.isEmpty()) {
				lists.add(newLinkedList);
				for (Integer integer : newLinkedList) {
					// 更新圈数
					arr[integer][2] = lists.size() - 1;
				}
			}
		} else {
			// 如果不在同一个圈内
			LinkedList<Integer> AList = lists.get(ii);
			LinkedList<Integer> BList = lists.get(jj);
			// 将其中一个，例如含有j的链表B，一直挪动第一个到最后，直到第一个等于j
			while (BList.getFirst() != j) {
				BList.add(BList.remove());
			}
			// 将此时的链表B插入到链表A（含有i的链表）中i之后
			while (AList.getFirst() != i) {
				AList.add(AList.remove());
			}
			// 移除i
			AList.add(AList.remove());
			for (Integer integer : BList) {
				arr[integer][2] = ii;
			}
			AList.addAll(0, BList);
			// 去掉多余的链表
			lists.remove(BList);
		}
	}
}