[TJOI2017]异或和

题目描述

在加里敦中学的小明最近爱上了数学竞赛，很多数学竞赛的题都是与序列的连续和相关的。所以对于一个序列，求出它们所有的连续和来说，小明觉得十分的简单。但今天小明遇到了一个序列和的难题，这个题目不仅要求你快速的求出所有的连续和，还要快速的求出这些连续和的异或值。小明很快的就求出了所有的连续和，但是小明要考考你，在不告诉连续和的情况下，让你快速求是序列所有连续和的异或值。

输入输出格式

输入格式：

第一行输入一个n,表示这序列的数序列第二行输入n个数字a1,a2...an代表这个序列

0<=a1,a2,...an，0<=a1+a2...+an<=10^6

输出格式：

输出这个序列所有的连续和的异或值

输入输出样例

输入样例#1：

3

1 2 3

输出样例#1：

说明

【样例解释】

序列1 2 3有6个连续和，它们分别是1 2 3 3 5 6，则1 xor 2 xor 3 xor 3 xor 5 xor 6 = 0

【数据范围】

对于20%的数据，1<=n<=100

对于100%的数据，1<=n <= 10^5

一般这种异或都是按位一位一位做的

对于某第k位，如果为1，那么说明

所有连续和异或的这第k位为1

如果满足这第k位为1的(s[i]-s[j])有cnt个

如果cnt为奇数，那么说明答案的第k位也等于1

如何求出第k位为1的(i,j)对数？

如果sum[i]第k位为1：

为了使第k位为1，要么sum[j]第k位为0且sum[j]前k-1位小于sum[i]前k-1位的大小

原因是如果红色条件不成立，进位后就变成了0

还有就是sum[j]第k位为1且sum[j]前k-1位大于sum[i]前k-1位的大小

同理，也是进位的问题

那么红色部分要求满足大小关系的对数，用两个树状数组就行

第k位为0同理

 #include<iostream>

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 using namespace std;

 int c[][],s[],a[],ans;

 int pw[],n;

 void add(int x,int y)

 {

   while (x<=)

     {

       c[x][y]++;

       x+=(x&(-x));

     }

 }

 int query(int x,int y)

 {

   int sum=;

   while (x)

     {

       sum+=c[x][y];

       x-=(x&(-x));

     }

   return sum;

 }

 int main()

 {int i,j,flag,cnt;

   cin>>n;

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

     {

       scanf("%d",&s[i]);

       s[i]+=s[i-];

     }

   pw[]=;

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

     pw[i]=pw[i-]*;

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

     if (pw[i]<=s[n])

       {

     memset(c,,sizeof(c));

     flag=;

     add(,);

     for (j=;j<=n;j++)

       {

         int tmp=s[j]&pw[i];

         if (tmp) cnt=query(a[j]+,)+query(,)-query(a[j]+,);

         else cnt=query(a[j]+,)+query(,)-query(a[j]+,);

         if (cnt%==) flag^=;

         add(a[j]+,(bool)tmp);

         if (tmp) a[j]|=pw[i];

       }

     if (flag) ans|=(pw[i]);

       }

   cout<<ans;

 }

巴特西

[TJOI2017]异或和

题目描述

输入输出格式

输入输出样例

说明

最新文章

热门文章