给两个字符串$s$,$t$。选择某个区间$i\in[l,r],r+l-1\geq m,swap(s[a_i],s[b_i])$

$|s|=k\leq 20。l,r\leq n=10^6$

求操作完匹配度最高的匹配度以及操作区间。

考虑暴力枚举区间固定一个$l$，位运算求匹配度，$O(n^2k)$
如果选择$[1,x]$，我们可以轻松模拟出来。

误区

一开始我想$[l+1,r]$即$s$操作$r$次，$t$操作$l$次，但是这是错的。

根据固定一个端点的思路，考虑先把每个位置，映射成$2^i$。位置之间的对比就成了,$s的swap$，相当于$t每个映射需要比较i$的变化

$dp[mask][1]$表示$t$的某个对应$s$的$p[i]$的状态的区间下标的最大值
$dp[mask][0]$表示$s$的某个对应$t$的$p[i]$的状态的区间下标的最小值

打个比方$t$在$R$的时候$54321$，表示$t_1匹配5的位置$，但是$[L+1,R]区间的问题$，其实在$L$的时候$32145$,表示$s_1匹配3的位置,$,最终因为我俩交换=没交换，就可以把他们都映射到一个统一集合上。这样对比就可以找出共同的$1$可以有几个。

即$t[i]的位置$在$R$的时候，其实表示$s[i]\times 2^{p[r][i]}$

然后就是$SOSdp$套路下，找超集的最大和最小下标，枚举有多少个$1$匹配到了。

代码

```c++

include

using namespace std;
typedef long long ll;

define pii pair

define mk make_pair

const int N = 2e6 + 10;
const int mod = 1e9 + 7;

int read()
{
int x = 0, f = 1;
char c = getchar();
while (c < ‘0’ || c > ‘9’)
{
if (c == ‘-‘)
f = -1;
c = getchar();
}
while (c >= ‘0’ && c <= ‘9’)
x = (x << 1) + (x << 3) + c - ‘0’, c = getchar();
return x f;
}
int p[N];
int calc(char s)
{
int len = strlen(s + 1);
int res = 0;
for (int i = 1; i <= len; i++)
if (s[i] == ‘1’)
res |= 1 << (p[i] - 1);
return res;
}
int dp[N][2];
char s[N], t[N];
int main()
{
int n = read(), m = read(), k = read();
scanf(“%s”, t + 1);// t是主要变换的
scanf(“%s”, s + 1);
int st = 1 << k;
for (int i = 0; i < st; i++)
{
dp[i][1] = -1e9;
dp[i][0] = 1e9;
}
int cnt1 = 0, cnt2 = 0;
for (int i = 0; i < k; i++)
p[i] = i;
for (int i = 1; i <= k; i++)
cnt1 += (s[i] == ‘1’), cnt2 += (t[i] == ‘1’);
dp[calc(t)][0] = 0;
dp[calc(s)][1] = 0;
for (int i = 1; i <= n; i++)
{
int x = read(), y = read();
swap(p[x - 1], p[y - 1]);
dp[calc(s)][1] = max(dp[calc(s)][1], i);
dp[calc(t)][0] = min(dp[calc(t)][0], i);
}

int ans = 0, la = 1, ra = n;
for (int i = 0; i < k; i++)
{
    for (int j = 0; j < st; j++)
        if (j & (1 << i))
        {
            dp[j ^ (1 << i)][1] = max(dp[j ^ (1 << i)][1], dp[j][1]);
            dp[j ^ (1 << i)][0] = min(dp[j ^ (1 << i)][0], dp[j][0]);
        }
}
for (int j = st - 1; j >= 0; j--)
{
    int cnt = __builtin_popcount(j);
    if (cnt1 >= cnt && cnt2 >= cnt)
    {
        int res = k - (cnt1 + cnt2 - 2 * cnt);

        if (dp[j][1] - dp[j][0] >= m)
        {
            if (res > ans)
            {
                ans = res;
                la = dp[j][0] + 1;
                ra = dp[j][1];
            }
        }
    }
}
cout << ans << endl;
cout << la << " " << ra << endl;

}