设 $op_i=0/1$ 的点为白/黑点，对黑点做 dp。

设 $dp_i$ 表示选了点 $i$ 的方案数，转移形如 $dp_i=\sum_{j<i} dp_j\times 2^{cnt_j}$，其中 $cnt_j$ 表示 $j\sim i$ 间与 $j$ 距离不超过 $D$ 的白点数。

从小到大加入点，那么一个白点能造成贡献的黑点是一段区间，可以用双指针维护出。那么转移就是区间乘二，单点修改，全局求和。

不过直接上线段树也太蠢了，不难发现都能双指针维护。时间复杂度 $\mathcal{O}(n)$。

#include <bits/stdc++.h>

using namespace std;

// using ikaleio fastIO.

typedef long long ll;

const int MAXN = 1e6 + 10;
const int mod = 1e9 + 7;

inline int add(int x, int y) { return x += y, x < mod ? x : x - mod; }
inline void cadd(int &x, int y) { x += y, x < mod || (x -= mod); }
inline void csub(int &x, int y) { x -= y, x < 0 && (x += mod); }

int n, m, p2[MAXN], sum, ans;

int p[MAXN], w[MAXN], t[MAXN], dp[MAXN];

int main() {
	io.read(n, m), *p2 = 1;
	for (int i = 1; i <= n; i++) p2[i] = add(p2[i - 1], p2[i - 1]);
	for (int i = 1; i <= n; i++) io.read(p[i], w[i]);
	for (int i = 1, j = 1, k = 0; i <= n; i++) {
		if (w[i]) dp[i] = ans + 1, cadd(ans, dp[i]), cadd(sum, dp[i]);
		else {
			for (; p[j] + m < p[i]; csub(sum, (ll)dp[j] * p2[k] % mod), k -= t[++j]);
			cadd(ans, sum), cadd(sum, sum), k++, t[i + 1]++;
		}
	}
	io.write(ans);
}

令 $dp_i$ 表示只考虑前 $i$ 个牛且选了第 $i$ 头牛的合法方案数。

若 $o_i=1$，则上一头牛任选（是教练和营员都可以），此时 $dp_i=\displaystyle\sum_{j<i} dp_j$。

若 $o_i=0$，发现上一头牛是营员就不好转移了（因为不知道上一个教练的位置），所以钦定上一头牛是教练来转移。这样转移，需要考虑上一头教练牛 $j$ 和当前牛 $i$ 中间的这段营员牛就是任选的，假设 $j$ 和 $i$ 中间的营员牛有 $x$ 头，则转移是 $dp_i=\displaystyle\sum_{p_i-p_j\le d\ \land\ o_j=1}2^xdp_j$。

为优化 $o_i=0$ 转移的时间复杂度，我们开一颗支持区间加、区间乘的线段树，存储所有教练牛的当前 $2^xdp_j$ 值（不存营员牛的）。每次处理到 $o_i=1$ 的教练牛时将 $dp_i$ 加入到线段树 $i$ 处；处理到 $o_i=0$ 的营员牛时将前缀 $[1,i]$ 全部乘以二。这样就可以实现对于当前 $i$，线段树的 $j$ 处维护的就是转移式中需要的 $2^x dp_j$。

核心代码：

ll L = 1, sumall = 1;
rep(i, 1, n) {
	if (o[i] == 1) {
		dp[i] = sumall;
		modify(1, i, i, 1, dp[i]);
	}
	else {
		while (L < i && !(o[L] == 1 && p[i] - p[L] <= d))    L++;
		if (L != i) {
			dp[i] = query(1, L, i);
		}
		modify(1, 1, i, 2, 0);
	}
	sumall = (sumall + dp[i]) % mod;
}

之中 $L$ 是满足 $p_i-p_L\le d$ 的教练牛中最靠左的那一头的下标。

完整赛时代码：

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<=(n);i++)
#define per(i,a,n) for(int i=(n);i>=(a);i--)
#define pb push_back
#define SZ(v) ((int)v.size())
#define fs first
#define sc second
#define all(x) (x.begin()),(x.end())
typedef long long ll;
typedef double db;
typedef pair<int, int> pii;
const ll mod = 1e9 + 7;
const int N = 1e6 + 5;
struct Node {
	int l, r;
	ll sum, add, mul;
}tr[N << 2];
void pushup(int u) {
	tr[u].sum = (tr[u * 2].sum + tr[u * 2 + 1].sum) % mod;
}
void maketag(int u, ll famul, ll faadd) {
	tr[u].sum = (tr[u].sum * famul + faadd * (tr[u].r - tr[u].l + 1)) % mod;
	tr[u].add = (famul * tr[u].add + faadd) % mod;
	tr[u].mul = (tr[u].mul * famul) % mod;
}
void pushdown(int u) {
	maketag(u * 2, tr[u].mul, tr[u].add);
	maketag(u * 2 + 1, tr[u].mul, tr[u].add);
	tr[u].add = 0;tr[u].mul = 1;
}
void build(int u, int l, int r) {
	if (l == r) {
		tr[u] = Node{ l,r,0,0,1 };
		return;
	}
	tr[u] = Node{ l,r,0,0,1 };
	int mid = (l + r) / 2;
	build(u * 2, l, mid);
	build(u * 2 + 1, mid + 1, r);
	pushup(u);
}
void modify(int u, int l, int r, ll _mul, ll _add) {
	if (l <= tr[u].l && tr[u].r <= r) {
		maketag(u, _mul, _add);
		return;
	}
	pushdown(u);
	int mid = (tr[u].l + tr[u].r) / 2;
	if (l <= mid)	modify(u * 2, l, r, _mul, _add);
	if (r > mid)	modify(u * 2 + 1, l, r, _mul, _add);
	pushup(u);
}
ll query(int u, int l, int r) {
	if (l <= tr[u].l && tr[u].r <= r) {
		return tr[u].sum;
	}
	pushdown(u);
	int mid = (tr[u].l + tr[u].r) / 2;
	ll res = 0;
	if (l <= mid)	res += query(u * 2, l, r);
	if (r > mid)	res += query(u * 2 + 1, l, r);
	return res % mod;
}

ll n, d, p[1000010], o[1000010], dp[1000010];
int main() {
	std::ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> d;
	build(1, 1, n);
	rep(i, 1, n) {
		cin >> p[i] >> o[i];
	}
	ll L = 1, sumall = 1;
	rep(i, 1, n) {
		if (o[i] == 1) {
			dp[i] = sumall;
			modify(1, i, i, 1, dp[i]);
		}
		else {
			while (L < i && !(o[L] == 1 && p[i] - p[L] <= d))    L++;
			if (L != i) {
				dp[i] = query(1, L, i);
			}
			modify(1, 1, i, 2, 0);
		}
		sumall = (sumall + dp[i]) % mod;
	}
	cout << (sumall - 1 + mod) % mod << "\n";
	return 0;
}