题意:有两个长度为\(n\)的序列\(a\)和\(b\),定义\(C_k=max(A_i,B_j)\ (i\ and\ j\ge k)\),求\(\sum^{n-1}_{i=0}C_i\).

题解:暴力思路:求出所有的\(C_k\),然后从\(n-1\)倒着维护最大值贡献给答案即可.

根据到这维护最大值这个思想,我们考虑\(i\)&\(j\)=\(i\)的情况,根据&运算的性质,两个数&之后只会不变或者变小,我们倒着枚举\(i\),根据上述性质,我们找\([i,n-1]\)中满足条件的\(j\),这里我们只要看单独的某一个\(1\)即可,可以用dp转移过来,那么我们每次可以得到\([i,n-1]\)中的满足条件的\(j\),更新最大值最小值.最后在求答案贡献的时候,\(A[i]\)表示的是\([i,n-1]\)中的\(i\)&\(j\)=\(i\)的某个位置\(x_1\)的值,同理,\(B[i]\)表示的是某个位置\(x_2\)的值,因为我们在更新的时候保证\(i\)&\(j\)=\(i\),且根据性质\(j\)一定不小于\(i\),那么\(x_1\)&\(x_2\ge i\),然后就根据我们前面的暴力思路求贡献给答案就好了.

代码:

#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
#define ll long long
#define db double
#define fi first
#define se second
#define pb push_back
#define me memset
#define rep(a,b,c) for(int a=b;a<=c;++a)
#define per(a,b,c) for(int a=b;a>=c;--a)
const int N = 1e6 + 10;
const int mod = 998244353;
const int INF = 0x3f3f3f3f;
using namespace std;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a/gcd(a,b)*b;}

ll a[N],A[N],b[N],B[N];

int main() {
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    #ifdef lr001
        freopen("/Users/somnus/Desktop/data/in.txt","r",stdin);
    #endif
    #ifdef lr002
        freopen("/Users/somnus/Desktop/data/out.txt","w",stdout);
    #endif
    int _;
    cin>>_;
    while(_--){
        int n;
        cin>>n;
        rep(i,0,n-1) cin>>a[i],A[i]=a[i];
        rep(i,0,n-1) cin>>b[i],B[i]=b[i];
        int base=0;
        while((1<<base)<=n) base++;  //要包括n
        /* brute_force
        rep(i,0,n-1){
            rep(j,0,n-1){
                res[i&j]=max(res[i&j],a[i]*b[j]);
            }
        }
        int ans=0;
        per(i,n-1,0){
            res[i]=max(res[i],res[i+1]);
            ans+=res[i];
        }
        cout<<ans<<'\n';
        */
        rep(i,n,(1<<base)-1){
            A[i]=B[i]=-INF;
            a[i]=b[i]=INF;
        }
        per(i,n,0){
            rep(j,0,base-1){
                int cur=1<<j;
                if((i&cur)==0){
                    A[i]=max(A[i],A[i^cur]);
                    B[i]=max(B[i],B[i^cur]);
                    a[i]=min(a[i],a[i^cur]);
                    b[i]=min(b[i],b[i^cur]);
                }
            }
        }
        ll mx=-1e18;
        ll ans=0;
        per(i,n-1,0){
            ll res=-1e18;
            res=max(res,A[i]*B[i]);
            res=max(res,A[i]*b[i]);
            res=max(res,a[i]*B[i]);
            res=max(res,a[i]*b[i]);
            res=max(res,mx);
            mx=res;
            ans=(ans+res+mod)%mod;
        }
        cout<<ans<<'\n';
    }



    return 0;
}