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

Note: if the answer is 0, the answer is - 1

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;}
inline LL read()
{
	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 void add(int x,int d){for(;x<=n;x+=x&-x)c[x]+=d;return;}
	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()
{
	m=n=read();k=read();
	for(register int i=1;i<=n;i++) p[i].r=read(),p[i].id=i;
	for(register int i=1;i<=n;i++) A[i]=p[i].a=read();
	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;
		TA.add(p[i].a,1);
	}
	Q=read();
	for(register int i=1;i<=Q;i++)
	{
		x=zz[read()];y=zz[read()];
		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)
		{
			int val=TA.ask(R[nr])-TA.ask(L[nr]-1);
			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);
		}
		TA.add(p[nl].a,-1);
	}
	for(register int i=1;i<=Q;i++) printf("%d\n",res[i]?res[i]:-1);
}
Published 853 original articles, won praise 104, visited 70000+
His message board follow

Posted on Thu, 16 Jan 2020 03:03:52 -0800 by jamiel