时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld
题目描述
给你一个长为n的序列a，m次查询区间[l,r]内出现次数第k1小的数中值第k2小的数是多少？
保证输入合法
输入描述:
第一行一个数n
第二行n个数表示序列a
第三行一个数m
之后m行每行四个数表示l r k1 k2
输出描述:
对于每次询问输出一行一个数表示答案
示例1
输入
10
3 6 6 8 3 10 1 6 5 6
10
4 7 1 2
5 7 1 1
5 6 1 2
2 6 2 1
8 9 1 1
6 9 1 2
1 2 1 1
1 4 2 1
5 7 1 3
2 6 1 3
输出
3
1
10
6
5
5
3
6
10
10
说明
3 6 6 8 3 10 1 6 5 6
[4,7]中出现1次的有1,3,8,10，第2小的是3
[5,7]中出现1次的有1,3,10，第1小的是1
[5,6]中出现1次的有3,10，第2小的是10
[2,6]中出现2次的有6，第1小的是6
[8,9]中出现1次的有5,6，第1小的是5
[6,9]中出现1次的有1,5,6,10，第2小的是5
[1,2]中出现1次的有3,6，第1小的是3
[1,4]中出现2次的有6，第1小的是6
[5,7]中出现1次的有1,3,10，第3小的是10
[2,6]中出现1次的有3,8,10，第3小的是10
备注:
对于100%的数据，
有1<=n,a[i],m<=40000
数据保证一定能找到那个数
题目链接：E.数列查找
比赛的时候用莫队+线段树求去重后的第$k_1$小出现次数+set求第$k_2$小的值，偷懒的办法果然就$TLE$了……，（然后胡思乱想还想到复杂的主席树上去了，燃鹅我这样的弱比不知道怎么套到这题里去）。
赛后看了别人的代码发现是用分块来做$k_2$的，用第$i$个块来维护值为$[B[i].l,B[i].r]$内的出现次数为$j$的数字的个数，比如第1个块中有1,2,3,3,6这五个数，那么$B[1][1]=3$，$B[1][2]=1$，这样一来查询的时候就可以从小到大遍历如果这个块内出现对应次数的数的个数小于$k_2$,说明答案在下一个块；如果大于等于$k_2$,说明就在当前块中，暴力遍历当前块内的所有元素，只看出现次数为对应次数的数值即可。
搞$k1$可以再开一个数组+$set$或者用直接用线段树在树上二分求，后者建树范围要控制在$[1,最大出现次数]$，否则很可能还是$TLE$
代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
using namespace std;
const int N = 40010;
const int M = 210;
struct info
{
int l, r, id, k1, k2, b;
bool operator<(const info &rhs)const {
return b < rhs.b || (b == rhs.b && r < rhs.r);
}
} Q[N];
int arr[N], ans[N], cnt[N], tcnt[N], Ecnt[N];
set<int>st;
namespace Block {
struct block
{
int l, r;
} B[M];
int _cnt[M][N];
int unit = 200, bcnt = 200;
int belong[N];
void init()
{
for (int i = 1; i <= 200; ++i)
{
B[i].l = (i - 1) * unit + 1;
B[i].r = i * unit;
}
for (int i = 1; i <= 40000; ++i)
belong[i] = (i - 1) / unit + 1;
}
void update(int x, int v)
{
int val = arr[x];
int pc = cnt[val];
int nc = cnt[val] + v;
int b = belong[val];
--_cnt[b][pc];
++_cnt[b][nc];
}
int query(int ecnt, int k)
{
for (int i = 1; i <= bcnt; ++i)
{
if(_cnt[i][ecnt] < k)
k -= _cnt[i][ecnt];
else
{
for (int j = B[i].l; j <= B[i].r; ++j)
{
if(cnt[j] == ecnt && --k == 0)
return j;
}
break;
}
}
return 0;
}
}
void update(int ecnt, int v)
{
int pc = Ecnt[ecnt], nc = (Ecnt[ecnt] += v);
if(pc == 0 && nc == 1)
st.insert(ecnt);
else if(pc == 1 && nc == 0)
st.erase(ecnt);
}
int main(void)
{
int n, i, m;
scanf("%d", &n);
int maxcnt = 0;
for (i = 1; i <= n; ++i)
scanf("%d", &arr[i]), ++tcnt[arr[i]], maxcnt = max(maxcnt, tcnt[arr[i]]);
scanf("%d", &m);
int unit = sqrt(n);
for (i = 0; i < m; ++i)
{
scanf("%d%d%d%d", &Q[i].l, &Q[i].r, &Q[i].k1, &Q[i].k2);
Q[i].id = i;
Q[i].b = Q[i].l / unit;
}
int L = Q[0].l, R = L - 1;
sort(Q, Q + m);
Block::init();
for (i = 0; i < m; ++i)
{
while (L > Q[i].l)
{
--L;
int pc = cnt[arr[L]], nc = pc + 1;
if(pc >= 1)
update(pc, -1);
update(nc, 1);
Block::update(L, 1);
++cnt[arr[L]];
}
while (L < Q[i].l)
{
int pc = cnt[arr[L]], nc = pc - 1;
update(pc, -1);
if(nc >= 1)
update(nc, 1);
Block::update(L, -1);
--cnt[arr[L]];
++L;
}
while (R > Q[i].r)
{
int pc = cnt[arr[R]], nc = pc - 1;
update(pc, -1);
if(nc >= 1)
update(nc, 1);
Block::update(R, -1);
--cnt[arr[R]];
--R;
}
while (R < Q[i].r)
{
++R;
int pc = cnt[arr[R]], nc = pc + 1;
if(pc >= 1)
update(pc, -1);
update(nc, 1);
Block::update(R, 1);
++cnt[arr[R]];
}
auto it = st.begin();
advance(it, Q[i].k1 - 1);
int ecnt = *it;
ans[Q[i].id] = Block::query(ecnt, Q[i].k2);
}
for (int i = 0; i < m; ++i)
printf("%d\n", ans[i]);
return 0;
}