GMOJ S3854 【分组】

Description

有 $n$ 个人，第 $i$ 个人有一定的地位 $a_i$ 和年龄 $r_i$ 。
现在要让几个人分成一个小组，小组中必须要有一个队长，要成为队长有这样的条件：

1. 队长在小组中的地位应该是最高的（可以并列第一）；
2. 小组中其他成员的年龄和队长的年龄差距不能超过 $k$ 。

有 $q$ 个询问，第 $i$ 个询问求要同时包含 $x_i$ 和 $y_i$ 的小组最多可以有多少人？

Solution

我们设 $f[i]$ 来表示第 $i$ 个人当队长时最多能够带多少人，这个可以用 离散化 加 线段树 来做，注意要对地位相同的情况进行处理。

然后我们把询问离线来做，用 $ma_i$ 来表示 $\max(r_{x_i}, r_{y_i})$ ，然后以它为关键字来排序，然后开另一棵 线段树 来求出答案即可，注意这里也要对地位相同的情况进行处理。

时间复杂度 $O(n \log n + q \log n)$ ，个人认为这题略显码农。

Code

#include <cstdio>
#define maxN 300010
#define maxM 100010
struct nodea{ int l, r, lc, rc, c; } a[maxN << 2], b[maxN << 2];
struct nodeb{ int a, r, a2, r2, nu, c; } p[maxN];
struct nodec{ int x, y, ma, nu; } q[maxM];
int ans[maxM], wz[maxN], f[maxN];
int t[maxN * 10], t2[maxN * 10];
int len = 0;
int min (int x, int y)
{
	return x < y ? x : y;
}
int max (int x, int y)
{
	return x > y ? x : y;
}
int read ()
{
	int x = 0;
	char c = getchar();
	while(c < '0' || c > '9')
	{
		c = getchar();
	}
	while(c >= '0' && c <= '9')
	{
		x = x * 10 + (c - '0');
		c = getchar();
	}
	return x;
}
void build1 (int l, int r)
{
	len++;
	a[len].l = l;
	a[len].r = r;
	a[len].lc = -1;
	a[len].rc = -1;
	a[len].c = 0;
	int now = len;
	if(l < r)
	{
		int mid = (l + r) / 2;
		a[len].lc = len + 1;
		build1(l, mid);
		a[now].rc = len + 1;
		build1(mid + 1, r);
	}
}
void build2 (int l, int r)
{
	len++;
	b[len].l = l;
	b[len].r = r;
	b[len].lc = -1;
	b[len].rc = -1;
	b[len].c = 0;
	int now = len;
	if(l < r)
	{
		int mid = (l + r) / 2;
		b[len].lc = len + 1;
		build2(l, mid);
		b[now].rc = len + 1;
		build2(mid + 1, r); 
	}
}
void px1 (int l, int r)
{
	int x = l, y = r, mid = t[(l + r) / 2];
	while(x <= y)
	{
		while(t[x] < mid)
		{
			x++;
		}
		while(t[y] > mid)
		{
			y--;
		}
		if(x <= y)
		{
			int tt = t[x];
			t[x] = t[y];
			t[y] = tt;
			x++;
			y--;
		}
	}
	if(l < y)
	{
		px1(l, y);
	}
	if(x < r)
	{
		px1(x, r);
	}
}
void px2 (int l, int r)
{
	int x = l, y = r, mid = p[(l + r) / 2].r;
	while(x <= y)
	{
		while(p[x].r < mid)
		{
			x++;
		}
		while(p[y].r > mid)
		{
			y--;
		}
		if(x <= y)
		{
			nodeb t = p[x];
			p[x] = p[y];
			p[y] = t;
			x++;
			y--;
		}
	}
	if(l < y)
	{
		px2(l, y);
	}
	if(x < r)
	{
		px2(x, r);
	}
}
int find (int x)
{
	int l = 1, r = t2[0];
	while(l < r)
	{
		int mid = (l + r) / 2;
		if(t2[mid] < x)
		{
			l = mid + 1;
		}
		else
		{
			r = mid;
		}
	}
	return l;
}
void change1 (int now, int x, int t)
{
	if(a[now].l == a[now].r)
	{
		a[now].c += t;
		return ;
	}
	int mid = (a[now].l + a[now].r) / 2;
	if(x <= mid)
	{
		change1(a[now].lc, x, t);
	}
	else
	{
		change1(a[now].rc, x, t);
	}
	a[now].c = a[a[now].lc].c + a[a[now].rc].c;
}
int query1 (int now, int l, int r)
{
	if(a[now].l == l && a[now].r == r)
	{
		return a[now].c;
	}
	int mid = (a[now].l + a[now].r) / 2;
	if(r <= mid)
	{
		return query1(a[now].lc, l, r);
	}
	else if(mid + 1 <= l)
	{
		return query1(a[now].rc, l, r);
	}
	else
	{
		return query1(a[now].lc, l, mid) + query1(a[now].rc, mid + 1, r);
	}
}
void px3 (int l, int r)
{
	int x = l, y = r, mid = q[(l + r) / 2].ma;
	while(x <= y)
	{
		while(q[x].ma > mid)
		{
			x++;
		}
		while(q[y].ma < mid)
		{
			y--;
		}
		if(x <= y)
		{
			nodec tt = q[x];
			q[x] = q[y];
			q[y] = tt;
			x++;
			y--;
		}
	}
	if(l < y)
	{
		px3(l, y);
	}
	if(x < r)
	{
		px3(x, r);
	}
}
void px4 (int l, int r)
{
	int x = l, y = r, mid = p[(l + r) / 2].r;
	while(x <= y)
	{
		while(p[x].r > mid)
		{
			x++;
		}
		while(p[y].r < mid)
		{
			y--;
		}
		if(x <= y)
		{
			nodeb tt = p[x];
			p[x] = p[y];
			p[y] = tt;
			x++;
			y--;
		}
	}
	if(l < y)
	{
		px4(l, y);
	}
	if(x < r)
	{
		px4(x, r);
	}
}
void change2 (int now, int x, int t)
{
	if(b[now].l == b[now].r)
	{
		b[now].c = max(b[now].c, t);
		return ;
	}
	int mid = (b[now].l + b[now].r) / 2;
	if(x <= mid)
	{
		change2(b[now].lc, x, t);
	}
	else
	{
		change2(b[now].rc, x, t);
	}
	b[now].c = max(b[b[now].lc].c, b[b[now].rc].c);
}
int query2 (int now, int l, int r)
{
	if(b[now].l == l && b[now].r == r)
	{
		return b[now].c;
	}
	int mid = (b[now].l + b[now].r) / 2;
	if(r <= mid)
	{
		return query2(b[now].lc, l, r);
	}
	else if(mid + 1 <= l)
	{
		return query2(b[now].rc, l, r);
	}
	else
	{
		return max(query2(b[now].lc, l, mid), query2(b[now].rc, mid + 1, r));
	}
}
int main ()
{
	int n = 0, k = 0;
	n = read();
	k = read();
	t[0] = 0;
	for(int i = 1;i <= n; i++)
	{
		p[i].nu = i;
		p[i].r = read();
	}
	for(int i = 1;i <= n; i++)
	{
		p[i].a = read();
		t[++t[0]] = p[i].a;
		t[++t[0]] = p[i].a - k;
		t[++t[0]] = p[i].a + k;
	}
	px1(1, t[0]);
	t2[0] = 0;
	t2[++t2[0]] = t[1];
	for(int i = 2;i <= t[0]; i++)
	{
		if(t[i] != t[i - 1])
		{
			t2[++t2[0]] = t[i];
		}
	}
	for(int i = 1;i <= n; i++)
	{
		p[i].a2 = find(p[i].a);
	}
	px2(1, n);
	build1(1, t2[0]);
	int dq = 0;
	for(int i = 1;i <= n; i++)
	{
		while(p[i].r == p[i + 1].r && i <= n)
		{
			change1(1, p[i].a2, 1);
			i++;
		}
		change1(1, p[i].a2, 1);
		for(int x = dq + 1;x <= i; x++)
		{
			f[p[x].nu] = query1(1, find(p[x].a - k), find(p[x].a + k));
		}
		dq = i;
	}
	int m = 0;
	m = read();
	for(int i = 1;i <= n; i++)
	{
		wz[p[i].nu] = i;
	}
	for(int i = 1;i <= m; i++)
	{
		q[i].nu = i;
		q[i].x = read();
		q[i].y = read();
		if(p[wz[q[i].x]].a > p[wz[q[i].y]].a)
		{
			int tt = q[i].x;
			q[i].x = q[i].y;
			q[i].y = tt;
		}
		q[i].ma = max(p[wz[q[i].x]].r, p[wz[q[i].y]].r);
	}
	for(int i = 1;i <= n; i++)
	{
		p[i].c = f[p[i].nu];
	}
	px3(1, m);
	px4(1, n);
	for(int i = 1;i <= n; i++)
	{
		wz[p[i].nu] = i;
	}
	int Now = 1;
	len = 0;
	build2(1, t2[0]);
	for(int i = 1;i <= n; i++)
	{
		change2(1, p[i].a2, p[i].c);
		while(p[i].r == p[i + 1].r)
		{
			i++;
			change2(1, p[i].a2, p[i].c);
		}
		while(q[Now].ma >= p[i].r && Now <= m)
		{
			int L = p[wz[q[Now].y]].a - k;
			int R = p[wz[q[Now].x]].a + k;
			if(L > R)
			{
				ans[q[Now].nu] = 0;
			}
			else
			{
				ans[q[Now].nu] = query2(1, find(L), find(R));
			}
			Now++;
		}
	}
	for(int i = 1;i <= m; i++)
	{
		printf("%d\n", ans[i] ? ans[i] : -1);
	}
	return 0;
}