时间限制: 1000 ms 内存限制: 262144 KB
【题目描述】
社区有n个居民，每个居民有一定的地位和年龄，ri表示第i个人的地位，ai表示第i个人的年龄。
最近社区里要举行活动，要求几个人分成一个小组，小组中必须要有一个队长，要成为队长要满足以下条件：
①、队长在小组中的地位应该是最高的（可以并列第一）；
②、小组中其他成员的年龄和队长的年龄差距不能超过K。
有些人想和自己亲密的人组在同一个小组，同时希望所在的小组人越多越好。
比如x和y想在同一个小组，同时希望他们所在的小组人越多越好当然。
它们也必须选一个符合上述条件的队长，那么问你，要同时包含x和y的小组，最多可以组多少人？
【输入】
第一行两个整数n和K。
接下来一行输入n个整数：r1,r2,…,rn。
接下来一行输入n个整数：a1,a2,…,an。
接下来输入Q表示有Q个询问。
接下来Q行每行输入x,y，表示询问：当x和y组在同一个小组，它们小组最多可以有多少人（x和y也有可能被选为队长，只要它们符合条件）。
【输出】
对于每个询问，输出相应的答案，每个答案占一行。
当x
和y无法在同一组时，输出-1（比如x的年龄是1， y的年龄是100，K=1，无论谁当队长，x和y两者中，总会有人跟队长的年龄差距超过K，那么输出-1）。
【输入样例】
5 1
1 5 4 1 2
4 4 3 2 2
4
5 3
2 3
2 5
4 1
【输出样例】
4
3
-1
4
【提示】
【样例解释】
询问1：当第5个人和第3个人想在一组时，小组成员可以有{1，3，4，5}，选择3当队长，而2不可以加入，因为2加入的话，5和2的年龄差距为2，超过K=1了。
询问2：当第2个人和第3个人想在一组时，可以选择{1，2，3}。
询问3：当2和5想在一起时，无法满足要求。
询问4：当4和1想在一起时，可以选择{1，3，4，5}。
【数据规模】
对于20%的数据：2≤n≤100，0≤k≤100，1≤ri,ai≤100，1≤q≤100。
对于40%的数据：2≤n≤1000，0≤k≤1000，1≤ri,ai≤1000，1≤q≤1000。
对于60%的数据：2≤n≤\(10^{4}\)，0≤k≤\(10^{9}\)，1≤ri,ai≤\(10^{9}\),1≤q≤\(10^{4}\)。
对于100%的数据：2≤n≤\(10^{5}\)，0≤k≤\(10^{9}\)，1≤ri,ai≤\(10^{9}\)，1≤q≤\(10^{5}\)，1≤x,y≤n,x≠y。
【题解】
询问次数多则肯定要预处理出每个人当领导时可以带多少人，再在可以选择的领导中取人数最大值。
可以将询问离线，按询问中两个人地位的最大值降序排序，则每次查询前将所有地位大于这个最大值的人的可取人数安年龄压入线段树，每次查询年龄段即可。
考虑如何预处理每个人可以带多少人，将每个人按地位升序排序，则在他及他之前的人在年龄范围内都可以被带。
每扫到一个人，先把他和和他地位相同的人全部压入线段树中，再查询年龄区间内人数。
代码如下：
#include<bits/stdc++.h> #define int long long using namespace std; const int N=4e5+5; map <int,int> dui; int n,k,cnt,q,sh[N<<2],mx[N<<2],cou[N]; struct lisan { int zhi,id; }ls[N<<2]; struct people { int r,a,id,dair; }p[N]; struct xunwen { int x,y,id,di,xs,ys; }wen[N]; inline bool cmp(lisan x,lisan y) { return x.zhi<y.zhi; } inline int read() { char c=getchar(); int x=0; while(!isdigit(c)) c=getchar(); while(isdigit(c)) {x=(x<<3)+(x<<1)+c-‘0‘;c=getchar();} return x; } //-------------树状数组---------------------// inline int lowbit(int x) { return x& (-x); } inline void update(int x,int val) { for(int i=x;i<=cnt;i+=lowbit(i)) sh[i]+=val; } inline int query(int x) { int daan=0; if(x<=0) return 0; for(int i=x;i;i-=lowbit(i)) daan+=sh[i]; return daan; } //----------------------------------// inline void lisanlisan() { sort(ls+1,ls+3*n+1,cmp); dui[ls[1].zhi]=++cnt; if(ls[1].id) p[ls[1].id].a=ls[1].zhi; for(int i=2;i<=n*3;i++) { if(ls[i].zhi!=ls[i-1].zhi) dui[ls[i].zhi]=++cnt; if(ls[i].id) p[ls[i].id].a=ls[i].zhi; } } inline bool cmp1(people x,people y) { return x.r<y.r; } inline void get_meiren() { sort(p+1,p+n+1,cmp1); int pre=1; for(int i=2;i<=n+1;i++) { if(p[i].r!=p[i-1].r) { for(int j=pre;j<=i-1;j++) update(dui[p[j].a],1); for(int j=pre;j<=i-1;j++) p[j].dair=query(dui[p[j].a+k])-query(dui[p[j].a-k]-1); pre=i; } } } inline bool cmp2(xunwen x,xunwen y) { return x.di>y.di; } inline void modify(int now,int l,int r,int x,int zhi) { if(l==r) { mx[now]=max(mx[now],zhi); return; } int mid=(l+r)>>1; if(x<=mid) modify(now<<1,l,mid,x,zhi); else modify(now<<1|1,mid+1,r,x,zhi); mx[now]=max(mx[now<<1],mx[now<<1|1]); } inline int cha(int now,int l,int r,int L,int R) { if(L>R) return 0; if(l>=L&&r<=R) return mx[now]; int mid=(l+r)>>1,daan=0; if(L<=mid) daan=cha(now<<1,l,mid,L,R); if(R>=mid+1) daan=max(daan,cha(now<<1|1,mid+1,r,L,R)); return daan; } inline void solve() { int dao=n; sort(wen+1,wen+q+1,cmp2); for(int i=1;i<=q;i++) { while(dao&&p[dao].r>=wen[i].di) { modify(1,1,cnt,dui[p[dao].a],p[dao].dair); dao--; } int ans=cha(1,1,cnt,dui[max((int)0,max(wen[i].xs,wen[i].ys)-k)],dui[min(wen[i].xs,wen[i].ys)+k]); if(ans==0) cou[wen[i].id]=-1; else cou[wen[i].id]=ans; } } signed main() { n=read();k=read(); for(int i=1;i<=n;i++) p[i].r=read(),p[i].id=i; for(int i=1;i<=n;i++) ls[i].zhi=read(),ls[i].id=i,ls[i+n].zhi=ls[i].zhi+k,ls[i+n+n].zhi=max((int)0,ls[i].zhi-k); lisanlisan(); q=read(); for(int i=1;i<=q;i++) wen[i].id=i,wen[i].x=read(),wen[i].y=read(),wen[i].di=max(p[wen[i].x].r,p[wen[i].y].r),wen[i].xs=p[wen[i].x].a,wen[i].ys=p[wen[i].y].a; get_meiren(); solve(); for(int i=1;i<=q;i++) cout<<cou[i]<<"\n"; return 0; }
原文：https://www.cnblogs.com/betablewaloot/p/12173897.html
