现在有一个(1 imes 2^{31})的网格图，位置编号(0sim 2^{31}-1)，给出n个三元组，第i个三元组用((s_i,t_i,d_i))表示，意义为从位置(s_i)开始，(s_i,s_i+d_i,...,s_i+(k-1)d_ileq e_i)都放上一颗棋子，其中只有最多一个网格中有奇数个棋子，询问这个网格的位置,(nleq 200000)。
解
考虑二分，注意到二分位置的话，不存在单调性，也无法判断是否有更优解，于是考虑二分一段区间，设二分区间为([l,r])，取中间点(mid=l+r>>1)，显然现在划分成两段区间([l,mid];[mid+1,r])，哪一段里的棋子为奇数个，就可以二分下去。
现在关键是如何确定一段区间([l,r])中有的棋子数目，对于一个三元组((s_i,t_i,d_i))而言，显然我们应该取两个区间的交集来计算，记为([L,R]),显然(L=max(l,s_i),R=min(r,t_i))，而三元组的含义，类似剩余类（多个三元组组成一个剩余系，当然不准确，而且也不可能是完全剩余系或者最简剩余系），实际上是循环节(s_i\% d_i+kd_i)在([s_i,t_i])中出现的次数，类比过来，也就是求这个循环节在([L,R])中出现的次数，显然可以拆成求([0,L-1],[0,R])的循环节出现的次数，后者减去前者就是答案了。
以([0,R])出现循环节k次为例，有(s_i\%d_i+(k-1)d_ileq R)，于是我们有(kleq [frac{R-s_i\%d_i+d_i}{d_i}])(一定记住是移完项以后再向下取整，提前向下取整答案是wa的)。
因此就可以再在(nlog(n))处理出答案。
参考代码：
#include <iostream>
#include <cstdio>
#define il inline
#define ri register
#define Size 200500
using namespace std;
int s[Size],e[Size],d[Size],n;
il void read(int&);
il bool check(int,int);
il int min(int,int),max(int,int);
int main(){
int lsy;read(lsy);
while(lsy--){read(n);
for(int i(1);i<=n;++i)
read(s[i]),read(e[i]),read(d[i]);
int l(0),r(1e9),mid,ans(0);
if(check(l,r)){while(l<r){mid=l+r>>1;
if(check(l,mid))r=mid;else l=mid+1;
}for(int i(1);i<=n;++i)
if(s[i]<=l&&l<=e[i]&&l%d[i]==s[i]%d[i])++ans;
printf("%d %d
",l,ans);
}else puts("There's no weakness.");
}
return 0;
}
il int max(int a,int b){
return a>b?a:b;
}
il int min(int a,int b){
return a<b?a:b;
}
il bool check(int l,int r){int ans(0);
for(int i(1),L,R;i<=n;++i){
L=max(l,s[i])-1,R=min(r,e[i]);if(L>=R)continue;
ans+=((R-s[i]%d[i]+d[i])/d[i]-(L-s[i]%d[i]+d[i])/d[i]);
}return ans&1;
}
il void read(int &x){
x^=x;ri char c;while(c=getchar(),c<'0'||c>'9');
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
}