ABC 360

D. Ghost Ants

        把向左走和向右走的蚂蚁分别存进两个数组并排序，对于两者都要枚举的情况，思路是只枚举一个，那枚举的这个就是一个固定值，问题就转化成如何快速找到另一个变量符合条件的值。

        假设枚举向左走的蚂蚁，对第 i 个向左走的蚂蚁，在向右走的蚂蚁中求出坐标大于等于 a [ i ] - 2 * t 的蚂蚁数量。两次二分就可以，第一次用 lower 找到最左边的，第二次用 upper 找到最右边的下一个。

        不管是 lower 还是 upper 都有可能返回 end ()

        · lower 返回 end ()，那 upper 也一定返回 end ()，所以 r - l 为 0，不用特判

        · upper 返回 end ()，因为 end () 本身就是最后一个元素的下一个元素，指向的就是空节点，不会产生影响，所以也不用特判

        因此不管返回的是不是 end ()，都是直接 r - l

        这里不用管 end () 是因为我只是在求符合条件的个数，而不是能不能查找到，是否存在。如果是要找具体的某一只蚂蚁那就得去特判是否返回的是 end ()

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 5, INF = 1e18;int T, n, t, cnt, ans;
string s;
vector<int> v0, v1; signed main()
{cin >> n >> t >> s;for (int i = 0; i < n; i ++){int x;cin >> x;if (s[i] == '0')	v0.push_back(x);else	v1.push_back(x);}sort(v0.begin(), v0.end());sort(v1.begin(), v1.end());int d = t * 2, cnt0 = v0.size(), cnt1 = v1.size();for (int i = 0; i < cnt0; i ++){auto l = lower_bound(v1.begin(), v1.end(), v0[i] - d);auto r = upper_bound(v1.begin(), v1.end(), v0[i]);ans += r - l;}cout << ans;return 0;
}