标签：Ynoi2019 le int text mid leq que rprmq1 P6109

Luogu P6109 [Ynoi2009] rprmq1

Luogu P6109

题目背景

我谔谔

本题读入量约 13 MB，输出量约 7 MB，请选择合适的输入输出方法

题目描述

有一个 \(n \times n\) 的矩阵 \(a\)，初始全是 \(0\)，有 \(m\) 次修改操作和 \(q\) 次查询操作，先进行所有修改操作，然后进行所有查询操作。

一次修改操作会给出 \(l_1,l_2,r_1,r_2,x\)，代表把所有满足 \(l_1 \le i \le r_1\) 且 \(l_2 \le j \le r_2\) 的 \(a_{i,j}\) 元素加上一个值 \(x\)。

一次查询操作会给出 \(l_1,l_2,r_1,r_2\)，代表查询所有满足 \(l_1 \le i \le r_1\) 且 \(l_2 \le j \le r_2\) 的 \(a_{i,j}\) 元素的最大值。

输入格式

第一行三个由空格分隔的整数 \(n,m,q\)。

之后 \(m\) 行，每行给出五个整数 \(l_1,l_2,r_1,r_2,x\)，表示一次修改操作。

之后 \(q\) 行，每行给出四个整数 \(l_1,l_2,r_1,r_2\)，表示一次查询操作。

输出格式

输出 \(q\) 行，对每次查询操作输出一行一个数表示答案。

样例 #1

样例输入 #1

样例输出 #1

提示

Idea：apiadu，Solution：ccz181078，Code：apiadu，Data：apiadu&nzhtl1477

注意：本题采用捆绑测试，只有当你通过一个 subtask 中的所有测试点后，你才能拿到这个 subtask 的分数。

对于其中 \(1\%\) 的数据，为样例 1。

对于另外 \(9\%\) 的数据，\(n=1\)。

对于另外 \(19\%\) 的数据，\(n,m\leq 500\)。

对于另外 \(19\%\) 的数据，\(n\leq 2000\)，\(q\leq 2\times 10^5\)。

对于另外 \(19\%\) 的数据，\(m,q\leq 2000\)。

对于 \(100\%\) 的数据，\(1\leq n,m\leq 5\times 10^4\)，\(1\leq q \leq 5\times 10^5\)，\(1\leq x\leq 2147483647\)，\(1\leq l_1\leq r_1\leq n\)，\(1\leq l_2\leq r_2\leq n\)。

Solution

首先原问题是二维的，考虑压缩到一维加上时间轴的方式来解决。对于每一次修改操作 \((l_1,r_1,l_2,r_2,v)\) 可以转化为在 \(l_1\) 时间将 \([l_2,r_2]\) 增加 \(v\)，然后在 \(r_1+1\) 的时间将 \([l_2,r_2]\) 增加 \(-v\)。那么询问 \((l_1,r_1,l_2,r_2)\) 变成了求 \(l_1\sim r_1\) 时间内区间 \([l_2,r_2]\) 的历史最值。题目中强调修改操作都在询问之前，明示离线分治。

考虑线段树分治，用外层线段树表示时间这一轴，对于一个线段树上的节点 \([l,r]\)，将包含在这个区间内的询问分类为：左右端点都在 \([l,\text{mid}]\) 内，左右端点都在 \((\text{mid},r]\)，左右端点分居 \(\text{mid}\) 两侧。容易发现只需要讨论第三种询问，前两种询问都可以通过递归到子树内解决。

既然所有的询问都跨越 \(\text{mid}\) 这一点，那么考虑将询问时间段 \([l,r]\) 拆分为 \([l,\text{mid}]\cup[\text{mid}+1,r]\)。那么可以先将 \([l,\text{mid}]\) 时间的修改加入，然后逐个加入 \([\text{mid}+1,r]\) 的修改，同时计算右端点为当前位置的询问的答案。撤销这部分修改，递归进入右子树。逐步撤销 \([l,\text{mid}]\) 的修改，然后计算左端点为当前位置的询问的答案。递归进入左子树。

需要用到支持区间加，区间历史最值的线段树，参考P4314 CPU 监控。

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
using ui64 = unsigned long long;
using Ldouble = long double;
#define fir first
#define sec second
#define MP make_pair
template<class T> void read(T &x) {
	x = 0; bool flag = 0; char b = getchar();
	while (!isdigit(b)) flag = b == '-' ? 1 : 0, b = getchar();
	while (isdigit(b)) x = x * 10 + b - 48, b = getchar();
	x = flag ? -x : x;
}
template<class T, class ...Args> void read(T &x, Args &...args) {
	read(x), read(args...);
}
constexpr int _N = 5e5 + 5, _Q = 5e5 + 5;
int n, m, q;
#define LC (k << 1)
#define RC (k << 1 | 1)
#define mid ((l + r) >> 1)
template<class T> void Max(T &x, T y) { x = max(x, y); }
namespace SGT {
	i64 maxn[_N << 2], hmax[_N << 2], tag1[_N << 2], tag2[_N << 2];
	bool Isres[_N << 2];
	void Pushup(int k) {
		maxn[k] = max(maxn[LC], maxn[RC]);
		hmax[k] = max(hmax[LC], hmax[RC]);
	}
	void Add(int k, i64 v1, i64 v2) {
		Max(tag2[k], tag1[k] + v2);
		Max(hmax[k], maxn[k] + v2);
		maxn[k] += v1, tag1[k] += v1;
	}
	void Reset(int k) {
		Add(LC, tag1[k], tag2[k]), Add(RC, tag1[k], tag2[k]);
		Isres[k] = 1, hmax[k] = maxn[k], tag1[k] = tag2[k] = 0;
	}
	void Pushdown(int k) {
		if (Isres[k]) {
			Reset(LC), Reset(RC);
			Isres[k] = 0;
		}
		Add(LC, tag1[k], tag2[k]), Add(RC, tag1[k], tag2[k]);
		tag1[k] = tag2[k] = 0;
	}
	void Update(int k, int l, int r, int a, int b, i64 v) {
		if (l > b || r < a) return ;
		if (l >= a && r <= b) return Add(k, v, v);
		Pushdown(k);
		Update(LC, l, mid, a, b, v), Update(RC, mid + 1, r, a, b, v);
		Pushup(k);
	}
	i64 Query(int k, int l, int r, int a, int b) {
		if (l > b || r < a) return 0;
		if (l >= a && r <= b) return hmax[k];
		Pushdown(k);
		return max(Query(LC, l, mid, a, b), Query(RC, mid + 1, r, a, b));
	}
}
struct Query { int id, l, r, x, y; };
struct Node { int l, r; i64 v; };
vector<Query> que[_N << 2];
vector<Node> vec[_N];
void AddQuery(int k, int l, int r, Query v) {
	if (v.l <= mid + 1 && v.r >= mid) {
		que[k].push_back(v);
		return ;
	}
	if (v.r <= mid) AddQuery(LC, l, mid, v);
	else AddQuery(RC, mid + 1, r, v);
}
void Add(int x) {
	for (auto s : vec[x]) SGT::Update(1, 1, n, s.l, s.r, s.v);
}
void Remove(int x) {
	for (int i = vec[x].size() - 1; i >= 0; --i) {
		auto s = vec[x][i];
		SGT::Update(1, 1, n, s.l, s.r, -s.v);
	}
}
i64 ans[_Q];
bool cmp1(Node A, Node B) { return A.v < B.v; }
bool cmp2(Query A, Query B) { return A.r < B.r; }
bool cmp3(Query A, Query B) { return A.l > B.l; }
void Solve(int k, int l, int r) {
	for (int i = l; i <= mid; ++i) Add(i);
	int p = 0, siz = que[k].size();
	sort(que[k].begin(), que[k].end(), cmp2);
	while (p < siz && que[k][p].r == mid) ++p;
	for (int i = mid + 1; i <= r; ++i) {
		Add(i);
		if (i == mid + 1) SGT::Reset(1);
		while (p < siz && que[k][p].r == i) {
			Max(ans[que[k][p].id], SGT::Query(1, 1, n, que[k][p].x, que[k][p].y));
			++p;
		}
	} 
	for (int i = r; i >= mid + 1; --i) Remove(i);
	if (l != r) Solve(RC, mid + 1, r);
	p = 0;
	sort(que[k].begin(), que[k].end(), cmp3);
	while (p < siz && que[k][p].l == mid + 1) ++p;
	for (int i = mid; i >= l; --i) {
		if (i == mid) SGT::Reset(1);
		while (p < siz && que[k][p].l == i) {
			Max(ans[que[k][p].id], SGT::Query(1, 1, n, que[k][p].x, que[k][p].y));
			++p;
		}
		Remove(i);
	}
	if (l != r) Solve(LC, l, mid);
} 
signed main() {
	ios::sync_with_stdio(0); cout.tie(0);
	read(n, m, q);
	for (int i = 1; i <= m; ++i) {
		int l, r, x, y, v;
		read(l, x, r, y, v);
		vec[l].push_back((Node){ x, y, v });
		vec[r + 1].push_back((Node){ x, y, -v });
	}
	for (int i = 1; i <= q; ++i) {
		int l, r, x, y;
		read(l, x, r, y);
		AddQuery(1, 1, n, (Query){ i, l, r, x, y });
	}
	for (int i = 1; i <= n; ++i)
		sort(vec[i].begin(), vec[i].end(), cmp1);
	Solve(1, 1, n);
	for (int i = 1; i <= q; ++i) cout << ans[i] << '\n';
}

标签：Ynoi2019,le,int,text,mid,leq,que,rprmq1,P6109
From： https://www.cnblogs.com/hanx16msgr/p/17545550.html

P6109 [Ynoi2019] rprmq1