题目大意
给出一条防线上的防具布置情况，求防线的第一个破绽位置与该位置上的防具数量。
题目分析
记\(S(x)\)表示\(0~x\)的位置上一共有多少防具，对于每组防具，如果\(s_i\)在x之前，那么就把\(min(x,d_i)\)之前的防具累加，一直累加到n求出\(S(i)\),时间复杂度为\(O(n)\)。
特判：若\(S(2^{31}-1)\)为偶数，则整道防线没有破绽。
设破绽的位置为\(P\)，故只有\(P\)上有奇数个防具，其他位置上都有偶数个防具，则对于所有的\(x<P\)，\(S(x)\)均为偶数，对于所有的\(x>=P\)，\(S(x)\)均为奇数。
考虑二分答案，若\(S(mid)\)为奇数，则答案必定在\(mid\)或者\(mid\)之前，即令\(r=mid\);若\(S(mid)\)为偶数，则答案必定在\(mid\)之后，即令\(l=mid+1\)。
时间复杂度为\(O(32n)\)。
Code
#include<iostream>
#include<cstdio>
#define inf 2147483647
#define sco 200010
using namespace std;
int T,n,s[sco],e[sco],d[sco],v[sco],f[sco];
int S(int x){
int ans=0;
for(int i=1;i<=n;++i){
if(s[i]<=x) ans+=(min(x,e[i])-s[i])/d[i]+1;
}
return ans;
}
int main(){
scanf("%d",&T);
while(T--){
scanf("%d",&n);
for(int i=1;i<=n;++i){
scanf("%d%d%d",&s[i],&e[i],&d[i]);
}
if(S(2147483647)%2==0){printf("There‘s no weakness.\n");continue;}
int l=1,r=2147483647,mid;
while(l<r){
mid=(1ll*l+1ll*r)>>1;
if(S(mid)&1)r=mid;else l=mid+1;
}
printf("%d %d\n",l,S(l)-S(l-1));
}
return 0;
}