BZOJ 2821: 作诗(Poetize)( 分块 )
分块,分成N^0.5块.O(N^1.5)预处理出sm[i][j]表示前i块中j的出现次数, ans[i][j]表示第i~j块的答案. 然后就可以O(N^0.5)回答询问了.总复杂度O((N+Q)N^0.5)
-----------------------------------------------------------------------------------------
-----------------------------------------------------------------------------------------
2821: 作诗(Poetize)
Time Limit: 50 Sec Memory Limit: 128 MB
Submit: 2234 Solved: 627
[Submit][Status][Discuss]
Description
神犇SJY虐完HEOI之后给傻×LYD出了一题:
SHY是T国的公主,平时的一大爱好是作诗。
由于时间紧迫,SHY作完诗之后还要虐OI,于是SHY找来一篇长度为N的文章,阅读M次,每次只阅读其中连续的一段[l,r],从这一段中选出一些汉字构成诗。因为SHY喜欢对偶,所以SHY规定最后选出的每个汉字都必须在[l,r]里出现了正偶数次。而且SHY认为选出的汉字的种类数(两个一样的汉字称为同一种)越多越好(为了拿到更多的素材!)。于是SHY请LYD安排选法。
LYD这种傻×当然不会了,于是向你请教……
问题简述:N个数,M组询问,每次问[l,r]中有多少个数出现正偶数次。
Input
输入第一行三个整数n、c以及m。表示文章字数、汉字的种类数、要选择M次。
第二行有n个整数,每个数Ai在[1, c]间,代表一个编码为Ai的汉字。
接下来m行每行两个整数l和r,设上一个询问的答案为ans(第一个询问时ans=0),令L=(l+ans)mod n+1, R=(r+ans)mod n+1,若L>R,交换L和R,则本次询问为[L,R]。
Output
输出共m行,每行一个整数,第i个数表示SHY第i次能选出的汉字的最多种类数。
Sample Input
1 2 2 3 1
0 4
1 2
2 2
2 3
3 5
Sample Output
0
0
0
1
HINT
对于100%的数据,1<=n,c,m<=10^5
Source
最新文章
- python学习笔记(基础一:&#39;hello world&#39;、变量、字符编码)
- 大漠绑定测试工具-VB6
- Webpack - CommonJs &; AMD 模块打包器
- c# winform窗体闪烁解决方法
- Atitit.dwr3 不能显示错误详细信息的解决方案,控件显示错误详细信息的解决方案 java .net php
- 创建git标签【转】
- 第4条:多用类型常量,少用#define预处理指令
- 开通博客第一天 (先发一些android(java)常见异常信息
- iOS_SN_BlueTooth( 一)蓝牙相关基础知识
- [Android] 停止、恢复 背影音乐的播放
- pjax 笔记
- Zepto.js库touch模块代码解析
- windows下运行Eigen
- html之head标签
- css 如何“画”一个抽奖转盘
- WebGL学习笔记(二)
- FNDLOAD Commands to Download Different Seed Data Types. (DOC ID 274667.1)
- Selenium2.0 Webdriver 随笔
- python(unittest)报告导出(一):使用HTMLTestRunner导出
- Jmeter系列-自动生成html报告
热门文章
- JavaScript常用内置对象(window、document、form对象)
- UNIX网络编程卷1 时间获取程序server UDP 协议无关
- Objective-C内存管理教程和原理剖析(三)
- 如何获取启动文件路径 GetModuleFileName
- .Net 数组去除重复项
- MMDrawerController 的实践,已经实现,几行简单的代码实现侧栏
- 共享bean
- Codility 1: equilibrium
- USACO Section 5.1 Musical Themes(枚举)
- C++学习之指针的常见错误