ACdream 1108(莫队)
2024-10-07 20:54:24
The kth number
Time Limit: 12000/6000MS (Java/Others)Memory Limit: 128000/64000KB (Java/Others)SubmitStatisticNext ProblemProblem Description
Do you still remember the Daming Lake's k'th number? Let me take you back and recall that wonderful memory.
Given a sequence A with length of n,and m querys.Every query is defined by three integer(l,r,k).For each query,please find the kth biggest frequency in interval [l,r].
Frequency of a number x in [l,r] can be defined by this code:
123456int
FrequencyOfX = 0;
for
(
int
i = l; i <= r; i ++) {
if
(a[i]==X) {
FrequencyOfX ++;
}
}
Input
First line is a integer T,the test cases.
For each case:
First line contains two integers n and m.
Second line contains n integers a1,a2,a3....an.
Then next m lines,each line contain three integers l,r,k.T<=12
1<=n,m,ai<=100000
1<=l<=r<=n
1<=k
data promise that for each query(l,r,k),the kind of number in interval [l,r] is at least k.Output
for every query,output a integer in a line.Sample Input
1
6 3
13 14 15 13 14 13
1 6 3
1 6 1
3 5 2Sample Output
1
3
1Source
zhangmingmingManager
初次接触莫队算法。屠了一次版。。。哈哈,不要在意这些细节
和平方分割的方法类似,莫队算法的思想大概也是把线性的序列尽量平均的进行分割。
一般用于不需要队数据进行修改的题目,而且必须离线。
这里的排序,都是先按照桶的顺序升序排序,如果桶的顺序相同再按终点排序。
Accepted Code:
/*
* this code is made by Stomach_ache
* Problem: 1108
* Verdict: Accepted
* Submission Date: 2014-09-04 21:32:52
* Time: 1320MS
* Memory: 4248KB
*/
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
/*Let's fight!!!*/ const int Sqrt = ;
const int MAX_N = ;
int a[MAX_N], ans[MAX_N], freq[MAX_N], cnt[MAX_N];
int ll[MAX_N], rr[MAX_N], kk[MAX_N], idx[MAX_N], n, m; bool cmp (int a, int b) {
if (ll[a]/Sqrt == ll[b]/Sqrt) return rr[a] < rr[b];
return ll[a] < ll[b];
} int query(int k) {
int lb = , ub = ;
while (ub - lb > ) {
int mid = (lb + ub) / ;
if (freq[mid] >= k) lb = mid;
else ub = mid;
}
return lb;
} int main() {
int T;
scanf("%d", &T);
while (T--) {
scanf("%d%d", &n, &m);
for (int i = ; i < n; i++) scanf("%d", a+i);
for (int i = ; i < m; i++) {
scanf("%d%d%d", ll+i, rr+i, kk+i);
idx[i] = i; ll[i]--; rr[i]--;
} sort(idx, idx + m, cmp);
memset(freq, , sizeof(freq));
memset(cnt, , sizeof(cnt)); int cl = , cr = -;
for (int i = ; i < m; i++) {
int l = ll[idx[i]], r = rr[idx[i]], k = kk[idx[i]];
while (cr < r) { freq[++cnt[a[++cr]]] ++; }
while (l < cl) { freq[++cnt[a[--cl]]] ++; }
while (r < cr) { freq[cnt[a[cr--]]--] --; }
while (cl < l) { freq[cnt[a[cl++]]--] --; }
ans[idx[i]] = query(k);
} for (int i = ; i < m; i++) printf("%d\n", ans[i]);
} return ;
}
最新文章
- ODBC、OLE DB、 ADO的区别
- [转]jQuery操作radio、checkbox、select 集合.
- Missing (Mono Script), Missing Prefab
- [Android Pro] Android 官方推荐 : DialogFragment 创建对话框
- win7下IIS错误:";无法访问请求的页面,因为该页的相关配置数据无效";的解决方法(转)
- HTML本地测试成功后上传博客注意事项
- springMVC源码浅析
- 八、桥接模式--结构模式(Structural Pattern)
- Swift - 复杂数据类型说明(数组,字典,结构体,枚举)
- CodeForces--TechnoCup--2016.10.15--ProblemA--Transformation: from A to B
- django 发送手机验证码
- 【java虚拟机系列】java虚拟机系列之JVM总述
- Html5学习笔记:图片上传
- 2 jquery选择器
- 各种浏览器下的页面元素xpath获取方法
- Notation, First Definitions 转 http://brnt.eu/phd/node9.html
- git clone远程branch和tag
- msys2 显示git branch
- Redis总体 概述,安装,方法调用
- 实现了一下Berlekamp-Massey
热门文章
- 关于操作系统中英文切换的.po和.mo介绍
- Docker配置JDK1.8
- csps模拟67神炎皇,降雷皇,幻魔皇题解
- LUOGU P4027 [NOI2007]货币兑换 (斜率优化+CDQ分治)
- 使用WCF上传文件
- 13_数据的划分和介绍之sklearn数据集
- 写js过程中遇到的一个bug
- php用正则表达式匹配URL的简单方法(亲测可行)
- python 日记 day4
- 深入浅出 Java Concurrency (22): 并发容器 part 7 可阻塞的BlockingQueue (2)[转]