# include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
int n, dp[N][2], pref[N][2];
string a, b;
inline int calc (int l, int r, int type){
if (type == 0)
return pref[r][0] - pref[l - 1][0] + (b[l - 1] == b[l] && b[l] == '0');
return pref[r][1] - pref[l - 1][1] + (b[l - 1] == b[l] && b[l] == '1');
}
struct st{
int must, val;
};
st t[3][3][N * 4], t11[N * 4], t10[N * 4];
void push (int i, int j, int v, int tl, int tr)
{
t[i][j][v].val += t[i][j][v].must;
if (tl != tr){
t[i][j][v + v].must += t[i][j][v].must;
t[i][j][v + v + 1].must += t[i][j][v].must;
}
t[i][j][v].must = 0;
}
void update (int i, int j, int l, int r, int val, int v = 1, int tl = 0, int tr = n)
{
push(i, j, v, tl, tr);
if (l > tr || tl > r) return;
if (l <= tl && tr <= r){
t[i][j][v].must += val;
push(i, j, v, tl, tr);
return;
}
int tm = (tl + tr) >> 1;
update(i, j, l, r, val, v + v, tl, tm);
update(i, j, l, r, val, v + v + 1, tm + 1, tr);
t[i][j][v].val = min( t[i][j][v + v].val, t[i][j][v + v + 1].val );
}
int get (int i, int j, int l, int r, int v = 1, int tl = 0, int tr = n)
{
push(i, j, v, tl, tr);
if (l > tr || tl > r)
return 1e9 + 7;
if (l <= tl && tr <= r)
return t[i][j][v].val;
int tm = (tl + tr) >> 1;
return min( get(i, j, l, r, v + v, tl, tm), get(i, j, l, r, v + v + 1, tm + 1, tr) );
}
main(){
memset( dp, 0x3f3f3f3f, sizeof(dp) );
cin >> n >> a >> b;
a = ' ' + a;
b = ' ' + b;
for (int i = 1; i <= n; i++){
st.insert(a[i]);
if (b[i] != b[i - 1])
pref[i][ b[i] - 48 ] = 1;
pref[i][0] += pref[i - 1][0];
pref[i][1] += pref[i - 1][1];
}
dp[0][0] = 0;
update( 0, 1, 0, 0, dp[0][1] );
for (int i = 1; i <= n; i++){
if (b[i] != b[i - 1]){
update(0, b[i] - 48, 0, i - 1, +1);
update(1, b[i] - 48, 0, i - 1, +1);
}
update(0, b[i] - 48, i, i, +1);
update(1, b[i] - 48, i, i, +1);
if (a[i] == b[i])
dp[i][0] = min( dp[i - 1][1], dp[i - 1][0] );
if (a[i] != b[i])
dp[i][1] = min( dp[i - 1][1], dp[i - 1][0] + 1);
dp[i][0] = min( dp[i][0], get(0, 1, 0, i - 1) + 1 );
dp[i][0] = min( dp[i][0], get(0, 0, 0, i - 1) + 1 );
dp[i][1] = min( dp[i][1], get(1, 0, 0, i - 1) + 1 );
dp[i][1] = min( dp[i][1], get(1, 1, 0, i - 1) + 1 );
dp[i][1] = min( dp[i][1], get(0, 0, 0, i - 1) - (b[i] == '0') + 2 );
dp[i][1] = min( dp[i][1], get(0, 1, 0, i - 1) - (b[i] == '1') + 2 );
//dp[i][0] = min( dp[i][0], dp[j - 1][1] + calc( j, i, 1 ) - (b[j] == '1') + 1 );
//dp[i][0] = min( dp[i][0], dp[j - 1][1] + calc( j, i, 0 ) - (b[j] == '0') + 1 );
//dp[i][1] = min( dp[i][1], dp[j - 1][1] + max(0, calc( j, i, 0 ) - (b[j] == '0') - (b[i] == '0') ) + 2 );
//dp[i][1] = min( dp[i][1], dp[j - 1][1] + max(0, calc( j, i, 1 ) - (b[j] == '1') - (b[i] == '1') ) + 2 );
update( 0, 0, i, i, dp[i][0] );
update( 0, 1, i, i, dp[i][0] );
update( 1, 0, i, i, dp[i][1] );
update( 1, 1, i, i, dp[i][1] );
}
cout << min(dp[n][0], dp[n][1]) << endl;
}
/**
13
0101100101001
1011111000000
13
0001101001101
0101100011011
8
11011100
01101001
**/
Compilation message
lamp.cpp:68:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main(){
^
lamp.cpp: In function 'int main()':
lamp.cpp:79:6: error: expected unqualified-id before '.' token
st.insert(a[i]);
^
