用主席树写起来跑的快一点，而且也很傻比，二分答案，即二分那个半径就行
主席树求的是区间<=k的个数
#include<bits/stdc++.h> using namespace std; #define maxn 1000005 int a[maxn],n,m; struct Node{int lc,rc,v;}t[maxn*25]; int rt[maxn],tot; int update(int last,int l,int r,int pos){ int now=++tot; t[now]=t[last]; t[now].v++; if(l==r)return now; int m=l+r>>1; if(pos<=m) t[now].lc=update(t[last].lc,l,m,pos); else t[now].rc=update(t[last].rc,m+1,r,pos); return now; } int query(int st,int ed,int L,int R,int l,int r){ if(L>R)return 0; if(L<=l && R>=r)return t[ed].v-t[st].v; int m=l+r>>1,res=0; if(L<=m)res+=query(t[st].lc,t[ed].lc,L,R,l,m); if(R>m)res+=query(t[st].rc,t[ed].rc,L,R,m+1,r); return res; } int build(int l,int r){ int now=++tot; t[now].lc=t[now].rc=t[now].v=0; if(l==r)return now; int m=l+r>>1; t[now].lc=build(l,m); t[now].rc=build(m+1,r); return now; } void init(){ memset(rt,0,sizeof rt); memset(t,0,sizeof t); tot=0; } int main(){ int t;cin>>t; while(t--){ init(); scanf("%d%d",&n,&m); for(int i=1;i<=n;i++)scanf("%d",&a[i]); rt[0]=build(1,n); for(int i=1;i<=n;i++) rt[i]=update(rt[i-1],1,2000000,a[i]); int ans=0,l,r,p,k; while(m--){ scanf("%d%d%d%d",&l,&r,&p,&k); l^=ans,r^=ans,p^=ans,k^=ans; int L=0,R=1000000,mid;ans=0; while(L<=R){ mid=L+R>>1; int res1=query(rt[l-1],rt[r],1,mid+p,1,2000000); int res2=query(rt[l-1],rt[r],1,p-mid-1,1,2000000); if(res1-res2>=k) ans=mid,R=mid-1; else L=mid+1; } cout<<ans<<' '; } } }
线段树的话就要模拟一下归并排序的过程，即线段树结点维护的是区间的有序序列
然后还是二分答案，然后查询的是区间[l,r]范围内在[p-mid,p+mid]范围内的数个数，要特别注意查询的方式
int res1=lower_bound(seg[rt].begin(),seg[rt].end(),v1)-seg[rt].begin(); int res2=upper_bound(seg[rt].begin(),seg[rt].end(),v2)-seg[rt].begin();//上界一定要用upper_bound! return res2-res1;
#include<bits/stdc++.h> #include<vector> using namespace std; #define maxn 100005 int n,k,l,r,ans,p,m,a[maxn]; #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 vector<int>seg[maxn<<2]; void pushup(int rt){ int s=seg[rt<<1].size(),t=seg[rt<<1|1].size(),i=0,j=0; while(i!=s && j!=t){ if(seg[rt<<1][i]<=seg[rt<<1|1][j]) seg[rt].push_back(seg[rt<<1][i]),i++; else seg[rt].push_back(seg[rt<<1|1][j]),j++; } while(i!=s){ seg[rt].push_back(seg[rt<<1][i]); i++; } while(j!=t){ seg[rt].push_back(seg[rt<<1|1][j]); j++; } } void build(int l,int r,int rt){ seg[rt].clear(); if(l==r){ seg[rt].push_back(a[l]);return; } int m=l+r>>1; build(lson);build(rson); pushup(rt); } int query(int L,int R,int v1,int v2,int l,int r,int rt){ if(L<=l && R>=r){ int res1=lower_bound(seg[rt].begin(),seg[rt].end(),v1)-seg[rt].begin(); int res2=upper_bound(seg[rt].begin(),seg[rt].end(),v2)-seg[rt].begin(); return res2-res1; } int m=l+r>>1,res=0; if(L<=m)res+=query(L,R,v1,v2,lson); if(R>m)res+=query(L,R,v1,v2,rson); return res; } int judge(int mid){ int res=0;//查找半径是mid res=query(l,r,p,p+mid,1,n,1); if(res>=k)return 1; res+=query(l,r,p-mid,p-1,1,n,1); if(res>=k)return 1; return 0; } int main(){ int t;cin>>t; while(t--){ n=k=l=r=ans=p=m=0; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++)scanf("%d",&a[i]); build(1,n,1); while(m--){ scanf("%d%d%d%d",&l,&r,&p,&k); l^=ans,r^=ans,p^=ans,k^=ans; int L=0,R=10000000,mid; ans=0; while(L<=R){//二分半径 mid=L+R>>1; if(judge(mid)) ans=mid,R=mid-1; else L=mid+1; } cout<<ans<<' '; } } }