题意：
给你n个数，你要将其分成k个区间，并且任意一个区间中，值在[x,y]中的数的个数要大于值不在[x,y]中的数的个数。问你y-x要最小的话，x和y分别是什么，并且要将这k个区间的左右端点输出。
题解：
嗨呀，果然是水题以前做太少基础都不扎实了，做到这种有那么一点点需要思考的题目才找回感觉嘛。
怎么找x,y使得y-x最小？我最直接的想法就是从小到大枚举y的时候确定x，如何确定才能避免时间复杂度变成O(N^2).尺取。
由于尺取的时间复杂度为O(N)，因此我们不能将检查当前情况正确性的时间复杂度变为O(N)，如何进行快速的检查？
这就需要你找到一个性质：由于每个区间中，在[x,y]的数量要至少比不在[x,y]的数量大1，那么假设在[x,y]中的值我们看成1，不在[x,y]中的值我们看成-1.要使得最后的区间能够至少k个，所有值加起来要>=k.原因自己探究，我是列了一些样例感觉是对的就没有深思。
所以我们只需要在尺取的时候检查当前在[x,y]中的数量要比不在[x,y]中的数量至少大k即可。
但是最后要你求出这个区间到底怎么分呢？
我们知道区间是连续的，那么每一个-1一定要找左边或者右边离他最近的1来消掉负面影响，我就使用了一个set存所有1的位置。
并且找到了之后，将当前的-1和对应的1的值变为0，代表他们的正负影响抵消了。
那么最后这个数组只剩下了1和0.那么我们只需要将其分成k个区间，并且保证每个区间值的和至少是1即可。那么我这里使用了贪心，从左往右找，只要和为1，就输出。因为1的数量一定是>=k的，所以正确性能保证，但注意第k个区间要特殊处理，将剩下的所有位置给包括即可。
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int num[N],a[N],b[N];
int main(){
int t;
scanf("%d",&t);
while(t--){
int n,k;
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)scanf("%d",&a[i]),b[i]=a[i];
sort(b+1,b+1+n);
int all=unique(b+1,b+1+n)-b-1;
for(int i=1;i<=n;i++)
num[int(lower_bound(b+1,b+1+all,a[i])-b)]++;
int l=1,r=1,s=0;
int ansl,ansr,ans=1e9;
while(r<=all){
s+=num[r];
if(s-(n-s)>=k){
while(s-num[l]-(n-s+num[l])>=k)s-=num[l++];
if(b[r]-b[l]<ans)ans=b[r]-b[l],ansl=b[l],ansr=b[r];
}
r++;
}
printf("%d %d\n",ansl,ansr);
set<int>st;
for(int i=1;i<=n;i++){
b[i]=(ansl<=a[i] && a[i]<=ansr)?1:-1;
if(b[i]==1)
st.insert(i);
}
for(int i=1;i<=n;i++){
if(b[i]==-1){
set<int>::iterator it=st.upper_bound(i);
if(it!=st.begin())it--;
b[i]=b[*it]=0;
st.erase(it);
}
}
l=1,r=1,s=0;
for(int i=1;i<k;i++){
while(s==0)s+=b[r++];
s=0;
printf("%d %d\n",l,r-1);
l=r;
}
printf("%d %d\n",l,n);
for(int i=1;i<=all;i++)num[i]=0;
}
}