题面 。
之前做过一道很类似的题目 洛谷P4168蒲公英 ，然后看到这题很快就想到了解法，做完这题可以对比一下，真的很像 。
【洛谷 P4135 作诗 题解】题目要求区间内出现次数为正偶数的数字的数量 。
数据范围1e5，可以分块 。
我们预处理出这么两个数组 。
一个是某个数字出现次数的分块前缀和，这个很简单 。
一个是sum[ i ][ j ]代表从第i个分块到第j个分块出现次数为正偶数的数字的个数 。
这个数组很好维护，只需要枚举左端点分块和右端点分块然后统计数字出现次数即可 。
这些代码里有一些细节，可以结合注释理解 。
for(int i=1;i<=get_pos(n);i++){ int kin=0; for(int j=i;j<=get_pos(n);j++){ for(int k=(j-1)*len+1;k<=min(n,j*len);k++){//这里有一些细节 tmp[a[k]]++; if((tmp[a[k]]&1))//如果这个数加完之后变成了奇数 if(tmp[a[k]]>1)//如果加完之后出现次数大于一，那么这个数就作为正偶数被统计进答案了，要减掉 kin--; else//否则这个数在加一之前没有被统计过，没有必要更改，这里写个else是因为防止与下面那个else产生冲突 kin+=0; else//加完之后如果变成了偶数那肯定从奇数变成了正偶数，对答案有贡献 kin++; } sum[i][j]=kin; } for(int j=1;j<=c;j++)//清空辅助数组 tmp[j]=0; }接下来处理询问 。
对于询问的l,r，算出其所在的分块lb,rb 。
若l，r所在分块相同或相邻则暴力计算，时间复杂度n1/2 。
若l，r所在分块之间相隔至少一个分块，那么先将答案设成这两个分块之间的出现次数为正偶数的数字数量 。
然后，计算两边散块内数字对答案的贡献 。
情况较多，可结合注释理解 。
void get_q(){ ans=0; for(int i=l;i<=lb*len;i++){ tmp[a[i]]++; if(tmp[a[i]]&1)//如果这个数在散块中出现次数为奇数 if((tim[rb-1][a[i]]-tim[lb][a[i]])&1)//如果它在中间块中出现次数为奇数，那么它没有被预先统计进答案里，且目前它对答案有贡献 ans++; else//如果这个数在中间块中出现次数为偶数 if(tim[rb-1][a[i]]-tim[lb][a[i]]>0)//如果这个数在中间块中出现次数为正偶数，那么它已经作为答案被统计过了，现在不符合条件要减掉 ans--; else//这个数并没有作为答案被统计过 if(tmp[a[i]]>1)//如果这个数在散块中之前已经作为正偶数被统计了，要减掉 ans--; else//否则并没有影响 ans-=0; else//这个数在散块中出现次数为偶数 if(tim[rb-1][a[i]]-tim[lb][a[i]]&1)//如果这个数在中间块中出现次数为奇数，那么这个数的出现次数被作为正偶数统计过，要减掉 ans--; else//否则这个数之前没有算进答案里，要加进去 ans++; } for(int i=(rb-1)*len+1;i<=r;i++){//以下分类同上 tmp[a[i]]++; if(tmp[a[i]]&1) if((tim[rb-1][a[i]]-tim[lb][a[i]])&1) ans++; else if(tim[rb-1][a[i]]-tim[lb][a[i]]>0) ans--; else if(tmp[a[i]]>1) ans--; else ans-=0; else if(tim[rb-1][a[i]]-tim[lb][a[i]]&1) ans--; else ans++; } for(int i=l;i<=lb*len;i++)//清空辅助数组 tmp[a[i]]--; for(int i=(rb-1)*len+1;i<=r;i++) tmp[a[i]]--; ans+=sum[lb+1][rb-1];}
经验总结扩展阅读
- 带权bitset?/bitset优化莫队 模板 洛谷P4135 Ynoi2016 掉进兔子洞 题解
- 洛谷P5309 Ynoi 2011 初始化 题解
- 洛P8109题解
- 自是指物作诗立就是什么意思 自是指物作诗立就的意思是什么
- 好听的微信名字诗意