Does the order of the substitution matter? If not, try:

my %subst;
@subst{@first_half} = @second_half;
s/\Q$_\E/$subst{$_}/ for keys %subst;
[download]

Or if order does matter:

for (my $i = 0; $i < @first_half; $i++) {
    s/\Q$first_half[$i]\E/$second_half[$i]/;
}
[download]

You may want to remove the \Q\E from each s/// if the REs aren't just strings, but have meta-chars in them, and you'll have to bind the s/// to whatever variable has the line in it too, of course.