题目大意：给你一堆数，每次询问区间[l,r]中离p第k小的|ai-p|
题解：考虑二分答案，对于每个可能的答案，我们只需要看在区间[l,r]里是否有≥k个比二分的答案还要接近于p的
考虑下标线段树，并将其可持久化，线段树i存储1~i中每个数有几个
因为数比较大，考虑离散化，这样最多1e5个数，可以接受
判断时只需要查找第r棵线段树和第l-1棵线段树的区间[l,r]中位于[p-k,p+k]的数有几个然后将返回的值相减看是否≥k即可，注意这里有一些细节
时间复杂度O(mlog^2n)
代码：
#include<iostream> #include<cstdio> #include<cstdlib> #include<algorithm> #include<cmath> #include<cstring> #include<string> using namespace std; int T,n,m,ans; struct node { int v,bh; }a[1000001]; bool cmp(const node &T1,const node &T2){return T1.v<T2.v;} bool cmp2(const node &T1,const node &T2){return T1.bh<T2.bh;} int L[1000001],R[1000001]; int head[1000001],lson[100001*200],rson[100001*200],cnt[100001*200],tn; void insert(int l,int r,int p,int now) { if(l==r && l==p){cnt[now]++;return;} int mid=l+r>>1; if(p<=mid) { tn++; lson[tn]=lson[lson[now]]; rson[tn]=rson[lson[now]]; cnt[tn]=cnt[lson[now]]; lson[now]=tn; insert(l,mid,p,lson[now]); } else { tn++; lson[tn]=lson[rson[now]]; rson[tn]=rson[rson[now]]; cnt[tn]=cnt[rson[now]]; rson[now]=tn; insert(mid+1,r,p,rson[now]); } cnt[now]=cnt[lson[now]]+cnt[rson[now]]; } void init() { tn=0; for(int i=1;i<=n;i++) { head[i]=++tn; lson[head[i]]=lson[head[i-1]]; rson[head[i]]=rson[head[i-1]]; cnt[head[i]]=cnt[head[i-1]]; insert(1,n,L[a[i].v],head[i]); } } int ask(int l,int r,int al,int ar,int now) { if(al>ar) return 0; if(l==al && r==ar)return cnt[now]; int mid=l+r>>1; if(ar<=mid)return ask(l,mid,al,ar,lson[now]); if(al>mid)return ask(mid+1,r,al,ar,rson[now]); return ask(l,mid,al,mid,lson[now])+ask(mid+1,r,mid+1,ar,rson[now]); } int aa,bb,val,k; int main() { scanf("%d",&T); while(T--) { scanf("%d%d",&n,&m); memset(L,0,sizeof(L)); memset(R,0,sizeof(R)); ans=0; for(int i=1;i<=n;i++){scanf("%d",&a[i].v);a[i].bh=i;} sort(a+1,a+1+n,cmp); for(int i=1;i<=n;i++)if(!L[a[i].v])L[a[i].v]=R[a[i].v]=i; for(int i=1;i<=1000000;i++)if(R[i-1]>0 && R[i]==0)R[i]=R[i-1]; for(int i=1000000;i>0;i--)if(L[i+1]>0 && L[i]==0)L[i]=L[i+1]; sort(a+1,a+1+n,cmp2); init(); while(m--) { scanf("%d%d%d%d",&aa,&bb,&val,&k); aa^=ans;bb^=ans;val^=ans;k^=ans; int l=0,r=1000000,mid,tl,tr; while(l<r) { mid=l+r>>1; tl=val-mid;tr=val+mid; tl=max(tl,1);tr=min(tr,1000000); if(R[tr]<L[tl] || R[tr]==0 || L[tl]==0){l=mid+1;continue;} int t1=ask(1,n,L[tl],R[tr],head[bb]),t2=0; if(aa>1)t2=ask(1,n,L[tl],R[tr],head[aa-1]); if(t1-t2<k)l=mid+1; else r=mid; } printf("%d ",r); ans=r; } } return 0; }
心得：考场上很快就想到做法，但是被卡了很久，因为数组没开够。。第一次见到*200的线段树，不知道什么原因开这么大，欠缺思考
实际上*20能过，只不过考场上可能数据出锅或者评测机出锅导致没过，赛后重测过了