727よりこちらの方が考察はラクだった。
https://yukicoder.me/problems/no/728
問題
N個の家があり、1次元の数直線上A[i]に配置されている。
A[i]の住人は、[A[i]-L[i],A[i]+R[i]]の範囲にある家にお菓子を配る。
互いにお菓子を配りあう住人の対は何通りか。
解法
X座標の小さい順に考えてみる。
A[i]の住人は、右側A[i]+R[i]までにある住人にお菓子を配る。
その際、その区間にある家A[j]において、A[j]-L[j]≦A[i]ならA[i]とA[j]の住人は互いにお菓子を配りあう。
これを平面(直線?)走査の要領で、X座標の小さい順に見ていくことで解く。
まず、BITを準備しておく。今見ている座標が[A[i],A[i]+R[i]]の区間の場合、BITのi番目の要素は1となる。
走査の位置Xが
- A[i]に到達した場合
- A[k]<A[i]となる条件を満たす(k,i)の対を数え上げたい。そこでlower_boundなどでA[i]-L[i]≦A[k]となる最小のkを求めよう。
- その後、BITを用いてk~(i-1)番の家のうち有効なものを数え上げる。
- その後、BITでi番目を1にする。
- A[k]<A[i]となる条件を満たす(k,i)の対を数え上げたい。そこでlower_boundなどでA[i]-L[i]≦A[k]となる最小のkを求めよう。
- A[i]+R[i]に到達した場合
- 以後の家は、A[i]の住人のお菓子が届かないので、BITでi番目を0にする。
template<class V, int ME> class BIT { public: V bit[1<<ME]; V operator()(int e) {if(e<0) return 0;V s=0;e++;while(e) s+=bit[e-1],e-=e&-e; return s;} void add(int e,V v) { e++; while(e<=1<<ME) bit[e-1]+=v,e+=e&-e;} }; BIT<int,20> bt; int N; int A[301010]; int L[303030]; int R[303030]; vector<pair<int,int>> E; void solve() { int i,j,k,l,r,x,y; string s; cin>>N; FOR(i,N) cin>>A[i]; FOR(i,N) { cin>>L[i]>>R[i]; E.push_back({A[i],i}); E.push_back({A[i]+R[i],N+i}); } ll ret=0; sort(ALL(E)); FORR(e,E) { x=e.second%N; if(e.second<N) { x=e.second; y=lower_bound(A,A+N,A[x]-L[x])-A; ret+=bt(x)-bt(y-1); bt.add(x,1); } else { bt.add(x,-1); } } cout<<ret<<endl; }
まとめ
片方がお菓子配りに来たときにその場でお返しすれば、片方だけ配ることはないのにね。