$O(n)$ 贪心，枚举

在 ? 的位置填入 0 或 1要求最多的逆序对，对于填入的数字来说 1 都在前面，0 都在后面，这样逆序对的数量会最多。

接下来考虑填入 01 的具体数量，可以先全部填入 1 求出结果，从后向前遍历字符串，把填入的 1 改成0 ， 计算每个 '?' 更改后的贡献，从而算出答案的最大值。

具体贡献更改的计算

假设将位置 $i$ 的 1 改为 0 后，$t$ 的变化为：

$t = t - i后面 0 的数量 + i前面1的数量 - i后面'?'的数量$，

其中 $t$ 为后面的 ? 全部填 0 ，前面（包括自己）的 ? 全部填入1的位置

后面 0 的数量和前面 1 的数量可以用前后缀预处理。

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
typedef pair<int, int> PII;

#define x first
#define y second

const int N = 2e5 + 10, mod = 998244353;

void solve()
{
    int n;
    cin >> n;
    string s;
    cin >> s;
    vector<bool> st(n + 1, 0);
    s = " " + s;
    for(int i = 1; i <= n; i ++) 
    {
        if(s[i] == '?') 
        {
            s[i] = '1';
            st[i] = 1;
        }
    }
    
    vector<int> suf(n + 2, 0), pre(n + 2, 0); //后缀0的数量，前缀1的数量
    for(int i = 1; i <= n; i ++)
        pre[i] = pre[i - 1] + (s[i] == '1');
    for(int i = n; i; i --)
        suf[i] = suf[i + 1] + (s[i] == '0');
    
    LL ans = 0;
    for(int i = 1; i <= n; i ++)
    {
        if(s[i] == '1')
            ans += suf[i];
    }
    LL t = ans, cnt = 0;
    for(int i = n; i; i --)
    {
        if(st[i])
        {
            s[i] = '0';
            t = t - suf[i + 1] - cnt + pre[i - 1];
            cnt ++;
        }
        
        ans = max(ans, t);
        // cout << t << ' ';
    }
    cout << ans << endl;
}

int main(){
    int t;
    cin >> t;
    while(t --)
        solve();
}