Mutual Training for Wannafly Union #4

【写在前面】现在还只会3题，还没去看讲题视频，剩下可以补的话会尽快补上来的。

【B】这道题看一下题上的图，就知道题意了，稍微写一下就发现他是一个等差数列求和的公式，我们可以把这些数放到数组里面，然后二分一下就可以了，直接开根可能会爆精度，但是这题没有，我直接开根也通过了。

【C】这道题就是求满足(a[i]-a[j])的绝对值等于差值的最大值和最小值的对数。注意到一些特殊的坑点就可以了，比如序列里面所有数相同的情况。参见代码如下：

//
//Created by just_sort 2016/12/23
//Copyright (c) 2016 just_sort.All Rights Reserved
//

//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/hash_policy.hpp>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <sstream> //isstringstream
#include <iostream>
#include <algorithm>
using namespace std;
//using namespace __gnu_pbds;
typedef long long LL;
//typedef pair<int, LL> pp;
#define REP1(i, a, b) for(int i = a; i < b; i++)
#define REP2(i, a, b) for(int i = a; i <= b; i++)
#define MP(x,y) make_pair(x,y)
const int maxn = 1100;
const int maxm = 1<<12;
const int inf = 0x3f3f3f3f;
//typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>order_set;
//head

LL a[100010];
map <LL, int> mp1, mp2;
int main()
{
    int n;
    while(scanf("%d", &n) != EOF)
    {
        mp1.clear();
        mp2.clear();
        for(int i = 1; i <= n; i++) scanf("%lld", &a[i]), mp1[a[i]]++, mp2[a[i]]++;
        sort(a+1, a+n+1);
        LL maxx, minn = 1e19;
        for(int i = 1; i < n; i++){
            //maxx = max(maxx, a[i+1] - a[i]);
            minn = min(minn, a[i+1] - a[i]);
        }
        LL ans1 = 0, ans2 = 0;
        maxx = a[n] - a[1];
        for(int i = 1; i <= n; i++){
            if(mp1[a[i]+minn] != 0){
                if(a[i] + minn == a[i]) ans1 += (mp1[a[i]+minn]-1);
                else ans1 += mp1[a[i]+minn];
                if(a[i] + minn == a[i]) mp1[a[i]+minn]--;
            }
            if(mp2[a[i]+maxx] != 0){
                if(a[i] + maxx == a[i]) ans2 += (mp2[a[i]+maxx]-1);
                else ans2 += mp2[a[i]+maxx];
                if(a[i] + maxx == a[i])mp2[a[i]+maxx]--;
            }
        }
        printf("%lld %lld\n", ans1, ans2);
    }
    return 0;
}

【D】求连子段的异或和<=k的个数，做法是先预处理一个异或前缀，这个东西在线处理也可以，然后对于a[i]把之前的数插到字典树里面，那么答案怎么寻找呢？这个地方我们需要分几种情况去讨论一下，满足往下走得到的值是小于等于k的就可以了。

//
//Created by just_sort 2016/12/25
//Copyright (c) 2016 just_sort.All Rights Reserved
//

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <sstream> //isstringstream
#include <iostream>
#include <algorithm>
using namespace std;
using namespace __gnu_pbds;
typedef long long LL;
typedef pair<int, LL> pp;
#define REP1(i, a, b) for(int i = a; i < b; i++)
#define REP2(i, a, b) for(int i = a; i <= b; i++)
#define MP(x,y) make_pair(x,y)
const int maxn = 1100;
const int maxm = 1<<12;
const int maxs = 1e6+7;
const int inf = 0x3f3f3f3f;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>order_set;
//head

typedef long long LL;
int buf, tmp;
LL sum;
struct node{
    int ch[maxs][2], num[maxs], sz;
    void init(){
        sz = 1;
        memset(ch[0], 0, sizeof(ch[0]));
        //memset(num , 0, sizeof(num));
    }
    void insert(int x)
    {
        int u = 0;
        bool now;
        for(int i = 20; ~i; i--){
            now = (1 << i) & x;
            if(!ch[u][now]){
                num[sz] = 0;
                memset(ch[sz], 0, sizeof(ch[sz]));
                ch[u][now] = sz++;
            }
            u = ch[u][now];
            num[u]++;
        }
    }
    LL query(int x, int k){
        int u = 0;
        LL ans = 0;
        bool now1, now2;
        for(int i = 20; ~i; i--){
            now1 = (1 << i) & x;
            now2 = (1 << i) & k;
            if(now2){
                if(now1){
                    ans += num[ch[u][1]];
                    if(!ch[u][0]) return ans;
                    u = ch[u][0];
                }
                else{
                    ans += num[ch[u][0]];
                    if(!ch[u][1]) return ans;
                    u = ch[u][1];
                }
            }
            else{
                if(now1){
                    if(!ch[u][1]) return ans;
                    u = ch[u][1];
                }
                else{
                    if(!ch[u][0]) return ans;
                    u = ch[u][0];
                }
            }
        }
        return ans;
    }
}Trie;

int main()
{
    int T, n, k;
    scanf("%d", &T);
    while(T--)
    {
        Trie.init();
        buf = sum = 0;
        scanf("%d%d", &n,&k);
        Trie.insert(0);
        for(int i = 1; i <= n; i++){
            scanf("%d", &tmp);
            buf ^= tmp;
            sum += Trie.query(buf, k);
            //cout<<sum<<endl;
            Trie.insert(buf);
        }
        printf("%lld\n", sum);
    }
    return 0;
}