BZOJ4241 历史研究 【回滚莫队】
题目描述：给出一个长度为\(n\)的数组，每次询问区间 \([l,r]\)，求 \(\max\limits_{x}x*cnt_x\)，其中 \(cnt_x\) 表示 \(x\) 在区间 \([l,r]\) 的出现次数。
数据范围：\(n\le 10^5,a_i\le 10^9\)。
分块也可以做到 \(O(n\sqrt{n})\)，但是空间也是 \(O(n\sqrt{n})\)。使用回滚莫队可以在 \(O(n)\) 空间内解决。
首先上来离散化，然后考虑莫队。发现这个东西增加一个数是 \(O(1)\) 的，但删除一个数至少要 \(O(\log n)\) 才能做，所以我们考虑只增。首先询问按照普通莫队的方法排序，然后处理 \(l\) 在一块，而且 \(r\) 递增的询问。设块的右端点为 \(mid\)，则 \((mid,r]\) 可以只添加数来解决，而 \([l,mid]\) 这一段直接暴力（长度 \(\sqrt{n}\)）。总时间复杂度是 \(O(n\sqrt{n})\) 的。
于是像区间众数这种东西也可以用回滚莫队做了。
code
```cpp
#include
#define Rint register int
using namespace std;
typedef long long LL;
const int N = 100003;
int n, m, blo, x[N], val[N], len, ql, qr, mid;
LL cnt[N], qans, ans[N], tt[N];
struct Query {
int l, r, id;
inline bool operator q[i].l) -- ql, add(x[ql]);
ans[q[i].id] = qans;
while(ql
最新文章
- SQL联合查询（内联、左联、右联、全联）的语法
- Mac & XCode 使用技巧总结
- 一排下去再上来的div
- iOS8 Core Image In Swift：视频实时滤镜
- 研究一下FBrush，它是从TWinControl才有的属性（可能是因为需要句柄）——发现{$R *.dfm}在运行期执行，而且很有深意，读到属性后赋值还会触发事件，这些无法在VCL代码里直接看到
- mysql去重的最方便的两种方法
- 用Pyton玩转数据练习题---第二周
- 【问题解决方案】ImportError: No module named 'openpyxl'/‘xlrd’
- 把jQuery的类、插件封装成seajs的模块的方法
- 更改MySQL数据库目录位置[zz]
- pyobjc-framework-Cocoa 5.1.2
- 如何修改macbook的MAC地址
- golang管道
- $PDB——Python调试利器详解
- OCP 12c最新考试原题及答案（071-5）
- linux 系统调用exec()
- http://www.cnblogs.com/CBDoctor/p/4459750.html
- CentOS安装Oracle官方JRE
- 页面加载时的div动画
- 设置tableview的滚动范围--iOS开发系列---项目中成长的知识三