【题解】LuoGu4403：[BJWC2008]秦腾与教学评估

原题传送门
小思维难度
核心思想：奇偶性
注意到要么无解，要么有且仅有一解（人数为奇）
想到二分
用一个$calc(i)$函数计算“前缀和”，就是点1到点i人数之和，可以$O(n)$得到
然后就是针对这个前缀和的分类讨论

• $calc(maxr)$ $mod$ $2==0$，无解
• $calc(mid)$ $mod$ $2==0$，答案在$[mid+1,r]中$，所以$l=mid+1$
• $calc(mid)$ $mod$ $2==1$，答案在$[l,mid]中$，所以$r=mid$

最终的答案即为$l$，至于$l$上的人数，为$calc(l)-calc(l-1)$

Code:

#include <bits/stdc++.h>
#define maxn 200010
#define inf 2147483647
#define LL long long
using namespace std;
LL n, s[maxn], e[maxn], d[maxn];

inline LL read(){
	LL s = 0, w = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') w = -1;
	for (; isdigit(c); c = getchar()) s = (s << 1) + (s << 3) + (c ^ 48);
	return s * w;
}

LL calc(LL x){
	LL sum = 0;
	for (int i = 1; i <= n; ++i)
		if (s[i] <= x) sum += (min(e[i], x) - s[i]) / d[i] + 1;
	return sum;
}

int main(){
	int M = read();
	while (M--){
		n = read();
		LL l = inf, r = -inf;
		for (int i = 1; i <= n; ++i){
			s[i] = read(), e[i] = read(), d[i] = read();
			l = min(l, s[i]), r = max(r, e[i]);
		}
		if (calc(r) % 2 == 0){
			printf("Poor QIN Teng:(\n");
			continue;
		}
		while (l < r){
			LL mid = (l + r) >> 1;
			if (calc(mid) & 1) r = mid; else l = mid + 1;
		}
		printf("%lld %lld\n", l, calc(l) - calc(l - 1));
	}
	return 0;
}