I've had a go at running a benchmark. If I've not made a mess of it, the pure masking solution seems to be by far the quickest.

use strict;
use warnings;

use Benchmark q{cmpthese};

my $str  = q{AGACGAGTA} x 12000;
my $mask = qq{\xFF}     x length $str;
my $x    = q{x}         x length $str;

my @toMask = (
   2 .. 6,
   78,
   506 .. 1473,
   4863,
   26290 .. 37907,
   107889 .. 107996);
substr $mask, $_, 1, qq{\x00} for @toMask;

my $resAndOrAndNot = andOrAndNot();
my $resAndRegex    = andRegex();
my $resSubstrList  = substrList();

die qq{Inconsistent\n}
   unless $resAndOrAndNot eq $resAndRegex
      and $resAndOrAndNot eq $resSubstrList;

cmpthese (-3,
   {
      andOrAndNot => \&andOrAndNot,
      andRegex    => \&andRegex,
      substrList  => \&substrList,
   });

sub andOrAndNot
{
    my $masked = ($str & $mask) | ($x & ~ $mask);
    return $masked;
}

sub andRegex
{
    my $masked = $str & $mask;
    $masked =~ s{\x00}{x}g;
    return $masked;
}

sub substrList
{
    my $masked = $str;
    substr $masked, $_, 1, q{x} for @toMask;
    return $masked;
}
[download]

produces

              Rate  substrList    andRegex andOrAndNot
substrList  26.0/s          --         -8%        -91%
andRegex    28.3/s          9%          --        -90%
andOrAndNot  278/s        969%        884%          --
[download]

Cheers,

JohnGG