yukicoder : No.728 ギブ and テイク

727よりこちらの方が考察はラクだった。
https://yukicoder.me/problems/no/728

問題

N個の家があり、１次元の数直線上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[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;
	
}

まとめ

片方がお菓子配りに来たときにその場でお返しすれば、片方だけ配ることはないのにね。