HDU 6059 17多校3 Kanade's trio（字典树）

Problem Description

Give you an array A[1..n]，you need to calculate how many tuples (i,j,k) satisfy that (i<j<k) and ((A[i] xor A[j])<(A[j] xor A[k]))

There are T test cases.

1≤T≤20

1≤∑n≤5∗105

0≤A[i]<230

Input

There is only one integer T on first line.

For each test case , the first line consists of one integer n ,and the second line consists of n integers which means the array A[1..n]

Output

For each test case , output an integer , which means the answer.

Sample Input

1 2 3 4 5

Sample Output

启发博客：http://blog.csdn.net/dormousenone/article/details/76570172

摘：

利用字典树维护前 k-1 个数。当前处理第 k 个数。

显然对于 k 与 i 的最高不相同位 kp 与 ip ：

当 ip=0 , kp=1 时，该最高不相同位之前的 ihigher=khigher 。则 jhigher 可以为任意数，均不对 i, k 更高位（指最高不相同位之前的高位，后同）的比较产生影响。而此时 jp 位必须为 0 才可保证不等式 (Ai⊕Aj)<(Aj⊕Ak) 成立。

当 ip=1,kp=0 时，jp 位必须为 1 ，更高位任意。

故利用数组 cnt[31][2] 统计每一位为 0 ，为 1 的有多少个（在前 K-1 个数中）。在字典树插入第 k 个数时，同时统计最高不相同位，即对于每次插入的 p 位为 num[p] (取值 0 或 1)，在同父节点对应的 1-num[p] 为根子树的所有节点均可作为 i 来寻找 j 以获取对答案的贡献。其中又仅要求 jp 与 ip (ip 值即 1-num[p]) 相同，故 jp 有 cnt[p][ 1-num[p] ] 种取值方案。

但是，同时需要注意 i 与 j 有在 A 数组的先后关系 (i<j) 需要保证。故在字典树中额外维护一个 Ext 点，记录将每次新加入的点与多少原有点可构成 i, j 关系。在后续计算贡献时去掉。

其余详见代码注释。

 #include <iostream>

 #include<cstdio>

 #include<algorithm>

 #include<queue>

 #include<map>

 #include<vector>

 #include<cmath>

 #include<cstring>

 using namespace std;

 long long ans1,ans2;

 int num[];//每一个数字的二进制转化

 int cnt[][];//cnt[i][j]记录全部插入数字第i位为0、1分别的数字

 struct trie

 {

     trie* next[];

     int cnt,ext;

     trie()

     {

         next[]=NULL;

         next[]=NULL;

         cnt=;//拥有当前前缀的数字个数

         ext=;//

     }

 };

 void calc(trie* tmp,long long c)

 {

     ans1+=tmp->cnt*(tmp->cnt-)/;

     ans2+=(c-tmp->cnt)*tmp->cnt-tmp->ext;

 }

 void insert(trie* r)

 {

     int i;

     for(i=;i<=;i++)

     {

         if(r->next[num[i]]==NULL)

             r->next[num[i]]= new trie;

         if(r->next[-num[i]]!=NULL)

             calc(r->next[-num[i]],cnt[i][-num[i]]);

         r=r->next[num[i]];

         r->cnt++;

         r->ext+=cnt[i][num[i]]-r->cnt;

         //每个点存下同位同数不同父亲节点的数字个数且序号比本身小的

     }

     return ;

 }

 int main()

 {

     int T,n,tmp;

     scanf("%d",&T);

     while(T--)

     {

         scanf("%d",&n);

         trie root;

         ans1=;//i,j选自同父亲节点

         ans2=;//i选自同父亲节点，j选择同位不同数不同父亲节点

         memset(cnt,,sizeof(cnt));

         while(n--)

         {

             scanf("%d",&tmp);

             for(int i=;i>=;i--)//这样可以保证不同大小的数字前缀都为0

             {

                 num[i]=tmp%;

                 cnt[i][num[i]]++;

                 tmp/=;

             }

             insert(&root);

         }

         printf("%lld\n",ans1+ans2);

     }

     return ;

 }

巴特西

HDU 6059 17多校3 Kanade's trio（字典树）

最新文章

热门文章