首页 > 代码库 > TOJ4114(活用树状数组)

TOJ4114(活用树状数组)

TOJ指天津大学onlinejudge

题意:给你由N个数组成的数列,算出它们的所有连续和的异或和,比如:数列{1,2},则answer = 1 ^ 2 ^ (1 + 2) = 0。

这道题有几个关键点:

1.这道题要将十进制数换成二进制数,并且对这些二进制数按位计算,比如说上面的式子,我们将它列成竖式:

            01

            10

            11

可以发现,对于第一位来说,一共有2个1,是偶数,异或值为0。answer += 0 * (1<<0)。对于第二位来说,一共有2个1,异或值为0,answer += 0 * (1<<1)。最终answer = 0;

2.Sum(i~j) = S[j] - S[i - 1]。     (S[0] = 0)      所以我们算式可以看成(S[1] - S[0]) ^ (S[2] - S[1]) ^ (S[2] - S[0]) ^ (S[3] - S[0]) ^ (S[3] - S[1]) ^ (S[3] - S[2]) ^ ..........

所以我们可以按块来看这些算式中的项,每一块就S[i]与S[i - 1]......S[0]做差得到的。

综上,我们计算异或和时,我们只需要预处理一下,算出每一个S[i],然后从头到尾扫n次,每一次计算出这些二进制数某一位一共有多少个1(就像上面所举例子一样),看看是偶数还是奇数,

如果是奇数,就answer += 1 * (1<<i)。

现在来说扫描时候的具体操作,假设我们现在已经计算完了S[1]....S[i]这些组成异或和的各项在某一位k的1的个数,在扫到S[i + 1]时,相当于又多了(S[i +1] - S[0]) ^ .......^ (S[i + 1] - S[i])这 i 项来统计,

我就只需要计算出S[i + 1]与前面各项S[ j ] (j属于[ 0 , i ]) 的差在这一位产生了多少个1,对于S[i + 1]与某一个S[ j ]来说,这取决于S[i + 1]和S[ j ]在这一位的值和S[i + 1]与S[ j ]在更低诸位上的大小关系。

在这里,我将S[i + 1]在这一位的值记为A1,更低的诸位统一记为B1,S[ j ]在这一位的值记为A2,更低诸位的统一记为B2。

1.当A1 == 1时,有两种情况可以产出一个1:

情况Ⅰ:A2 == 0,且B1 >= B2。

情况Ⅱ:A2 == 1,且B1 < B2(可以从前面借位来产生1,就像10 - 9 = 1这样)

2.当A1 == 0时,有两种情况可以产出一个1:

情况Ⅰ:A2 == 0,且B1< B2

情况Ⅱ:A2 == 1,且B1 >= B2。

由此可以看出,对于S[i + 1]与前面诸前缀和之差在某一位能产生多少个1,我只要知道S[ j ]比这一位低的诸位与S[i + 1]比这一位低的诸位之大小关系即可。

这个可以用树状数组来保存,树状数组的下标表示的是值域,BIT[ Bi ]中存的比这一位低的诸位B小于等于Bi的S[ k ]的个数,由于我们扫这一遍S[ i ]的目的就是为了计算特定的一位,

所以我们有多少位就扫多少次,扫完一次就清空一次树状数组。由于还跟S[ j ]在这一位的值有关,所以我们开两个树状数组,一个记录在这一位为1的S[i],一个则记录在这一位为0的S[j]。

对于每一个S[i]我们边算边存,如果S[i]在这一位为1,则存在BIT_1中;如果为0,则存在BIT_0中。

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
#define maxn 100005
#define maxn2 1000005
using namespace std;
int BIT_0[maxn2],BIT_1[maxn2];
int S[maxn];
int lowbit(int k)
{
    return (k & (-k));
}
void add(int v,int pos,int mmax,int a[])
{
    while(pos <= mmax){
        a[pos] += v;
        pos += lowbit(pos);
    }
}
int sum(int pos,int a[])
{
    int ret = 0;
    while(pos > 0){
        ret += a[pos];
        pos -= lowbit(pos);
    }
    return ret;
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--){
        memset(S,0,sizeof(S));
        int n;
        scanf("%d",&n);
        for(int i = 1;i <= n;++i){
            scanf("%d",&S[i]);
            S[i] += S[i - 1];
        }
        int temp = S[n];
        int len = 0;
        while(temp > 0){
            temp = temp>>1;
            ++len;
        }
        int answer = 0;
        for(int i = 0;i < len;++i){
            int cnt = 0;
            int cnt_0 = 0,cnt_1 = 0,mmax = (1<<i);
            for(int j = 0;j <= n;++j){
                int tail = S[j] % (1<<i);
                ++tail;
                int t_cnt = 0;
                if(S[j] & (1<<i)){
                    t_cnt += sum(tail,BIT_0);
                    t_cnt += (cnt_1 - sum(tail,BIT_1));
                    add(1,tail,mmax,BIT_1);
                    ++cnt_1;
                }
                else{
                    t_cnt += sum(tail,BIT_1);
                    t_cnt += (cnt_0 - sum(tail,BIT_0));
                    add(1,tail,mmax,BIT_0);
                    ++cnt_0;
                }
                cnt += t_cnt;
            }
            if(cnt & 1) answer += (1<<i);
            memset(BIT_0,0,sizeof(BIT_0));
            memset(BIT_1,0,sizeof(BIT_1));
        }
        printf("%d\n",answer);
    }
    return 0;
}

这里有一个小技巧,由于lowbit( )不好处理0,所以我把每一个tail都加1,(tail的取值最小就是0),这样sum(x)其实算的是tail在[0,x-1]之间的S[j]

 

 

本题启发:树状数组的下标用来表示值域

TOJ4114(活用树状数组)