我的方法使用了动态规划和树状数组，可能并不简洁，但题解太简略了，我暂时也不清楚怎么简单地维护题解里的 uu 和 vv，其他部分是原题解的详细版本。

首先分析一下操作（方便描述，标了个号）：

  1. 将 aa 循环左移一位。若在进行操作前 a1≠0a_1\neq 0，则消耗 xx 点代价。
  2. 将 aa 循环右移一位。若在进行操作前 a1≠0a_1\neq 0，则消耗 yy 点代价。
  3. 交换 x,yx,y。消耗 zz 点代价。
  4. 若 a1=b1a_1=b_1，将 bb 循环左移一位，同时令 a1=0a_1=0。不消耗代价。

题目中出现了大量的循环位移操作，实际上可以对其进行简化分析，因为题目要求把 aa 清空，那么我们将每一个 44 操作当作一个阶段，于是，题目要求按照 bb 数组的顺序完成 nn 个阶段的操作，每个阶段消掉一个数字，消掉数字的顺序就是 bb 数组的顺序（这样，操作 44 中的循环移位解决掉了）。

移动整个数组并不好处理，因此可以理解为移动环上的指针。于是转化 11 和 22 操作，最后的描述可以变为：

令指针 pp 指向 a1a_1。有如下操作：

  1. 将指针右移一位，若原指向点不为 00，消耗 xx 点代价。
  2. 将指针左移一位，若原指向点不为 00，消耗 yy 点代价。
  3. 交换 x,yx,y。消耗 zz 点代价。
    指针要依次移动到 bb 数组标记的每一个位置，完成 nn 个阶段。

注意：移动指针与移动数组相反；指针在 00 的移动没有代价！

那么，先把每一个阶段要求到达的位置处理出来，这样就没有两个数组了。因为都是排列，所以可以把 aa 中数字位置处理到 pp 数组，即 p[a[i]]=i，再把 bb 中的每一个数字对应成 aa 中的位置，按顺序记录，详见代码。

入手点是 33 操作，可以发现，在每一个阶段，一定只会使用 11 和 22 操作中的一种，操作 33 至多 11 次且在开始（将结尾的操作 33 归为下一阶段）。考虑到只有操作 33 有后效性，利用它来设计状态：

  • dp0,idp_{0,i} 表示进行过偶数次操作 33，这时 11 和 22 操作代价和开始时一样。
  • dp1,idp_{1,i} 表示进行过奇数次操作 33，这时 11 和 22 操作代价和开始时相反。

设计转移（这应该是比较好想的）：

  • dp0,i=max⁡{dp0,i−1+stepsleft×x,dp0,i−1+stepsright×y,dp1,i−1+stepsleft×y+z,dp1,i−1+stepsright×x+z}dp_{0,i}=\max\{dp_{0,i-1}+steps_{left}\times x,dp_{0,i-1}+steps_{right}\times y,dp_{1,i-1}+steps_{left}\times y+z,dp_{1,i-1}+steps_{right}\times x+z\}
  • dp1,i=max⁡{dp1,i−1+stepsleft×y,dp1,i−1+stepsright×x,dp0,i−1+stepsleft×x+z,dp0,i−1+stepsright×y+z}dp_{1,i}=\max\{dp_{1,i-1}+steps_{left}\times y,dp_{1,i-1}+steps_{right}\times x,dp_{0,i-1}+steps_{left}\times x+z,dp_{0,i-1}+steps_{right}\times y+z\}

设计边界：

  • dp0,1=0dp_{0,1}=0
  • dp1,1=zdp_{1,1}=z

这里重点处理 stepsleftsteps_{left} 和 stepsrightsteps_{right}，具体地，每一个 00 位置都不算贡献，要求一种可以动态修改和区间查询的数据结构，想到线段树和树状数组。但是在比赛中，线段树由于常数问题（也许）被卡掉了，改用了树状数组，具体逻辑就是把未清空的位置设为 11，清空后改为 00，用区间和处理步数，详见代码。

输出的答案便是 min⁡{dp0,n,dp1,n}\min\{dp_{0,n},dp_{1,n}\} 了。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,x,y,z;
struct BIT{
  int t[2000006],tot;
  void init(){
    memset(t,0,sizeof(t));
    tot=0;
  }
  void add(int i,int val=1){
	  if(i==0)return;
    tot++;
    for(;i<=n;i+=(i&-i)){
      t[i]+=val;
    }
  }
  int query(int i){
    int s=0;
    for(;i;i-=(i&-i)){
      s+=t[i];
    }
    return s;
  }
}bit;
int a[1000006],p[1000006];
int dp[2][1000006];
int q(int l,int r){
	return bit.query(r)-bit.query(l-1);
}
int left(int now,int to){
//	return now>=to?now-to:n+now-to;
//	return now>=to?SegTree.query(1,to+1,now):SegTree.query(1,1,now)+SegTree.query(1,to+1,n);
	return now>=to?q(to+1,now):q(1,now)+q(to+1,n);
}
int l1(int x){
	return x-1==0?n:x-1;
}
int right(int now,int to){
//	return now<=to?to-now:n+to-now;
//	return now<=to?SegTree.query(1,now,to-1):SegTree.query(1,now,n)+SegTree.query(1,1,to-1);
	return now<=to?q(now,to-1):q(now,n)+q(1,to-1);
}
int r1(int x){
	return x+1==n?1:x+1;
}
void solve(){
	scanf("%lld%lld%lld%lld",&n,&y,&x,&z);
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
		p[a[i]]=i;
//		SegTree.dat[i]=1;
	}
//	SegTree.build(1,1,n);
	bit.init();
	for(int i=1;i<=n;i++){
		bit.add(i);	
		int tmp;
		scanf("%lld",&tmp);
		a[p[tmp]]=i;
	}
	for(int i=1;i<=n;i++){
		p[a[i]]=i;
	}
	p[0]=1;
	dp[0][1]=0;
	dp[1][1]=z;
	for(int i=1;i<=n;i++){
		int L=left(p[i-1],p[i]);
		int R=right(p[i-1],p[i]);
		dp[0][p[i]]=min({
				dp[0][p[i-1]]+L*x,
				dp[0][p[i-1]]+R*y,
				dp[1][p[i-1]]+L*y+z,
				dp[1][p[i-1]]+R*x+z
		});
		dp[1][p[i]]=min({
				dp[1][p[i-1]]+L*y,
				dp[1][p[i-1]]+R*x,
				dp[0][p[i-1]]+L*x+z,
				dp[0][p[i-1]]+R*y+z,
		});
		bit.add(p[i],-1);
	}
	printf("%lld\n",min(dp[0][p[n]],dp[1][p[n]]));
}
signed main(){
#ifdef USE_FILE_IO
	freopen("code.in","r",stdin);
	cerr<<"[File IO]"<<endl;
#endif
	int t=1;
//	cin>>t;
	while(t--){
		solve();
	}
	return 0;
}