# Group (group)

#### DescriptionDescriptionDescription

Define a legal set as: the biggest difference between ageageageage and RankRankRank of all elements in the set is not greater than kkk

Given the RankRankRank and ageageageage of nnn individuals, there are QQ group queries. Each query contains (x,y)(x,y)(x,y) the maximum set size that meets the requirements

Data range: n ≤ 105;k ≤ 109;Age,Rank ≤ 109n\leq 10^5;k\leq 10^9;Age,Rank\leq 10^9n ≤ 105;k ≤ 109;Age,Rank ≤ 109

#### SolutionSolutionSolution

First, find out the maximum set size (tree array) when each person is the oldest. Query is to find the maximum value of a certain age group (line segment tree) in a legal set

The time complexity is O((n+Q)logn)O((n+Q)logn)O((n+Q)logn)

Some pretreatment methods:

First of all, sort the age AAA from large to small. Because we want to use tree array, we need to discretize it
Define the following array:
num[i]num[i]num[i] means the new position of the number with the original position of iii
L[i]L[i]L[i] means the rank of iii (i.e. the position corresponding to a a a after ranking) whose age is at least k k k years younger than it (query the front drive of p[i].a − kp[i].a-kp[i].a − K for the next one)
R[i]R[i]R[i] R [i] indicates that the rank is iii, and the last rank older than it is k k k (query the next one of p[i].a+kp[i].a+kp[i].a+k)

Then we will process the query. Because there are many queries, we have to use the vectorvectorvector, but in this way, the binary is more troublesome, so we can open an auxiliary array to help memory
Then we deal with each person as the team leader, and record it as nlnlnlnlnl. Find out the nrnrnr as large as possible to make the nrnrnr higher than nlnlnlnl. Then we query the nrnrnrnr as the set size of the maximum value by tree array. Because our position is sorted from large to small, we can ensure that the added one can do the maximum value of the following elements, and directly query

#### CodeCodeCode

#include<cctype>
#include<cstdio>
#include<vector>
#include<algorithm>
#define LL long long
#define N 100010
using namespace std;int n,m,k,A[N],Q,x,y,f[N],zz[N],L[N],R[N],res[N],v[N],nl,nr;
struct node{int r,a,id;}p[N];
inline bool cmp(node x,node y){return x.r>y.r;}
{
char c;LL d=1,f=0;
while(c=getchar(),!isdigit(c)) if(c=='-') d=-1;f=(f<<3)+(f<<1)+c-48;
while(c=getchar(),isdigit(c)) f=(f<<3)+(f<<1)+c-48;
return d*f;
}
struct szsz
{
int c[N];
inline int ask(int x){int ans=0;for(;x;x-=x&-x)ans+=c[x];return ans;}
}TA;
struct xds
{
#define lson k<<1
#define rson k<<1|1
int dat[N<<3];
inline void up(int k){dat[k]=max(dat[lson],dat[rson]);return;}
inline int Query(int ql,int qr,int k=1,int l=1,int r=n)
{
if(ql<=l&&r<=qr) return dat[k];
int mid=l+r>>1,Ans=0;
if(ql<=mid) Ans=max(Ans,Query(ql,qr,lson,l,mid));
if(qr>mid) Ans=max(Ans,Query(ql,qr,rson,mid+1,r));
return Ans;
}
inline void Modify(int x,int d,int k=1,int l=1,int r=n)
{
if(l==r) {dat[k]=max(dat[k],d);return;}
int mid=l+r>>1;
if(x<=mid) Modify(x,d,lson,l,mid);else Modify(x,d,rson,mid+1,r);
up(k);
return;
}
#undef lson
#undef rson
}T;
vector<int>q[N];
signed main()
{
sort(A+1,A+1+m);m=unique(A+1,A+1+m)-A-1;
sort(p+1,p+1+n,cmp);
for(register int i=1;i<=n;i++)
{
zz[p[i].id]=i;
L[i]=lower_bound(A+1,A+1+m,p[i].a-k)-A;
R[i]=upper_bound(A+1,A+1+m,p[i].a+k)-A-1;
p[i].a=lower_bound(A+1,A+1+m,p[i].a)-A;
}
for(register int i=1;i<=Q;i++)
{
if(x<y) swap(x,y);
q[y].push_back(i);
v[i]=x;
}
for(nl=nr=1;nl<=n;nl++)
{
while(nr<=n&&p[nr].r>=p[nl].r)
{
T.Modify(p[nr++].a,val);
}
for(register int j=0;j<q[nl].size();j++)
{
int i=q[nl][j],x=v[i],y=nl;
int ql=max(L[x],L[y]),qr=min(R[x],R[y]);
if(ql>qr) res[i]=-1;
else res[i]=T.Query(ql,qr);
}