在秦腾进入北京大学学习的第一个学期，就不幸遇到了前所未有的教学评估。

在教学评估期间，同学们被要求八点起床，十一点回宿舍睡觉，不准旷课，上课不准迟到，上课不准睡觉……甚至连著名的北大三角地也在教学评估期间被以影响校容的理由被拆除。这些“变态”规定令习惯了自由自在随性生活学习的北大同学叫苦不迭。

这一天又到了星期五，一大早就是秦腾最不喜欢的高等代数课。可是因为是教学评估时期，不能迟到，于是他在八点五分的 时候挣扎着爬出了宿舍，希望能赶快混进在八点钟已经上课了的教室。

可是，刚一出宿舍楼门他就傻眼了: 从宿舍到教学楼的路上已经站满了教学评估团的成员。他们的目的就是抓住像他这样迟到的学生，扣除学校的分数。

秦腾当然不能让评估团得逞。他经过观察发现，整个评估团分成了N个小组，每个小组的成员都分布在从宿舍楼到教学楼的路上的某一段，并且同一小组的成员间的距离是相等的。于是，我们可以用三个整数 (S,E,D) 来描述评估团的小组: 既该小组的成员在从宿舍到教学楼的路上的：(S, S + D, S + 2D, …, S + KD (K ∈ mathbb{Z}, S + KD ≤ E, S + (K + 1)D > E)) 位置。

观 察到了教学评估团的这一特点，又经过了认真的思考，秦腾想出了对策: 如果在路上的某一位置有奇数个教学评估团成员，他就可以运用调虎离山，声东击西，隔山打牛，暗度陈仓……等方法，以这一地点为突破口到达教学楼。

但是由于 教学评估团的成员的十分狡猾，成员位置安排的设计极其精妙，导致在整条路上几乎没有这样的位置出现。即使由于安排不慎重出现了这样的位置，最多也仅有一个。

现在秦腾观察出了所有小组的安排，但是由于整个教学评估团的人数太多，他实在看不出这样的位置是否存在。

现在，你的任务是写一个程序，帮助他做出判断。

教学评估团的总人数不大于 (10^8)。

(S_i ≤ E_i,1 ≤ T ≤ 5,N ≤ 200000,0 ≤ S_i, E_i, D_i ≤ 2^{31} – 1)。

Solution

注意到题目中的关键信息：

即使由于安排不慎重出现了这样的位置，最多也仅有一个。

这就说明如果用前缀和记录当前位置之前的总人数时，在有奇数的情况下，一定是从那个位置开始之后全是奇数。

想到这里，二分也就应运而生了。

首先先判断是否有解。如果所有位置的总人数是偶数就没有解。

然后二分出奇数所在位置，具体操作可以求出当前位置及之前的人数。

那么 check 函数该怎么写呢？

可以枚举每组评估团，求出该位置之前的这组评估团的人数，求和即可。

bool check(ll x)
{
	int sum=0;
	for (int i=1;i<=n;++i)
	{
		if (x<s[i]) continue;
		sum+=(min(x,e[i])-s[i])/d[i]+1;
	}
	if (sum%2==0) return false;
	else return true;
}

确定好了位置之后，可以 (O(n)) 扫一遍求出人数。

完整Code

#include<cstdio>
#include<algorithm>
#define ll long long
#define N 200005
using namespace std;
int n,t;
ll res,ans,mx,num,l,r,s[N],e[N],d[N];
bool check(ll x)
{
	int sum=0;
	for (int i=1;i<=n;++i)
	{
		if (x<s[i]) continue;
		sum+=(min(x,e[i])-s[i])/d[i]+1;
	}
	if (sum%2==0) return false;
	else return true;
}
int main()
{
	scanf("%d",&t);
	while (t--)
	{
		mx=num=0;
		scanf("%d",&n);
		for (int i=1;i<=n;++i)
		{
			scanf("%lld%lld%lld",&s[i],&e[i],&d[i]);
			num+=(e[i]-s[i])/d[i]+1;mx=max(mx,e[i]);
		}
		if (num%2==0)
		{
			printf("Poor QIN Teng:(
");
			continue;
		}
		res=l=0;r=mx;
		while (l<=r)
		{
			ll mid=(l+r)>>1;
			if (check(mid)) res=mid,r=mid-1;
			else l=mid+1;
		}
		ans=0;
		for (int i=1;i<=n;++i)
		{
			if (res<s[i]||res>e[i]) continue;
			if ((res-s[i])%d[i]==0) ++ans;
		}
		printf("%lld %lld
",res,ans);
	} 
	return 0;
}