【luogu CF1609G】A Stroll Around the Matrix（贪心）（线段树）

A Stroll Around the Matrix

题目链接：luogu CF1609G

题目大意

给你两个严格上升的序列，保证它们的差分序列也严格递增，其中一个长度不超过 100。
每次操作会选择一个序列，给后面的 k 个加一个首项和公差相同的等差序列，然后构造一个 n*m 的棋盘，(i,j) 位置的值是第一个数组 i 位置的值加上第二个数组 j 位置的值。
问你从 (1,1) 走到 (n,m) 只往右向下走的最小费用和。

思路

发现一件特别的性质，不仅序列递增，序列差分也递增。
我们再看算费用的方式，假设没有修改，我们要怎么快速的搞。

发现因为是递增，如果我们求出差分数组，而且每个位置的费用是 $a_i+b_j$。
那如果我们差分了，那就是说如果你这里把 $a$ 移到下一个位置，那后面的所有位置的都要加上你移之前的 $a$ 值。
那我们一个贪心的想法是先放这个值小的。
再加上差分数组也严格递增，那不就是把两个差分后得到的数组归并一下！

然后考虑怎么归并，发现有一个特别小，那是不是可以直接枚举小的每个数插入到大的，插到线段树上二分。
然后注意插入之后不仅要有自己的贡献，还有 $b$ 前面部分因为它能多贡献一次。

然后就没啥了。

代码

#include
#include
#define ll long long

using namespace std;

const int N = 1e5 + 100;
int n, m, q;
ll a[105], b[N], aa[105], bb[N];

struct XD_tree {
	ll lzy[N << 2], sum[N << 2], maxn[N << 2], sums[N << 2];
	
	void up(int now) {
		sum[now] = sum[now << 1] + sum[now << 1 | 1];
		sums[now] = sums[now << 1] + sums[now << 1 | 1];
		maxn[now] = max(maxn[now << 1], maxn[now << 1 | 1]);
	}
	
	void downa(int now, int l, int r, ll k) {
		sum[now] += k * (r - l + 1); maxn[now] += k;
		sums[now] += k * (l + r) * (r - l + 1) / 2;
		lzy[now] += k;
	}
	
	void down(int now, int l, int r) {
		int mid = (l + r) >> 1;
		if (lzy[now]) {
			downa(now << 1, l, mid, lzy[now]);
			downa(now << 1 | 1, mid + 1, r, lzy[now]);
			lzy[now] = 0;
		}
	}
	
	void build(int now, int l, int r) {
		if (l == r) {
			sum[now] = maxn[now] = b[l];
			sums[now] = b[l] * l; return ;
		}
		int mid = (l + r) >> 1;
		build(now << 1, l, mid); build(now << 1 | 1, mid + 1, r);
		up(now);
	}
	
	void Add(int now, int l, int r, int L, int R, ll k) {
		if (L <= l && r <= R) {
			downa(now, l, r, k); return ;
		}
		down(now, l, r); int mid = (l + r) >> 1;
		if (L <= mid) Add(now << 1, l, mid, L, R, k);
		if (mid < R) Add(now << 1 | 1, mid + 1, r, L, R, k);
		up(now);
	}
	
	int find(int now, int l, int r, ll k) {
		if (k > maxn[now]) return r;
		if (l == r) return l - 1;
		down(now, l, r); int mid = (l + r) >> 1;
		if (maxn[now << 1] >= k) return find(now << 1, l, mid, k);
			else return find(now << 1 | 1, mid + 1, r, k);
	}
	
	ll query(int now, int l, int r, int L, int R) {
		if (L > R) return 0;
		if (L <= l && r <= R) return sum[now];
		down(now, l, r); int mid = (l + r) >> 1; ll re = 0;
		if (L <= mid) re += query(now << 1, l, mid, L, R);
		if (mid < R) re += query(now << 1 | 1, mid + 1, r, L, R);
		return re;
	}
}T;

void adda(int k, int d) {
	if (k == n) a[0] += d, k--;
	for (int i = 1; i <= k; i++) a[n - i] += d;
}

void addb(int k, int d) {
	if (k == m) b[0] += d, k--;
	T.Add(1, 1, m - 1, m - 1 - k + 1, m - 1, d);
}

ll slove() {
	ll ans = (a[0] + b[0]) * (n + m - 1) + T.sum[1] * m - T.sums[1];
	for (int i = 1; i < n; i++) {
		int pl = T.find(1, 1, m - 1, a[i]);
		ans += T.query(1, 1, m - 1, 1, pl) + a[i] * (n + m - 2 - pl - (i - 1));
	}
	return ans;
}

int main() {
	scanf("%d %d %d", &n, &m, &q);
	for (int i = 1; i <= n; i++) scanf("%lld", &aa[i]), a[i - 1] = aa[i] - aa[i - 1];
	for (int i = 1; i <= m; i++) scanf("%lld", &bb[i]), b[i - 1] = bb[i] - bb[i - 1];
	T.build(1, 1, m - 1);
	while (q--) {
		int op, k, d; scanf("%d %d %d", &op, &k, &d);
		if (op == 1) adda(k, d); if (op == 2) addb(k, d);
		printf("%lld\n", slove());
	}
	
	return 0;
}