空之碎物

· · 题解

超级无敌结论题。与图论无关的两只 \log 做法。

按位考虑。发现最终的数一个二进制位上一定能被写成 (((x_1\ominus x_2)\ominus x_3)\ominus...)\ominus x_k 的形式，而这个东西能取到 1 当且仅当 x_1=1 且 \forall i\in[2,k] x_i=0（注意这里的 x_k 并不一定是原序列中的某个数的该二进制位，也有可能是若干个数该二进制位下操作的结果）。

Observation 1: x\ominus y\leq x。

证明：显然。

Observation 2: 若至少有 2 个数，则取 k=2 一定不劣。

证明：考虑 x_1\ominus (((x_2\ominus x_3)\ominus ... )\ominus x_k)。若原来的那个形式能取到 1，则现在这个形式依旧能取到 1。

Observation 3: 当 r-l+1>26 时，f(l,r)=\max_{i=l}^{r} a_i。

证明：取 x_1=\max_{i=l}^{r} a_i。则我们需要做的事情就是尽可能让 x_1 取值为 1 的那些二进制位保持为 1。

构造是容易的，不妨让剩下的数按照 (((x_2\ominus x_3)\ominus x_4)\ominus...)\ominus x_k 的形式操作，对于一个二进制位，如果除了 x_1 以外剩下的数里面有 \geq 2 个为 1 的，那么无论如何操作最终这一位一定是 0。所以当剩余数个数 >25 时一定存在一种操作方案是的最终与 x_1 操作的数为 0。而由于 x\ominus y\leq x，所以我们在 r-l+1>26 时答案一定为区间最大值。

Observation 4: 当 r-l+1\neq 3 时，f(l,r) 的值一定由 Observation 3 中的构造方式得来（即除去最大值以外的数按某个顺序依次操作，最后最大值操作这个结果）。

上述已经证明 k=2，所以问题转化为 x_2 在 x_1 的那些为 1 的位尽量为 0。

证明：

显然 x_1 一定是一个数，不然把其他数丢进 x_2 里不劣，同时 x_2 一定是按顺序依次操作，因为这样只会让 x_2 更小。

如果存在 x_1'<x_1 且 x_1'\ominus x_2'>x_1\ominus x_2，那么令 i 为 x_1>x_1' 的最高位，j 为 x_1'\ominus x_2'>x_1\ominus x_2 的最高位。可以得到 i>j，且 x_2(i)=1。对于所有 i'>i 且 x_1(i')=1，显然 x_1'(i')=1。此时其他任何数都无法充当 i' 位唯一一个 1。所以，对于第 i 位，其他但凡有一个数为 0 或至少两个数为 1，那么 x_2(i) 就一定为 0，这与上述矛盾。

唯一的反例出现在 r-l+1=3，即除了 x_1,x_1' 以外的最后一个数该位上为 1 的情况。而且反例很好找，好找到样例 2 就有。

于是剩下的就不难了，从高位到低位贪心，如果这一位 x_1 是 1 且其他数只有一个 1，把唯一拥有那个 1 的数标记不能充当构成 x_2 的第一个数，如果除了它全被标记了那么这一位无论如何取不到 1。对于长度 >26 的区间，直接单调栈算出最大值，对于长度 =3，暴力枚举所有操作方式即可。

时间复杂度：

参考代码：

#include<bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define _rep(i,a,b) for(int i=(a);i>=(b);i--)
#define subset(i,x) for(int i=(x);i;i=((i-1)&x))
#define pi pair<int,int>
#define arr(a) array<int,(a)>
#define F fflush(stdout)
#define RE return puts("-1"),void()
#define cases(_) while((_)--) solve();
using namespace std;
const int mod=998244353;
inline void ckmin(int& x,int y){x=min(x,y);}
inline void ckmax(int& x,int y){x=max(x,y);}
inline void add(int& x,int y){x=(x%mod+y%mod+mod)%mod;}
inline void mul(int& x,int y){x=(x%mod)*(y%mod)%mod;}
const int N=200005,BIT=25;
int _=1,n,a[N],t[BIT+5],flg[BIT+5],vis[N],ans,res,tmp,nxt[N],pre[N];
inline void add(int x){
    if(x==0) return;
    rep(o,0,BIT) if((a[x]>>o)&1) t[o]++,flg[o]=x;
}
inline int f(int x,int y){
    int res=0;
    rep(o,0,BIT) if((x>>o)&1 && !((y>>o)&1)) res+=(1<<o);
    return res;
}
inline int calc(int x,int y,int z){
    int r1=f(f(x,y),z),r2=f(f(x,z),y),r3=f(f(y,z),x),r4=f(f(y,x),z),r5=f(f(z,y),x),r6=f(f(z,x),y);
    int c1=f(z,f(x,y)),c2=f(y,f(x,z)),c3=f(x,f(y,z)),c4=f(z,f(y,x)),c5=f(x,f(z,y)),c6=f(y,f(z,x));
    int a1=max(max(max(r1,r2),r3),max(max(r4,r5),r6));
    int a2=max(max(max(c1,c2),c3),max(max(c4,c5),c6));
    return max(a1,a2);
}
void solve(){
    scanf("%lld",&n),a[0]=-1;
    rep(i,1,n) scanf("%lld",&a[i]);
    rep(l,1,n){
        int mx=0;
        rep(o,0,BIT) t[o]=0,flg[o]=0;
        rep(r,l,min(l+30,n)){
            if(a[r]<=a[mx]) add(r);
            else add(mx),mx=r;
            rep(o,l,r) vis[o]=0;
            int sum=r-l,res1=0;
            _rep(o,BIT,0) if(t[o]==1 && (a[mx]>>o)&1){
                sum-=(vis[flg[o]]==0);
                if(sum==0) sum++,res1+=(1ll<<o);
                else vis[flg[o]]=1;
            }
            if(r-l!=2) add(ans,a[mx]-res1);
            else add(ans,calc(a[l],a[l+1],a[l+2]));
            add(tmp,a[mx]);
        }
    }
    fill(nxt+1,nxt+n+1,n+1);
    stack<int> st;
    rep(i,1,n){
        while(!st.empty() && a[i]>a[st.top()]) nxt[st.top()]=i,st.pop();
        st.push(i);
    }
    while(!st.empty()) st.pop();
    _rep(i,n,1){
        while(!st.empty() && a[i]>=a[st.top()]) pre[st.top()]=i,st.pop();
        st.push(i);
    }
    rep(i,1,n) add(res,(i-pre[i])*(nxt[i]-i)%mod*a[i]);
    add(ans,res-tmp);
    printf("%lld\n",ans);
}
signed main(){
    cases(_);
    return 0;
}