A40848. 圆圈舞
题目描述
圆圈舞
题目描述
春天温暖的阳光照耀着大地，正是草原上的小动物们最快乐的时候。小动物们在草原上开了一个舞会，欢度这美好的时光。
舞会上最重要的一个环节就是跳圆舞曲，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)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
参考答案
import java.util.LinkedList;
import java.util.Scanner;
import java.util.Vector;
public class 圆圈舞 {
public static int n,m,HF[];
public static LinkedList<person> list1=new LinkedList<>();
public static Vector<LinkedList<person>> v=new Vector<>();
public static void main(String[] args) {
Scanner s=new Scanner(System.in);
n=s.nextInt();
for(int i=0;i<n;i++){
person p=new person(i+1);
p.setHi(s.nextInt());
p.setFi(s.nextInt());
list1.add(p);
}
v.add(list1);
m=s.nextInt();
HF=new int[m];
for(int i=0;i<m;i++){
int a=s.nextInt();
int b=s.nextInt();
int c=s.nextInt();
if(a==1){
change(b,c);
HF[i]=count();
}
else if(a==2){//换欢乐值
changeHi(b,c);
HF[i]=count();
}
else if(a==3){//换感动值
changeFi(b,c);
HF[i]=count();
}
}
for(int i=0;i<m;i++){
System.out.println(HF[i]);
}
}
public static int count(){
int sumHF=0;
int a=v.size();
for(int i=0;i<a;i++){
for(int j=0;j<v.get(i).size();j++){
int count=0;
for(int k=j+1;k<v.get(i).size();k++){
sumHF+=(v.get(i).size()-(k-j))*v.get(i).get(k).getHi()*v.get(i).get(k).getFi();
count++;
}
if(count!=v.get(i).size()-1){
for(int k=0;k<(v.get(i).size()-1-count);k++){
sumHF+=(j-k)*v.get(i).get(k).getHi()*v.get(i).get(k).getFi();
}
}
}
}
return sumHF%1000000007;
}
public static void changeHi(int n1,int n2){//欢乐值
int a=seek(n1);
person p=new person(0);
LinkedList<person> lista=v.get(a);
for(int i=0;i<lista.size();i++){
if(lista.get(i).getname()==n1){
p=lista.get(i);
break;
}
}
p.setHi(n2);
}
public static void changeFi(int n1,int n2){//感动值
int a=seek(n1);
person p=new person(0);
LinkedList<person> lista=v.get(a);
for(int i=0;i<lista.size();i++){
if(lista.get(i).getname()==n1){
p=lista.get(i);
break;
}
}
p.setFi(n2);
}
public static void change(int n1,int n2){//交换位置
person p1=new person(0);
person p2=new person(0);
int c=seek(n1);
int d=seek(n2);
LinkedList<person> lista=v.get(c);
LinkedList<person> listb=v.get(d);
if(c==d){//在同一队列
LinkedList<person> pk=new LinkedList<>();
for(int i=0;i<lista.size();i++){
if(lista.get(i).getname()==n1)
p1=lista.get(i);
if(lista.get(i).getname()==n2)
p2=lista.get(i);
}
if(lista.indexOf(p1)<lista.indexOf(p2)){
for(int i=lista.indexOf(p1)+1;lista.indexOf(p2)!=lista.indexOf(p1)+1;){
pk.add(lista.get(i));
lista.remove(i);
}
}else{
int h=lista.indexOf(p1);
int k=lista.indexOf(p2);
person l=lista.get(h+1);
for(int i=k;lista.indexOf(l)!=k;){
pk.add(lista.get(i));
lista.remove(i);
}
}
v.add(pk);
}else{//不在同一队列
for(int i=0;i<lista.size();i++){
if(lista.get(i).getname()==n1){
p1=lista.get(i);
break;
}
}
for(int i=0;i<listb.size();i++){
if(listb.get(i).getname()==n2){
p2=listb.get(i);
break;
}
}
while(lista.indexOf(p1)!=lista.size()-1){
lista.add(lista.getFirst());
lista.removeFirst();
}
for(int i=listb.indexOf(p2);i<listb.size();i++){
lista.add(listb.get(i));
}
for(int i=0;i<listb.indexOf(p2);i++){
lista.add(listb.get(i));
}
v.remove(listb);
}
}
public static int seek(int n1){//寻找该人在哪个队列
int a=0;
for(int i=0;i<v.size();i++){
for(int j=0;j<v.get(i).size();j++){
if(v.get(i).get(j).getname()==n1){
a=i;
}
}
if(a!=0)
break;
}
return a;
}
}
class person{//定义一个类 存放每个人的信息
private int Hi,Fi,HF;
private int name;
person(int name){
this.name=name;
}
public int getname(){
return name;
}
public void setHi(int i){
this.Hi=i;
}
public int getHi(){
return Hi;
}
public void setFi(int i){
this.Fi=i;
}
public int getFi(){
return Fi;
}
public void setHF(int i){
this.HF=i;
}
public int getHF(){
return HF;
}
}