Submission #73109382

---

Source Code Expand

#include<bits/stdc++.h>
#define LL long long
#define PII pair<int, int>
#define PLI pair<LL, int>
#define PLL pair<LL, LL>
using namespace std;
const int N = 4e5, inf = 1e9, LOG = 20;
int n;
struct SGT {
	struct node	{
		int l, r, lc, rc, mi, mx;
	};
	int ret;
	vector<node> tree;
	inline void init() {
		tree.clear(); ret = 0;
		tree.push_back({0, 0, 0, 0, n + 1, 0});
	}
	inline void update(int pos, int v, int &id, int l = 1, int r = inf) {
		if (pos < l || r < pos) return;
		int mid = (l + r) >> 1, h = id;
		if (id == 0) {
//			if (l != 1 || r != inf) cerr << tree[1].lc << " " << tree[1].rc << "\n";
			h = id = tree.size();
//			if (l != 1 || r != inf) cerr << id << " " << tree[1].lc << " " << tree[1].rc << " " << l << " " << r << " " << pos << " " << v << " ok\n";
			tree.push_back({l, r, 0, 0, v, v});
		}
			
		if (l == r) {
			tree[h].mi = min(tree[h].mi, v);
			tree[h].mx = max(tree[h].mx, v); 
//			cerr << h << " " << l << " " << r << " " << tree[id].mi << " " << tree[id].mx << " val\n";
			return; 
		}
		update(pos, v, tree[h].lc, l, mid);
		update(pos, v, tree[h].rc, mid + 1, r);
		tree[h].mi = min(tree[tree[h].lc].mi, tree[tree[h].rc].mi);
		tree[h].mx = max(tree[tree[h].lc].mx, tree[tree[h].rc].mx);
	}
	PII query(const int z, const int y, int id) {
		if (id == 0 || y < tree[id].l || tree[id].r < z) return {0, n + 1};
//		cerr << z << " " << y << " " << id << " " << tree[id].mi << " " << tree[id].mx << "\n";
		int l = tree[id].l, r = tree[id].r;
		if (z <= l && r <= y) return {tree[id].mx, tree[id].mi};
		PII a = query(z, y, tree[id].rc), b = query(z, y, tree[id].lc);
//		cout << a.first << " " << b.first << " " << tree[id].lc << " " << tree[id].rc << " no\n";
		return {max(a.first, b.first), min(a.second, b.second)};
	}
}f, g;
int st1[LOG + 5][N + 5], st2[LOG + 5][N + 5], lg[N + 5];
inline PII getval(int l, int r) {
	if (l > r) return {0, n + 1};
	int len = r - l + 1;
	PII ret;
	ret.first = max(st1[lg[len]][l], st1[lg[len]][r - (1 << lg[len]) + 1]);
	ret.second = min(st2[lg[len]][l], st2[lg[len]][r - (1 << lg[len]) + 1]);
	return ret;
}
inline void solve() {
	int d; cin >> n >> d;
	vector<int> a(n + 5), l(n + 5), r(n + 5);
	for (int i = 1; i <= n; i++) cin >> a[i];
	lg[1] = 0;
	for (int i = 2; i <= n; i++) lg[i] = lg[i >> 1] + 1;
	f.init();
	for (int i = 1; i <= n; i++) {
		l[i] = f.query(max(1, a[i] - d + 1), min(inf, a[i] + d - 1), f.ret).first;
		f.update(a[i], i, f.ret);
		st1[0][i] = l[i];
	}
	g.init();
	for (int i = n; i >= 1; --i) {
		r[i] = g.query(max(1, a[i] - d + 1), min(inf, a[i] + d - 1), g.ret).second;
		g.update(a[i], i, g.ret);
		st2[0][i] = r[i];
	}
//	for (int i = 1; i <= n; i++) cout << i << ": " << l[i] << " " << r[i] << "\n";
	for (int i = 1; i <= LOG; i++) {
		for (int j = 1; j <= n; j++) {
			st1[i][j] = max(st1[i - 1][j], st1[i - 1][min(n, j + (1 << (i - 1)))]);
			st2[i][j] = min(st2[i - 1][j], st2[i - 1][min(n, j + (1 << (i - 1)))]);
//			cout << i << " " << j << " " << st1[i][j] << " " << st2[i][j] << "\n"; 
		}
	}
	LL ans = 0;
	for (int i = 1; i <= n; i++) {
		int l = i, r = n, pos = i;
		while (l <= r) {
			int mid = (l + r) >> 1;
			PII val = getval(i, mid);
//			cout << i << " " << l << " " << r << " " << mid << " " << val.first << " " << val.second << "\n";
			if (val.first < i && val.second > mid) pos = mid, l = mid + 1;
			else r = mid - 1;
		}
		ans += pos - i + 1;
	}
	cout << ans << "\n";
}
signed main() {
	ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
	int t = 1;
	//cin >> t;
	while (t--) solve();
	return 0;
}

Submission Info

Judge Result