求数组中i<j<k 并且ai^aj<aj^ak的三元组组数
枚举插入ak，让ak中每一位作为最高位，查找字典树内最高位不同的数字数量
注意把ak的每个前缀做一个bad标记
存储让这个前缀作为i可以与字典树内形成i,j对的个数，这些不满足i<j
ai : 1 1 0 1
aj : ? 0 0 0
ak : 1 0 0 1
结合这个图会直观点。。
#include<bits/stdc++.h>
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<stdio.h>
#include<algorithm>
#include<queue>
#include<string.h>
#include<iostream>
#include<math.h>
#include<set>
#include<map>
#include<vector>
#include<iomanip>
using namespace std;
#define ll long long
#define pb push_back
#define FOR(a) for(int i=1;i<=a;i++)
const int inf=0x3f3f3f3f;
const int maxn=5e5+9; struct NODE{int cnt;int nxt[2];int bad;
}trie[maxn*30];int sz;
int dig[30];
int cnt[30][2];
ll ans;
int arr[maxn];void cal(int p,int cnt){ans+=1ll*trie[p].cnt*(trie[p].cnt-1)>>1; //ai,aj都在前缀内选ans+=1ll*trie[p].cnt*(cnt-trie[p].cnt)-trie[p].bad; //ai在前缀，aj不在
}void insert(){int now=0;for(int i=0;i<30;i++){if(!trie[now].nxt[dig[i]]){trie[now].nxt[dig[i]]=++sz;}if(trie[now].nxt[1-dig[i]]){cal(trie[now].nxt[1-dig[i]],cnt[i][1-dig[i]]);}now=trie[now].nxt[dig[i]];trie[now].cnt++;trie[now].bad+=cnt[i][dig[i]]-trie[now].cnt;}
}int main(){int T;scanf("%d",&T);while(T--){memset(trie,0,sizeof trie);memset(cnt,0,sizeof cnt);int n;scanf("%d",&n);sz=0,ans=0;FOR(n){scanf("%d",&arr[i]);for(int j=29;j>=0;j--){dig[j]=arr[i]%2;cnt[j][arr[i]%2]++;arr[i]/=2;}insert();}printf("%lld\n",ans);}
}接着补题之前做做异或题吧。。
