111

发布时间 2023-11-26 18:12:47作者: 最爱丁珰

首先将原区间分块(设块的大小是T)

先处理处每一个数字的vector

再处理一个num数组,表示一连串子块之间的出现了偶数次的数字的个数。复杂度为\(O(T^2)\)

对于每一个询问

如果询问的端点再同一个块里面,暴力循环记录每一个数字的出现次数(cnt数组)输出答案,然后再暴力循环把每一个数字对cnt数组的改变给变回来。复杂度\(O(T)\)

如果不在同一块里面,设左端点的块为\(p\),右端点的块为\(q\)

首先让ans加上\([p+1,q-1]\)这些块里面的num之和

对需要暴力处理的每一个数字,统计出来它在暴力区间里面的个数和整个区间的个数,分别为a和b,那么\(b-a\)就是这个数字在块里面的出现次数

\(b-a\)为奇数且a为奇数,那么ans++

\(b-a\)为偶数且a为奇数,那么ans--