GMOJ S3804 【小 X 的 AK 计划】

Description

给你 $n$ 个点的坐标 $x_1$ ~ $x_n$ ，有一个人在 0 时刻站在 0 位置，它的速度为 1 ，每到一个点，他可以花 $t_i$ 的时间 AK ，获得 $1$ 的价值，求他在 $m$ 时刻能够得到的最大价值。

$$1 \leq n \leq 10 ^ 5, 1 \leq m;x_i \leq 10 ^ {18}, 0 \leq t_i \leq 10 ^ 9$$

Solution

我们不难发现我们不会走回头路，因此我们可以在确定最后一次 AK 所在的位置的情况下，得出他在 AK 上能够花的最大时间。

设这个位置的坐标为 $X$ ，那么问题就转化为了在所有的 $x_i \leq X$ 中，选出一些 $t_i$ ，使得他们的和不超过 $(m - X)$ ，求最多能够选多少个数。

显然我们只会选最小的。

因此我们可以想到用 线段树 来进行维护，维护两个东西，在 $t_i \in [l, r]$ 中， $\sum t_i$ 和 $(t_i \in [l, r])$ （即有多少个不同的 $i$ 使得 $t_i \in [l, r]$ ）的值。

因为我们发现 $t_i$ 很大，所以我们要对 $t_i$ 进行 离散化 。

当我们对 $x_i$ 按升序排序后，对于转换后的问题，我们可以二分答案。

至此，我们便得到了一个时间复杂度为 $O(n \log ^ 2 n)$ 的算法。

Code

#include <cstdio>
#define maxN 100010
struct nodea{ long long l, r, lc, rc, c, c2; } a[maxN << 2];
struct nodeb{ long long x, t; } b[maxN];
long long lenc = 0, lend = 0, len = 0;
long long c[maxN], d[maxN];
long long max (long long x, long long y)
{
	return x > y ? x : y;
}
void px1 (long long l, long long r)
{
	long long x = l, y = r, mid = c[(l + r) / 2];
	while(x <= y)
	{
		while(c[x] < mid)
		{
			x++;
		}
		while(c[y] > mid)
		{
			y--;
		}
		if(x <= y)
		{
			long long t = c[x];
			c[x] = c[y];
			c[y] = t;
			x++;
			y--; 
		}
	}
	if(l < y)
	{
		px1(l, y);
	}
	if(x < r)
	{
		px1(x, r);
	}
}
void px2 (long long l, long long r)
{
	long long x = l, y = r, mid = b[(l + r) / 2].x;
	while(x <= y)
	{
		while(b[x].x < mid)
		{
			x++;
		}
		while(b[y].x > mid)
		{
			y--;
		}
		if(x <= y)
		{
			nodeb t = b[x];
			b[x] = b[y];
			b[y] = t;
			x++;
			y--;
		}
	}
	if(l < y)
	{
		px2(l, y);
	}
	if(x < r)
	{
		px2(x, r);
	}
}
long long find (long long x)
{
	long long l = 1, r = lend;
	while(l < r)
	{
		long long mid = (l + r) / 2;
		if(d[mid] < x)
		{
			l = mid + 1;
		}
		else
		{
			r = mid;
		}
	}
	return l;
}
void build (long long l, long long r)
{
	len++;
	a[len].l = l;
	a[len].r = r;
	a[len].lc = -1;
	a[len].rc = -1;
	a[len].c = 0;
	a[len].c2 = 0;
	long long now = len;
	if(l < r)
	{
		long long mid = (l + r) / 2;
		a[len].lc = len + 1;
		build(l, mid);
		a[now].rc = len + 1;
		build(mid + 1, r);
	}
}
void change (long long now, long long x, long long t)
{
	if(a[now].l == a[now].r)
	{
		a[now].c += t;
		a[now].c2++;
		return ;
	}
	long long mid = (a[now].l + a[now].r) / 2;
	if(x <= mid)
	{
		change(a[now].lc, x, t);
	}
	else
	{
		change(a[now].rc, x, t);
	}
	a[now].c = a[a[now].lc].c + a[a[now].rc].c;
	a[now].c2 = a[a[now].lc].c2 + a[a[now].rc].c2;
}
long long queryc (long long now, long long l, long long r)
{
	if(a[now].l == l && a[now].r == r)
	{
		return a[now].c;
	}
	long long mid = (a[now].l + a[now].r) / 2;
	if(r <= mid)
	{
		return queryc(a[now].lc, l, r);
	}
	else if(mid + 1 <= l)
	{
		return queryc(a[now].rc, l, r);
	}
	else
	{
		return queryc(a[now].lc, l, mid) + queryc(a[now].rc, mid + 1, r);
	}
}
long long queryc2 (long long now, long long l, long long r)
{
	if(a[now].l == l && a[now].r == r)
	{
		return a[now].c2;
	}
	long long mid = (a[now].l + a[now].r) / 2;
	if(r <= mid)
	{
		return queryc2(a[now].lc, l, r);
	}
	else if(mid + 1 <= l)
	{
		return queryc2(a[now].rc, l, r);
	}
	else
	{
		return queryc2(a[now].lc, l, mid) + queryc2(a[now].rc, mid + 1, r);
	}
}
int main ()
{
	long long n = 0, m = 0;
	scanf("%lld %lld", &n, &m);
	for(long long i = 1;i <= n; i++)
	{
		scanf("%lld %lld", &b[i].x, &b[i].t);
		c[++lenc] = b[i].t + 1;
	}
	px1(1, lenc);
	for(long long i = 1;i <= lenc; i++)
	{
		if(c[i] != c[i - 1])
		{
			d[++lend] = c[i];
		}
	}
	px2(1, n);
	for(long long i = 1;i <= n; i++)
	{
		b[i].t = find(b[i].t);
	}
	build(1, lend);
	long long ans = 0;
	for(long long i = 1;i <= n; i++)
	{
		change(1, b[i].t, d[b[i].t] - 1);
		long long m2 = m - b[i].x;
		long long l = 1, r = lend;
		while(l < r)
		{
			long long mid = (l + r + 1) / 2;
			if(queryc(1, 1, mid) <= m2)
			{
				l = mid;
			}
			else
			{
				r = mid - 1;
			}
		}
		ans = max(ans, queryc2(1, 1, l));
	}
	printf("%lld", ans);
	return 0;
}