题目链接
手搓一下第一个测试样例可以发现， \(1\sim 3\) 的 \(1,3\) 合并，\(a_3>a_2\) 所以可以维护一个单调栈，单调递减，如果单调栈顶的下一位 \(b\) 等于当前的 \(b\)，且当前 \(a\) 大于栈顶 \(a\) 那么将栈顶下一位和当前的序列合并，这样答案就是栈底。
\(\mathscr{Code:}\)
#include<bits/stdc++.h>
#define LL long long
#define int LL
#define per(i, a, b) for (int i = a, END##i = b; i >= END##i; i--)
#define rep(i, a, b) for (int i = a, END##i = b; i <= END##i; i++)
#define repn(x) rep(x, 1, n)
#define repm(x) rep(x, 1, m)
#define pb push_back
#define e(x) for(int i = h[x], v = to[i]; i; i = nxt[i], v = to[i])
#define E(x) for(auto y : p[x])
#define PII pair<int, int>
#define i64 unsigned long long
#define YY puts("Yes"), exit(0)
#define NN puts("No"), exit(0)
using namespace std;
const int Mod = 1e9 + 7;
const int Inf = 0x3f3f3f3f;
const LL InfLL = 0x3f3f3f3f3f3f3f3f;
inline LL read() {LL s = 0, fu = 1; char ch = getchar(); while (ch < '0' || ch > '9') ch == '-' ? fu = -1 : 0, ch = getchar(); while (ch >= '0' && ch <= '9') s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar(); return s * fu;}#define x first
#define y second
const int N = 3e5 + 10;
int n, top;
PII a[N], stk[N];inline void Main() {top = 0;n = read();repn(i) {a[i].x = read();a[i].y = read();}stk[0] = {0, -1000};rep(i, 1, n) {while (top && stk[top].x <= a[i].x) {if (stk[top - 1].y == a[i].y) {a[i].x += stk[top - 1].x - stk[top].x;top--;}top--;}stk[++top] = a[i];printf("%lld ", stk[1].x);}puts("");
}signed main() {// freopen("input.in", "r", stdin);int T = read();while (T--)Main();return 0;
}
类似的题目