首页 > 代码库 > 莫队算法
莫队算法
http://www.cnblogs.com/hzf-sbit/p/4056874.html
https://www.zhihu.com/question/27316467/answer/36260465
处理一类无修改的离线区间询问问题
复杂度为O(n*sqrt(n)*a),a为单次更新操作的复杂度。
作者:张瑯小强 链接:https://www.zhihu.com/question/27316467/answer/130423804 来源:知乎 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。 ********************************* 问题:有n个数组成一个序列,有m个形如询问L, R的询问,每次询问需要回答区间内至少出现2次的数有哪些。 ********************************* int len; // 块长度 struct Query{ int L, R, ID, block; Query(){} // 构造函数重载 Query(int l, int r, int ID):L(l), R(r), ID(ID){ block = l / len; } bool operator < (const Query rhs) const { if(block == rhs.block) return R < rhs.R; // 不是if(L == rhs.L) return R < rhs.R; return L < rhs.L return block < rhs.block; // 否则这就变回算法一了 } }queries[maxm]; map<int, int> buf; inline void insert(int n){ if(buf.count(n)) ++buf[n]; else buf[n] = 1; } inline void erase(int n){ if(--buf[n] == 0) buf.erase(n); } int A[maxn]; // 原序列 queue<int> anss[maxm]; // 存储答案 int main(){ int n, m; cin >> n; len = (int)sqrt(n); // 块长度 for(int i = 1; i <= n; i++){ cin >> A[i]; } cin >> m; for(int i = 1; i <= m; i++){ int l, r; cin >> l >> r; queries[i] = Query(l, r, i); } sort(queries + 1, queries + m + 1); int L = 1, R = 1; buf[A[1]] = 1; for(int i = 1; i <= m; i++){ queue<int>& ans = anss[queries[i].ID]; Query &qi = queries[i]; while(R < qi.R) insert(A[++R]); while(L > qi.L) insert(A[--L]); while(R > qi.R) erase(A[R--]); while(L < qi.L) erase(A[L++]); for(map<int, int>::iterator it = buf.begin(); it != buf.end(); ++it){ if(it->second >= 2){ ans.push(it->first); } } } for(int i = 1; i <= m; i++){ queue<int>& ans = anss[i]; while(!ans.empty()){ cout << ans.front() << ‘ ‘; ans.pop(); } cout << endl; } }
在update的同时更新ans。(本题可考虑维护一个set,表示出现至少两次的数的集合)
莫队算法
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。