写了大量暴力分，导致的代码长度 6.1k（洁身自好只有 1kb，最长那位老哥一坨洁身自好），稍微写写吧。

首先你发现所有合法对都需要选。然后一个显然的 Trick 就是按照最大值分治（笛卡尔树？不知道我早就忘了这个东西）。那么你就考虑从小到大加入元素 \(x\)，然后每次合并区间的时候所产生的贡献就是左右部分元素两两配对，总合法对数 \(\times x\)。对这个东西暴力维护是显然的，但是你会发现只能做 \(V=32\) 的情况，这样可以拿到 76 分。转化一下值域可以拿到 84 分，不讲。

然后怎么优化呢？考虑使用高低位分块的技巧。注意到所有的合并操作只有 \(n\log n\) 次，那么我们直接加入标记，从左到右扫，计算贡献即可。

代码非常长。

::::success[Code]

#define FileIO
#include
using namespace std;
#define ll long long
#define fi first
#define se second
#define il inline
bool stMem; double stT=clock();
const int N=3e5+10, TN=1e3+10, M=21, V=16384, SV=33;
const int LB=7, HB=14-LB, LS=(1<>=1,a=(a*a)%P) if(b&1) res=(res*a)%P;return res;
}
// ---------------------------------------------------- //
int n,a[N],now_test_id,mxV;
bool sbA, sbB, sbC, vis[M];
int st[N][M], lg[N];
vector e[V], sub[V], fat[V], dd, user[N];
int fa[N], sz[N], tmp[V], mpc[V], lt[N];
int sl[N], sr[N];
ll smp[N][SV];
struct querys{ int l,r; ll v; };
vector qrys[N];
ll subcnt[HS][LS], supcnt[HS][LS], cnt[V];
int find(int x){ return x==fa[x]?x:fa[x]=find(fa[x]); }
ll ans;
il int query_max(int l,int r){if(l>r) return 0;int k=lg[r-l+1];return max(st[l][k],st[r-(1< "<>x)&1) son^=tmp[x];sub[i].push_back(son);++tmp_tot;}}cerr<<"TEST: sum of all subset: "<>x)&1) nfa|=tmp[x];fat[i].push_back(nfa);++tmp_tot;}}cerr<<"TEST: sum of all fatset: "<>LB, xl=x&(LS-1);for(int s=xl;s>LB, xl=x&(LS-1); ll res=-cnt[x]; // offset (x \in subset[x], supset[x])for(int s=xh;s>n;lg[0]=-1;for(int i=1;i<=n;++i)lg[i]=lg[i>>1]+1;for(int i=1;i<=n;++i) cin>>a[i], mxV=max(mxV,a[i]);{sbA=1; for(int i=1;i=0){ ans+=smp[ul][w]*1ll*now_v; }for(auto w:fat[a[v]])if(w<33){ ans+=smp[ul][w]*1ll*now_v; }ans-=smp[ul][a[v]]*1ll*now_v; // offsetuser[ul].push_back(v);}user[ur].clear();for(int i=0;i<=32;++i) smp[ul][i]+=smp[ur][i];smp[ul][now_v]++;}lt[p]=1;}cerr<>T;while(T--) solve();cerr<<"\n";cerr<<"[Info] End Of Running. \n";cerr<<"       Time Used   : "<<(clock()-stT)/CLOCKS_PER_SEC*1000.00<<" ms\n";cerr<<"       Memory Used : "<<(&stMem-&edMem)/1048576.00<<" Mib\n";return 0;
}

::::

https://www.luogu.com.cn/article/yb0g0aix