[TJOI2017]异或和
题目描述
在加里敦中学的小明最近爱上了数学竞赛，很多数学竞赛的题都是与序列的连续和相关的。所以对于一个序列，求出它们所有的连续和来说，小明觉得十分的简单。但今天小明遇到了一个序列和的难题，这个题目不仅要求你快速的求出所有的连续和，还要快速的求出这些连续和的异或值。小明很快的就求出了所有的连续和，但是小明要考考你，在不告诉连续和的情况下，让你快速求是序列所有连续和的异或值。
输入输出格式
输入格式：
第一行输入一个n,表示这序列的数序列 第二行输入n个数字a1,a2…an代表这个序列
0<=a1,a2,…an，0<=a1+a2…+an<=10^6
输出格式：
输出这个序列所有的连续和的异或值
输入输出样例
输入样例#1：
1 | 3 |
输出样例#1：
1 | 0 |
说明
【样例解释】
序列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%的数据，
题解
这道题想到按位统计就不难。（不过快速统计看了眼题解才想起来用树状数组太菜了。。）
题目相当于求
求和实在XOR意义下的。
前缀和肯定看到连续区间和就不难想到了。
这样考虑如果我们枚举每一位，然后枚举当前的
如何快速知道有哪些
可以与当前的
相减使得枚举位为1呢？
分类讨论：
- 如果枚举的值当前位是1的话，假如对于一个
它的当前位也是1，并且前面的位比当前的S_i要大，那么
通过借位(肯定是可以借位的，因为给出的数均非负！这点很重要，这意味着它一定有高位可以借位)
当前位是1。
假如
当前位是0，显然前面的位之和要小于
如果当前
的这一位是0，和上面恰恰相反，不难分析。
然后应该想到权值树状数组！！！
然后这道题就很容易的AC了。
Code：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
int p[maxn] , n , s[maxn] ;
long long ans , bit[2][1000005];
inline void update(int pos , int v , int num)
{
for(int i = pos + 1 ; i <= s[n] ; i += i & -i)
bit[num][i] += v;
}
inline int query(int pos , int num)
{
int ans = 0;
for(int i = pos + 1 ; i ; i -= i & -i)
ans += bit[num][i];
return ans;
}
int main()
{
scanf("%d",&n);
for(int i = 1 ; i <= n ; ++i)
scanf("%d",&p[i]);
for(int i = 1 ; i <= n ; ++i)
s[i] = s[i-1] + p[i];
for(int k = 0 ; (1 << k) <= s[n] ; ++k){
int S = (1 << k) - 1 , tot = 0;
std::memset(bit,0,sizeof(bit));
for(int j = 0 ; j <= n ; ++j){ // when j = 0 , the bit only add 1 for convenient
int ty = (s[j] >> k) & 1 , now = s[j] & S;
if(ty == 1){
tot += query(now , 0) + query(S , 1) - query(now, 1);
update(now , 1 , 1);
}
else tot += query(now , 1) + query(S , 0) - query(now, 0) , update(now , 1 , 0);
}
ans += 1ll * (1 << k) * (tot & 1);
}
printf("%lld",ans);
}
[AHOI2008]逆序对
题目描述
暑假到了，小可可和伙伴们来到海边度假，距离海滩不远的地方有个小岛，叫做欢乐岛，整个岛是一个大游乐园，里面有很多很好玩的益智游戏。碰巧岛上正在举行“解谜题赢取免费门票”的活动，只要猜出来迷题，那么小可可和他的朋友就能在欢乐岛上免费游玩两天。
迷题是这样的：给出一串全部是正整数的数字，这些正整数都在一个范围内选取，谁能最快求出这串数字中“逆序对”的个数，那么大奖就是他的啦！
当然、主办方不可能就这么简单的让迷题被解开，数字串都是被处理过的，一部分数字被故意隐藏起来，这些数字均用-1来代替，想要获得大奖就必须求出被处理的数字串中最少能有多少个逆序对。小可可很想获得免费游玩游乐园的机会，你能帮助他吗？
注：“逆序对”就是如果有两个数A和B，A在B左边且A大于B，我们就称这两个数为一个“逆序对”，例如：4 2 1 3 3里面包含了5个逆序对：(4, 2)、(4, 1)、(4, 3)、(4, 3)、(2, 1)。
1 | 假设这串数字由5个正整数组成，其中任一数字N均在1～4之间，数字串中一部分数字被“-1”替代后，如：4 2 -1 -1 3 ，那么这串数字，可能是4 2 1 3 3，也可能是4 2 4 4 3，也可能是别的样子。你要做的就是根据已知的数字，推断出这串数字里最少能有多少个逆序对。 |
输入输出格式
输入格式：
第一行两个正整数N和K；
第二行N个整数，每个都是-1或是一个在1~K之间的数（N<=10000，K<=100）。
输出格式：
一个正整数，即这些数字里最少的逆序对个数。
输入输出样例
输入样例#1：
1 | 5 4 |
输出样例#1：
1 | 4 |
说明
100%的数据中，N<=10000，K<=100。
60%的数据中，N<=100。
40%的数据中，-1出现不超过两次。
题解
以前考试，看到这道题不会，觉得自己很弱，却从没想到要去认认真真把它弄明白。
今天自己认真想了想，仅仅用了不到半小时就一遍AC了。
真的很难吗？
也许平时的思维懒惰，某些时候有一点思路就当自己会了，某种程度上造成了我现在的结果？
正式：
首先要发现填入的数单调不降这个性质，可以用数学推导法证明决策包容性。
然后这道题其实就做完了，记录每个-1处填什么的时候对答案贡献了多少逆序对即可。
Code：
1 |
|