自动搬运

查看原文

来自洛谷，原作者为

	Dream_weavers printf("Hello, World!");

搬运于2025-08-24 22:37:57，当前版本为作者最后更新于2022-05-01 15:46:13，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意

有一个长度为 $n$ 的序列 $a$，对这个序列进行 $m$ 次操作，得到序列 $b$，操作类型具体如下：

• 1 x y 表示第 $x$ 个元素加上第 $y$ 个元素。

• 2 x y 表示第 $x$ 个元素乘上第 $y$ 个元素。

如果 $x=y$，那新的 $x$ 就等于原来的 $x$ 的两倍或平方。

现在给出序列 $b$ 和 $m$ 次操作，请还原出序列 $a$。

思路

体面看起来挺吓唬人，甚至线段树的题刷多了还以为是线段树，但就是一道简单的模拟。

建一些数组或一个结构体记录这些操作，然后逆序进行操作。这里逆序指操作顺序相反，加变成减（$b_x-b_y$），乘变成除（$b_x\div b_y$）。如果 $x=y$ 就要特判一下，两倍变成除以二（$b_x\div2$），平方变成开方（$\sqrt{b_x}$）。最后就能还原出序列 $a$。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5;
int n,m,b[N];
struct node{//建一个记录操作的结构体
	int opt,x,y;
}f[N];
signed main(){
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n;i++)scanf("%lld",&b[i]);
	for(int i=1;i<=m;i++){//输入操作
		scanf("%lld%lld%lld",&f[i].opt,&f[i].x,&f[i].y);
	}
	for(int i=m;i>0;i--){//进行“逆序”操作
		int opt=f[i].opt,x=f[i].x,y=f[i].y;
		if(opt==1){
			if(x!=y)b[x]-=b[y];
			else b[x]/=2;//特判x=y
		}else if(opt==2){
			if(x!=y)b[x]/=b[y];
			else b[x]=sqrt(b[x]);//特判x=y
		}
	}
	for(int i=1;i<=n;i++)printf("%lld ",b[i]);//还原
    return 0;
}