acw 120. 防线()

给一些区间【l , r】 , 区间i 内间隔 d[i] 有一个点（可能会重复），保证最后只有一个位置的点数为奇数，其他位置的点数为偶数

找出这个点

二分查找

二分点的位置，注意题目中唯一的奇数点

求区间和，判断奇偶性，缩小范围

#include "bits/stdc++.h"
using namespace std;
 const int N=2e5+5;
 struct T{
     int l,r,d;
 };
 T a[N];
 int n;
 int sum(int p){
     int i,t=0;
     for(i=1;i<=n;i++){
         if(a[i].l<=p)
         t+=(min(a[i].r,p)-a[i].l)/a[i].d+1;
     }
     return t;
 }
 int rs(int l,int r){
     return sum(r)-sum(l-1);
 }
 void sov(){
     cin>>n;
     int i,l=0,r=0,ans;
     for(i=1;i<=n;i++) 
     cin>>a[i].l>>a[i].r>>a[i].d,r=max(r,a[i].r);
     if(sum(r)%2==0){
         cout<<"There's no weakness.\n";return;
     }
     while(l<=r){
         int md=(l+r)/2;
         if(rs(l,md)%2) ans=md,r=md-1; else l=md+1;  
     }
     cout<<ans<<' '<<sum(ans)-sum(ans-1)<<'\n';
 }
 int main(){
     int tes;
      cin>>tes; while(tes--) sov();
 }
————————

给一些区间【l , r】 , 区间i 内间隔 d[i] 有一个点（可能会重复），保证最后只有一个位置的点数为奇数，其他位置的点数为偶数

找出这个点

二分查找

二分点的位置，注意题目中唯一的奇数点

求区间和，判断奇偶性，缩小范围

#include "bits/stdc++.h"
using namespace std;
 const int N=2e5+5;
 struct T{
     int l,r,d;
 };
 T a[N];
 int n;
 int sum(int p){
     int i,t=0;
     for(i=1;i<=n;i++){
         if(a[i].l<=p)
         t+=(min(a[i].r,p)-a[i].l)/a[i].d+1;
     }
     return t;
 }
 int rs(int l,int r){
     return sum(r)-sum(l-1);
 }
 void sov(){
     cin>>n;
     int i,l=0,r=0,ans;
     for(i=1;i<=n;i++) 
     cin>>a[i].l>>a[i].r>>a[i].d,r=max(r,a[i].r);
     if(sum(r)%2==0){
         cout<<"There's no weakness.\n";return;
     }
     while(l<=r){
         int md=(l+r)/2;
         if(rs(l,md)%2) ans=md,r=md-1; else l=md+1;  
     }
     cout<<ans<<' '<<sum(ans)-sum(ans-1)<<'\n';
 }
 int main(){
     int tes;
      cin>>tes; while(tes--) sov();
 }