A - The kth number
Problem 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:
int 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
Sample Input
1 6 3 13 14 15 13 14 13 1 6 3 1 6 1 3 5 2
Sample Output
1 3 1
题意
给你个数列a1~an,定义在一个区间内，一个数的frequency为它在区间内出现的次数
现在有m个询问，每个询问(l,r,k),要求输出区间[l,r]之间第k大的frequency为多少
A：The kth number
假如对于询问的区间我们有这样一个数组freq【i】表示出现次数大于等于i次的数的个数，那么答案可以利用二分得出
接下来要做的就是始终维护freq的信息是当前要询问的区间的信息，每次询问二分一下。
将所有的左端点分成sqrt块之后第一个关键字按照左端点的块排序，第二个关键字按照右端点排序。
相邻两个询问在同一块内：对于每个组的询问，右端点最多右移n, 对于每两个相邻询问，左端点最多移动sqrt(n)
相邻两个询问在不同块内：最多只会有sqrt n次这种情况，每次O(n)移动也无所谓
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int N = 101000;
const int Sqrt = 333;
int ll[N],rr[N],kk[N],idx[N],n,m,a[N],freq[N],cnt[N],ans[N];
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 l = 1,r = 100000;
while (l<=r) {
int mid = l+r>>1;
if (freq[mid]>=k) {
l = mid+1;
} else {
r = mid-1;
}
}
return l-1;
}
int main() {
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
int cas;
scanf("%d",&cas);
while (cas--) {
scanf("%d%d",&n,&m);
for (int i = 0; i < n; i ++) {
scanf("%d",a+i);
}
for (int i = 0; i < m; i ++) {
scanf("%d%d%d",ll+i,rr+i,kk+i); ll[i] --; rr[i] --;
idx[i] = i;
}
sort(idx,idx+m,cmp);
memset(freq,0,sizeof(freq));
memset(cnt,0,sizeof(cnt));
int cl = 0,cr = -1;
for (int i = 0; i < m; i ++) {
int l = ll[idx[i]];
int r = rr[idx[i]];
int 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 = 0; i < m; i ++) {
printf("%d\n",ans[i]);
}
}
return 0;
}