给定n个数，令符号[l, r, t]表示第l个数到第r个数中第t大的值。
对于给定的len、y和k，求多重集{[l,r,(r-l+1)/len*y] | (r-l+1) mod len=0}中的第k大值
具体来说，这个多重集包含：
每个长度是len的区间中第y大的值，
每个长度是2len的区间中第2y大的值，
每个长度是3len的区间中第3y大的值，
……
以此类推。
对于下面的样例，这个多重集是{2, 3, 3, 4}
第一行四个数，n, len, y, k (n ≤ 100000, y ≤ len ≤ n, k ≤ 长度为len倍数的区间个数)
第二行n个，每个数 ≤ n
输出一个数表示答案
样例输入 4 2 1 3 2 1 3 4样例输出 3思路：二分答案ans 把原数组中大于等于ans的看成len-y，小于ans的看成-y 然后统计多少个（长度是len倍数的)区间总和大于等于0，记作C
根据C和K的大小关系决定向左还是向右二分答案。
可以利用前缀偏移和树状数组统计多少个（长度是len倍数的)区间总和大于等于0。
#include<bits/stdc++.h> using namespace std; const int MAX=1e5+30; const int MOD=1e9+9; const double PI=acos(-1.0); typedef long long ll; int a[MAX],n,len,y; ll A[MAX],b[MAX],c[MAX],v[MAX]; void add(int x,int y) { while(x<=n+1) { A[x]+=y; x+=x&(-x); } } ll ask(int x) { ll ans=0; while(x) { ans+=A[x]; x-=x&(-x); } return ans; } ll check(int x) { for(int i=1;i<=n;i++) { b[i]=a[i]>=x?len-y:-y; b[i]+=b[i-1]; c[i]=b[i]; } c[n+1]=0; sort(c+1,c+n+2); int cd=unique(c+1,c+n+2)-c-1; for(int i=0;i<=n;i++)v[i]=lower_bound(c+1,c+cd+1,b[i])-c;//将前缀和的值离散化，方便插入树状数组 ll ans=0; for(int i=0;i<len;i++)//前缀偏移枚举区间 { add(v[i],1); for(int j=i+len;j<=n;j+=len) { ans+=ask(v[j]);//统计之前插入的前缀和b[x]中，有多少个b[x]<=b[j]，即有多少个以j为结尾的长度为len的倍数的区间和大于等于0. add(v[j],1); } add(v[i],-1);//清除树状数组 for(int j=i+len;j<=n;j+=len)add(v[j],-1); } return ans; } int main() { ll k; cin>>n>>len>>y>>k; for(int i=1;i<=n;i++)scanf("%d",&a[i]); int l=-1e9,r=n,ans=0; while(r>=l) { int mid=(l+r)/2; if(check(mid)>=k) { ans=mid; l=mid+1; } else r=mid-1; } cout<<ans<<endl; return 0; }