#include<bits/stdc++.h>
#define Type int
#define qr(x) x=read()
using namespace std;
inline Type read(){
char c=getchar(); Type x=0, f=1;
while(!isdigit(c)) (c=='-'?f=1:f=-1), c=getchar();
while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48), c=getchar();
return x*f;
}
const int N = 1e6 + 10;
int n, m, a[N], nid;
struct Trie{
int f[N][2], rt, t[32][2];
inline void insert(int th){
int x = a[th], u = 1;
for(int i=0; i<30; i++){
int now = t[u][(x & (1 << i))];
if(!now) now = ++rt;
f[now][1]++; u = now;
}
}
inline void update(int j){
int x = a[j], u = 1;
for(int i=0; i<30; i++){
int now = t[u][(x & (1 << i))];
f[now][0]++;
f[now][1]--;
u = now;
}
}
inline int query(int x){
int u = 1, res = 0;
for(int i=0; i<30; i++){
int g = (x & (1 << i));
int lson = t[u][0], rson = t[u][1], L, R;
if(g == 1) L = f[lson][g] - 1, R = f[rson][g^1];
else L = f[lson][g], R = f[rson][g^1] - 1;
if(!lson or !rson) L = 0;
res += L * R; u = t[u][g];
}
return res;
}
}tri;
int main(){
// freopen("in.in", "r", stdin), freopen("out.out", "w", stdout);
qr(n);
for(int i=1; i<=n; i++) qr(a[i]);
for(int i=1; i<=n; i++)
tri.insert(i);
int ans = 0;
for(int i=1; i<=n; i++){
ans += tri.query(a[i]);
tri.update(i);
}
cout<<ans<<"\n";
return 0;
}
标签:read,while,isdigit,Cun,Type,getchar
From: https://www.cnblogs.com/YuenYouth/p/18503719