跪求大佬测评

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define PII pair<int, int>
#define _for(i, a, b) for (int i = (a); i <= (b); i++)
#define _pfor(i, a, b) for (int i = (a); i >= (b); i--)

const int N = 1e6 + 5; 

int T, n, m, Len, V, p[N], nxt[N], vis[N], din[N];
int dfn[N], low[N], idx, scc_cnt, bel[N], dp[N];
stack<int> stk;

struct edge {
	int d, v, a;
}ed[N];
vector<PII> G[N], nG[N];

void init() {
	scc_cnt = idx = 0;
	_for(i, 1, max(n, m) + 1) vis[i] = bel[i] = dfn[i] = low[i] = din[i] = dp[i] = 0, G[i].clear(), nG[i].clear();
	while (stk.size()) stk.pop();
	_for(i, 0, Len + 1) nxt[i] = 2e18;
}

void tarjan(int u) {
	dfn[u] = low[u] = ++idx;
	stk.push(u); vis[u] = 1;
	for (auto e : G[u]) {
		int v = e.first;
		if (!dfn[v]) {
			tarjan(v);
			low[u] = min(low[u], low[v]);
		}
		else if (vis[v]) low[u] = min(low[u], dfn[v]);
	}
	if (dfn[u] == low[u]) {
		int y; scc_cnt++;
		do {
			y = stk.top(); stk.pop();
			vis[y] = 0;
			bel[y] = scc_cnt;
		} while (y != u);
	}
}

void add(int a, int b) {
	G[a].push_back({b + 1, 1});
}

int read() {
	char c = ' ';
	int f = 1, x = 0;
	while (c < '0' || c > '9') {
		if (c == '-') f = -1;
		c = getchar();
	}
	while (c >= '0' && c <= '9') {
		x = x * 10 + c - '0';
		c = getchar();
	}
	return x * f;
}

void wr(int x) {
	if (x < 0) putchar('-'), x = -x;
	if (x > 9) wr(x / 10);
	putchar(x % 10 + '0');
}
//fc detect.out detect5.ans
signed main() {
//	freopen("detect2.in", "r", stdin);
//	freopen("detect.out", "w", stdout);
	cin >> T;
	while (T--) {
		cin >> n >> m >> Len >> V;
		init();
		_for(i, 1, n) ed[i].d = read(), ed[i].v = read(), ed[i].a = read();
		_for(i, 1, m) p[i] = read(), nxt[p[i]] = i;
		_pfor(i, Len, 0) nxt[i] = min(nxt[i], nxt[i + 1]);
//		_for(i, 1, Len) cout << nxt[i] << ' ';
//		puts("");
		int res = 0;
		_for(i, 1, m) G[i].push_back({i + 1, 0}), G[1].push_back({i, 0});
		_for(i, 1, n) {
			if (ed[i].a == 0) {
				if (ed[i].v > V) {
					if (nxt[ed[i].d] != 2e18) res++, add(nxt[ed[i].d], m)/*, cout << "che=" << nxt[ed[i].d] << ' ' << m << endl;*/;
				}
			}
			if (ed[i].a < 0) {
				if (ed[i].v > V) {
					if (nxt[ed[i].d] == 2e18) continue;
					int L = nxt[ed[i].d], R = m;
					while (L < R) {
						int mid = (L + R + 1) >> 1;
						if (ed[i].v * ed[i].v + 2 * ed[i].a * (p[mid] - ed[i].d) > V * V && (p[mid] - ed[i].d) * 2 * ed[i].a > -ed[i].v * ed[i].v) L = mid;
						else R = mid - 1;
					}
					if (ed[i].v * ed[i].v + 2 * ed[i].a * (p[L] - ed[i].d) > V * V && (p[L] - ed[i].d) * 2 * ed[i].a > -ed[i].v * ed[i].v) {
//						cout << i << ':' << L << endl;
						res++;
						add(nxt[ed[i].d], L);
//						cout << "che=" << nxt[ed[i].d] << ' ' << m << endl;
					}
				}
			}
			if (ed[i].a > 0) {
				if (nxt[ed[i].d] == 2e18) continue;
				int L = nxt[ed[i].d], R = m;
				while (L < R) {
					int mid = (L + R) >> 1;
					if (ed[i].v * ed[i].v + 2 * ed[i].a * (p[mid] - ed[i].d) > V * V) R = mid;
					else L = mid + 1;
				}
				if (ed[i].v * ed[i].v + 2 * ed[i].a * (p[L] - ed[i].d) > V * V) {
					res++;
					add(L, m);
//					cout << "che=" << L << ' ' << m << endl;
				}
			}
		}
		_for(i, 1, m) if (!dfn[i]) tarjan(i);
//		_for(i, 1, n) cout << bel[i] << ' ';
		_for(i, 1, m) {
			for (auto e : G[i]) {
				int v = e.first, w = e.second;
				if (bel[i] != bel[v]) nG[bel[i]].push_back({bel[v], w}), din[bel[v]]++;
			}
		}
		queue<int> q;
		vector<int> Tans;
		_for(i, 1, scc_cnt + 1) if (!din[i]) q.push(i);
		_for(i, 1, scc_cnt + 1) dp[i] = -2e18;
		dp[bel[m + 1]] = 0;
//		cout << bel[m + 1] << endl;
		while (q.size()) {
			int u = q.front(); q.pop();
			Tans.push_back(u);
			for (auto e : nG[u]) {
				int v = e.first;
				if (--din[v] == 0) q.push(v);
			}
		}
		reverse(Tans.begin(), Tans.end());
		for (auto u : Tans) {
			for (auto e : nG[u]) {
				int v = e.first, w = e.second;
//				cout << u << ' ' << v << endl;
				dp[u] = max(dp[u], dp[v] + w); 
			}
		}
		cout << res << ' ' << m - dp[bel[1]] << '\n';
	}
}
/*
1
5 5 15 3
0 3 0
12 4 0
1 1 4
5 5 -2
6 4 -4
2 5 8 9 15
*/

#include <bits/stdc++.h>
using namespace std;

#define ls p << 1
#define rs p << 1 | 1
#define int long long
#define PII pair<int, int>
#define _for(i, a, b) for (int i = (a); i <= (b); i++)
#define _pfor(i, a, b) for (int i = (a); i >= (b); i--)

const int N = 1e6 + 5; 

int T, n, a[N], sum[N], f[N];

int get(int l, int r) {
	return sum[r] - sum[l];
}

int read() {
	char c = ' ';
	int f = 1, x = 0;
	while (c < '0' || c > '9') {
		if (c == '-') f = -1;
		c = getchar();
	}
	while (c >= '0' && c <= '9') {
		x = x * 10 + c - '0';
		c = getchar();
	}
	return x * f;
}

void wr(int x) {
	if (x < 0) putchar('-'), x = -x;
	if (x > 9) wr(x / 10);
	putchar(x % 10 + '0');
}

struct edge {
	int l, r, maxn;
}tree[N * 4];

void push_up(int p) {
	tree[p].maxn = max(tree[ls].maxn, tree[rs].maxn);
}

void build(int p, int l, int r) {
	tree[p].l = l, tree[p].r = r; tree[p].maxn = -2e18;
	if (l == r) {
		tree[p].maxn = -2e18;
		return;
	}
	int mid = (l + r) >> 1;
	build(ls, l, mid);
	build(rs, mid + 1, r);
	push_up(p);
}

void modify(int p, int x, int v) {
	if (tree[p].l == tree[p].r) {
		tree[p].maxn = max(tree[p].maxn, v);
		return;
	}
	int mid = (tree[p].l + tree[p].r) >> 1;
	if (x <= mid) modify(ls, x, v);
	else modify(rs, x, v);
	push_up(p);
}

int query(int p, int l, int r) {
	if (l <= tree[p].l && tree[p].r <= r) return tree[p].maxn;
	int res = -2e18, mid = (tree[p].l + tree[p].r) >> 1;
	if (l <= mid) res = max(res, query(ls, l, r));
	if (r > mid) res = max(res, query(rs, l, r));
	return res;
}

signed main() {
//	freopen("color2.in", "r", stdin);
	cin >> T;
	while (T--) {
		cin >> n;
		_for(i, 1, n) a[i] = read(), f[i] = 0;
		_for(i, 1, n) sum[i] = sum[i - 1] + (a[i] == a[i - 1]) * a[i];
		build(1, 0, N - 5);
		modify(1, 0, 0);
		_for(i, 1, n) {
			f[i] = -2e18;
			if (i < n) {
				int t = query(1, a[i + 1], a[i + 1]);
				if (t != -2e18) f[i] = t + a[i + 1] + sum[i];
				f[i] = max(f[i], max(query(1, 0, a[i + 1] - 1), query(1, a[i + 1] + 1, N - 5)) + sum[i]);
			}
			else f[i] = max(f[i], query(1, 0, N - 5) + sum[i]);
			modify(1, a[i], f[i] - sum[i + 1]);
//			_for(j, 0, i - 1) {
//				f[i] = max(f[i], f[j] + get(j + 1, i) + (i < n) * (a[i + 1] == a[j]) * (a[i + 1]));
//			}
//			cout << f[i] << ' ';
		}
//		puts("");
		cout << f[n] << '\n';
	}
}
/*
3
3
1 2 1
4
1 2 3 4
8
3 5 2 5 1 2 1 4
*/