#Description 一个数组，要求先对前n个数字排序（以方便后续操作）；又要求对前n+i个数字排序；又要求对前n+j ... 前n+k个数字排序（i、j、k的大小远小于n，且i、j、k间没有大小关系）。总之就是对一个不定的范围内数据要进行频繁的按大小顺序调用，但是这个范围边界变化不大，很多数据重叠，这样每次都对此次区间内数据排序，频繁排序的话很费时间。
例如一个数组\(\{1,3,6,5,2,4,1,9,0\}\)，一共9个数字，下标08。要求： 每次取一个区间，计算区间内\((最大值-最小值)^2+(次大值-次小值)^2+(次次大值-次次小值)^2+...\)的值。很容易想到对区间排个序，即可方便获得最大、次大值等。 对15排序：\(\{2,3,4,5,6\}\) 对16排序：\(\{1,2,3,4,5,6\}\) 对25排序：\(\{2,4,5,6\}\) 可以看出2、5、6始终在范围内，但每次都要针对所选区间重新排序，很麻烦。 既然大部分数据一直出现在范围内，现在就希望能够一次排序，应对所有情况。
#Key 继续使用上述的例子：\(Array = \{1,3,6,5,2,4,1,9,0\}\) 开个新数组作其索引：\(Index = \{0,1,2,3,4,5,6,7,8\}\) 令索引数组按照\(Array\)的大小关系排序，得\(Index = \{8,0,6,4,1,5,3,2,7\}\)
对于区间[1, 5]：从左向右找出第一个在[1, 5]的下标即为最小值：8不符合、0不符合、6不符合，4符合，那么最小值就是\(Array[4] = 2\)，次大值就是\(Array[1] = 3\) ...
即每次只需检测排序后当前位的数字的下标是否在该区间内即可。
#Sample 题目：https://hihocoder.com/problemset/problem/1384 一道贪心的题，期间需要对下标i到j、i到j+k之间的数字分别排序。是别人家的代码（他的原文链接，虽然我也不知道他是不是转别人的），就是在这学到的技巧。注意观察judge函数与judge2函数的差异，judge2函数即实现了上述排序思想。 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
using namespace std;
typedef long long int ll;
ll m,n,k;
ll a[500050];
ll b[500050];
int cnt=0;
inline bool cmp(int x,int y)
{
return a[x]<a[y];
}
bool judge(int l,int r)
{
int pos=0;
while(l+pos<=r)b[pos]=a[l+pos],pos++;
sort(b,b+pos);
pos--;
int mid=(pos-1)/2;
ll res=0;
for(int i=0; i<=mid&&i<m; i++)
{
res+=(b[i]-b[pos-i])*(b[i]-b[pos-i]);
if(res>k)
return false;
}
return res<=k;
}
void init(int l,int r)
{
cnt=0;
for(int i=l; i<=r; i++)b[cnt++]=i;
sort(b,b+cnt,cmp);
}
bool judge2(int r)
{
int i,j,kk;
ll res=0;
for(i=0,j=cnt-1,kk=m; kk; i++,j--,kk--)
{
while(i<j&&b[i]>r)i++;
while(i<j&&b[j]>r)j--;
if(i>=j)break;
res+=(a[b[i]]-a[b[j]])*(a[b[i]]-a[b[j]]);
if(res>k)break;
}
return res<=k;
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%lld%lld%lld",&n,&m,&k);
for(int i=0; i<n; i++)
scanf("%lld",&a[i]);
int ans=0;
int l=0;
while(l<n)
{
int kk=1;
while(kk+l<n&&judge(l,l+kk))
kk*=2;
int first=l+kk/2,last=l+kk-1<n?l+kk-1:n-1;
init(l,last);
int mid;
int pos=l;
while(first<=last)
{
if(judge2(mid=(first+last)/2))
{
first=mid+1;
pos=mid;
}
else
last=mid-1;
}
l=pos+1;
ans++;
}
cout<<ans<<endl;
}
return 0;
}