Description：

给出 $n$ 个竖直的区间，求只经过整点的经过每个区间的直线个数。

$1\leqslant n\leqslant 10^5$

Solution：

其实就是求第 $i$ 项 $\in[l_i,r_i]$ 的个数，正解是会发现这个等价于 $l_i\leqslant a_1+ib\leqslant r_i$ ，于是先做半平面交，然后统计一下半平面交内整点个数，会发现这题斜率都是整数所以可以直接统计。

我的考场做法是先写一个暴力枚举一下斜率，然后把每个区间上移那么多，然后看区间交的大小，然后会发现有解的一定是一段区间，那么我们可以先随便找一个解然后左右二分出有解的范围，这样我们就可以把上边界和下边界分开统计，然后会发现每个位置对答案的贡献是一个关于公差的一次函数，那么我们就上下分别维护一个凸壳，凸壳上的边都是对答案有贡献的，然后统计凸壳每个直线有贡献的区间下方的整点个数即可。

代码是考场代码。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n;

typedef long long ll;

#define MAXN 200010

ll L[MAXN],R[MAXN];

ll ava,maxk,mink;

#define INF 0x3f3f3f3f

ll calc(ll k)

{

	ll l = L[1] - k,r = R[1] - k;

	for(int i = 1;i <= n;++i)

	{

		r = min(r,R[i] - k * i);

		l = max(l,L[i] - k * i);

	}

	return r - l + 1;

}

int stack[MAXN],top = 0;

struct line

{

	double k,b;

}e[MAXN];

double intersectionx(line a,line b)

{

	return (b.b - a.b) / (a.k - b.k);

}

int main()

{

	scanf("%d",&n);

	for(int i = 1;i <= n;++i)

	{

		scanf("%lld%lld",&L[i],&R[i]);

	}

	ll l = -INF,r = INF,mid;

	ava = -INF;

	while(l < r)

	{

		mid = ((l + r) >> 1);

		ll val = calc(mid);

		if(val >= 0){ava = mid;break;}

		if(calc(mid + 1) >= val)l = mid + 1;

		else r = mid;

	}

	if(ava == -INF)

	{

		puts("0");

		return 0;

	}

	l = -INF;r = ava;

	while(l < r)

	{

		mid = ((l + r) >> 1);

		if(calc(mid) > 0)r = mid;

		else l = mid + 1;

	}

	mink = l;

	l = ava;r = INF;

	while(l < r)

	{

		mid = ((l + r + 1) >> 1);

		if(calc(mid) > 0)l = mid;

		else r = mid - 1;

	}

	maxk = r;

	ll ans = maxk - mink + 1;

	for(int i = 1;i <= n;++i)

	{

		e[i].k = -i;

		e[i].b = R[i];

	}

	for(int i = 1;i <= n;++i)

	{

		while(top >= 2 && intersectionx(e[stack[top]],e[stack[top - 1]]) >= intersectionx(e[stack[top]],e[i]))--top;

		stack[++top] = i;

	}

	while(top >= 2 && intersectionx(e[stack[top - 1]],e[stack[top]]) >= maxk)--top;

	l = mink;

	for(int i = 1;i < top;++i)

	{

		double x = intersectionx(e[stack[i]],e[stack[i + 1]]);

		if(l <= floor(x))

		{

			r = floor(x);

			int p = stack[i];

			ans += 1ll * (R[p] - l * p + R[p] - r * p) * (r - l + 1) / 2;

		}

		l = max((long long)ceil(x),l);

		if(l == r)++l;

	}

	if(l <= maxk)

	{

		r = maxk;

		int p = stack[top];

		ans += 1ll * (R[p] - l * p + R[p] - r * p) * (r - l + 1) / 2;

	}

	top = 0;

	for(int i = 1;i <= n;++i)

	{

		e[n - i + 1].k = -i;

		e[n - i + 1].b = L[i];

	}

	for(int i = 1;i <= n;++i)

	{

		while(top >= 2 && intersectionx(e[stack[top]],e[stack[top - 1]]) >= intersectionx(e[stack[top]],e[i]))--top;

		stack[++top] = i;

	}

	while(top >= 2 && intersectionx(e[stack[top - 1]],e[stack[top]]) >= maxk)--top;

	l = mink;

	for(int i = 1;i < top;++i)

	{

		double x = intersectionx(e[stack[i]],e[stack[i + 1]]);

		if(l <= floor(x))

		{

			r = floor(x);

			int p = n - stack[i] + 1;

			ans -= 1ll * (L[p] - l * p + L[p] - r * p) * (r - l + 1) / 2;

		}

		l = max((long long)ceil(x),l);

		if(l == r)++l;

	}

	if(l <= maxk)

	{

		r = maxk;

		int p = n - stack[top] + 1;

		ans -= 1ll * (L[p] - l * p + L[p] - r * p) * (r - l + 1) / 2;

	}

	cout << ans << endl;

	return 0;

}