题解 P9130 【[USACO23FEB] Hungry Cow P】

赛时开始一眼线段树分治，交了几发都 T 了，就意识到事情不对。后来想了想发现势能分析不能带撤销。。。

后来加了一些不能改变复杂度假了的优化，没过之后就自闭跑路了。。。

赛后听别人说了个楼房重建就明白怎么做了。

首先，我们离线下来把 \(a\) 排序，去重（这样方便一点，不然权值线段树上的空节点得特判），线段树的叶子节点表示的是 \([t_i,t_{i+1})\) 这段区间。为了方便，我们设 \(t_{n+1}=\inf\)。

我们维护当前线段树区间的 \(4\) 个值：

1. 总共匹配了多少个值；
2. 总共向右超出了多少个值；
3. 匹配的答案是多少；
4. 左区间超出部分的答案，若左区间超出部分在右区间依旧超出，那就不管了。

考虑 pushup，分 \(2\) 种情况：

1. 左区间超出部分在右区间依旧超出，则右区间被填满了；
2. 左区间超出部分都可以在右区间插入，我们在右区间做线段树二分，计算出最后一个左区间超出部分的位置。由于需要减掉原始匹配的答案所以具体实现时需要维护 4（在 pushup 的时候记一下）。

写的时候刚睡醒，一个地方 + 和 - 打反了，调了半年。

代码很短：

#include <bits/stdc++.h>
#define ls num << 1
#define rs ls | 1
#define li ls, l, mid
#define ri rs, mid + 1, r
#define int long long
#define SZ(x) (int) x.size() - 1
#define all(x) x.begin(), x.end()
#define ms(x, y) memset(x, y, sizeof x)
#define F(i, x, y) for (int i = (x); i <= (y); i++)
#define DF(i, x, y) for (int i = (x); i >= (y); i--)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
template <typename T> void chkmax(T &x, T y) { x = max(x, y); }
template <typename T> void chkmin(T &x, T y) { x = min(x, y); }
template <typename T> void read(T &x) {
	x = 0; int f = 1; char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
	x *= f;
}
const int N = 1e5 + 10, MOD = 1e9 + 7, inv2 = (MOD + 1) / 2;
int rt, tot, x[N], y[N], t[N];
int qq(int l, int r) {
	return ((r - l + 1) % MOD) * ((l + r) % MOD) % MOD * inv2 % MOD;
}
struct seg {
	int out, sum, ans, lans;
} tt[N * 4];
pair <int, int> query(int num, int l, int r, int x) {
	if (l == r) return make_pair(t[l] + tt[num].sum + x - 1, tt[num].ans);
	int mid = (l + r) >> 1;
	int cnt = t[mid + 1] - t[l] - tt[ls].sum;
	if (x <= cnt) return query(ls, l, mid, x);
	pair <int, int> ans = query(rs, mid + 1, r, x - cnt + tt[ls].out);
	ans.second += tt[ls].ans + tt[num].lans;
	return ans;
}
void pushup(int num, int l, int r) {
	int mid = (l + r) >> 1;
	int cnt = t[r + 1] - t[mid + 1] - tt[rs].sum;
	if (cnt < tt[ls].out) {
		tt[num].out = tt[rs].out + tt[ls].out - cnt;
		tt[num].sum = tt[ls].sum + t[r + 1] - t[mid + 1];
		tt[num].ans = tt[ls].ans + qq(t[mid + 1], t[r + 1] - 1);
		tt[num].lans = -1;
	} else {
		tt[num].out = tt[rs].out;
		tt[num].sum = tt[ls].sum + tt[rs].sum + tt[ls].out;
		pair <int, int> pos = make_pair(t[mid + 1] - 1, 0);
		if (tt[ls].out) pos = query(rs, mid + 1, r, tt[ls].out);
		tt[num].lans = qq(t[mid + 1], pos.first) - pos.second;
		tt[num].ans = tt[ls].ans + tt[rs].ans + tt[num].lans;
	}
}
void change(int num, int l, int r, int x, int y) {
	if (l == r) {
		tt[num].sum = min(y, t[l + 1] - t[l]);
		tt[num].ans = qq(t[l], t[l] + tt[num].sum - 1);
		tt[num].out = y - tt[num].sum;
		return;
	} int mid = (l + r) >> 1;
	if (mid >= x) change(li, x, y);
	else change(ri, x, y);
	pushup(num, l, r);
}
signed main() {
	int n; read(n);
	F(i, 1, n) read(x[i]), read(y[i]), t[i] = x[i];
	sort(t + 1, t + n + 1);
	int m = unique(t + 1, t + n + 1) - t - 1;
	t[m + 1] = 1e18;
	F(i, 1, n) {
		change(1, 1, m, lower_bound(t + 1, t + m + 1, x[i]) - t, y[i]);
		cout << (tt[1].ans % MOD + MOD) % MOD << '\n';
	}
	return 0;
}