Codeforces Round #365 (Div. 2) D. Mishka and Interesting sum 离线操作，树状数组，last[value]，异或和

Source

Codeforces Round #365 (Div. 2)

My Solution

离线操作，树状数组，last[value]，异或和

首先，根据位异或的性质， 有一个结论：区间内所有出现次数为偶数的元素的异或和 == (区间内所有元素的异或和) ^ (区间内所有不同元素的异或和)

1、对于求  (区间内所有元素的异或和)  可以用 前缀异或和

2、对于(区间内所有不同元素的异或和)， 则要用类似于求 区间不同的元素的个数 的算法

2016 UESTC Training for Data Structures K - 郭大侠与甲铁城 树状数组+离线操作

先把所有询问储存下来， 然后根据右端点排序；

然后对于 last[value] 记录的是到 当前 ans[i].r之前的 最近的一个 value 出现的位置， 相当于所有的相同的元素都保留尽可能靠近又端点的那个位置的元素；

用一个 lastRight对象表示 上一次的r， 然后当前 从 lastRight 向 ans[i].r 更新， 把 出现相同元素的只保留离右端点最近的那个 ，

即如果last[a[j]] != j， 说明最近一次出现的a[j]不在这里， 所以把 那个 ai去掉 ， 并更新  last[a[j]] = j;

则可以 logn的获得(区间内所有不同元素的异或和) (get(ans[i].r) ^ get(ans[i].l - 1))；add(last[a[j]], a[j]);

//用树状数组+last[value] 求 (区间内所有不同元素的异或和) 的核心代码如下：

sort(ans + 1, ans + m + 1, cmpr);
int lastRight = 1;
for(int i = 1; i <= m; i++){
for(int j = lastRight; j <= ans[i].r; j++){
if(last[a[j]] != j){
add(last[a[j]], a[j]);  //
last[a[j]] = j;
}
}
lastRight = ans[i].r;
ans[i].val = (get(ans[i].r) ^ get(ans[i].l - 1)) ^ (sum[ans[i].r] ^ sum[ans[i].l - 1]); //

}

总复杂度 O(nlogn)

此外

1、最开始的时候用的  //ios::sync_with_stdio(false); cin.tie(0); 关掉同步的cincout， 迷之TLE好多发，最后实在没办法了用 scanf printf 代替关掉同步的cincout， 结果又过了。经过笔者和一个好朋友讨论以后，有一个猜测 如果是读字符串可能是 关掉同步的cincout更快， 如果是读数字可能是 scanf printf更快， 但基本上没有什么依据，唯一的一点依据是 他有一次 scanf printf 一直TLE， 但 改用 关掉同步的cin cout 就过了， 情况刚好和这里相反 ⊙﹏⊙‖∣， 而他那次是处理字符串。

2、关于用树状数组+last[value] 求 (区间内所有不同元素的异或和)  或 (区间不同元素的总数)， 的last[value]，最开始的时候担心 value比较大，所以把value离散化了last[Ind[value]]，后来发现 还是直接 把 原来的 last数组 改成 map<int, int> last; 好， 这样就不用离散化操作了。

#include 
#include 
#include 

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx