首页 > 其他分享 >cdq分治

cdq分治

时间：2024-08-02 14:39:14浏览次数：14  
标签：Node const int 分治 nd mid cdq

cdq分治

主要思想为分治，分为三个部分：

  • 左区间内部。
  • 左区间对右区间。
  • 右区间内部。

一个保险的标准顺序是先处理左区间，再处理左区间对右区间的贡献，最后处理右区间，这样就可以保证时序性了。

注意这种写法在处理左区间对右区间贡献是要先按标号排序分出正确的左右区间，如果是先递归左右区间则不用。

一般cdq问题在分治时需要保证当前左区间和右区间某一维有序，若处理时没有 \(O(\log n)\) 修改、查询的数据结构，可以采用归并排序的方式将时间复杂度从 \(O(n \log^2 n)\) 优化到 \(O(n \log n)\) 。

处理点对相关问题

给定一个长度为 \(n\) 的序列，统计有一些特性的点对 \((i, j)\) 的数量或找到一对点 \((i, j)\) 使得一些函数的值最大。

基本流程如下：

  • 找到序列中点 \(mid\) 。
  • 将所有点对分为三类：
    • \(i, j \in [l, mid]\) 。
    • \(i, j \in [mid + 1, r]\) 。
    • \(i \in [l, mid], j \in [mid + 1, r]\) 。
  • 将前两类分治处理，设法处理最后一类，一般为统计左区间对右区间的贡献。

三维偏序

有 \(n\) 个元素，每个元素有 \(a_i, b_i, c_i\) 三个属性，设 \(f(i)\) 表示满足 \(a_j \leq a_i \and b_j \leq b_i \and c_j \leq c_i \leq i \not = j\) 的 \(j\) 的数量。对于所有 \(d \in [0, n)\) ，求 \(f(i) = d\) 的 \(i\) 的数量。

\(n \leq 10^5\) ，\(a_i, b_i, c_i \leq 2 \times 10^5\)

先将序列按第一维排序，这样第一维偏序就解决了。

考虑计算 \([l, mid]\) 对 \([mid + 1, r]\) 的贡献，此时只需要满足第二、三维的偏序关系，用树状数组或再用一次 cdq 分治即可。

cdq分治套树状数组：

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 7, V = 2e5 + 7;

struct Node {
	int a, b, c, cnt, ans;
} p[N], nd[N];

int ans[N];

int n, vlim, m;

template <class T = int>
inline T read() {
	char c = getchar();
	bool sign = (c == '-');
	
	while (c < '0' || c > '9')
		c = getchar(), sign |= (c == '-');
	
	T x = 0;
	
	while ('0' <= c && c <= '9')
		x = (x << 1) + (x << 3) + (c & 15), c = getchar();
	
	return sign ? (~x + 1) : x;
}

namespace BIT {
int c[V];

inline void update(int x, int k) {
	for (; x <= vlim; x += x & -x)
		c[x] += k;
}

inline int query(int x) {
	int res = 0;
	
	for (; x; x -= x & -x)
		res += c[x];
	
	return res;
}
} // namespace BIT

void cdq(int l, int r) {
	if (l == r)
		return;
	
	int mid = (l + r) >> 1;
	cdq(l, mid), cdq(mid + 1, r);
	sort(nd + l, nd + mid + 1, [](const Node &a, const Node &b) { return a.b < b.b; });
	sort(nd + mid + 1, nd + r + 1, [](const Node &a, const Node &b) { return a.b < b.b; });
	int j = l;
	
	for (int i = mid + 1; i <= r; ++i) {
		for (; j <= mid && nd[j].b <= nd[i].b; ++j)
			BIT::update(nd[j].c, nd[j].cnt);
			
		nd[i].ans += BIT::query(nd[i].c);
	}
	
	for (--j; j >= l; --j)
		BIT::update(nd[j].c, -nd[j].cnt);
}

signed main() {
	n = read(), vlim = read();
	
	for (int i = 1; i <= n; ++i)
		p[i].a = read(), p[i].b = read(), p[i].c = read();
	
	sort(p + 1, p + 1 + n, [](const Node &a, const Node &b) { return a.a == b.a ? (a.b == b.b ? a.c < b.c : a.b < b.b) : a.a < b.a; });
	
	for (int i = 1, cnt = 1; i <= n; ++i, ++cnt)
		if (p[i].a != p[i + 1].a || p[i].b != p[i + 1].b || p[i].c != p[i + 1].c)
			nd[++m] = p[i], nd[m].cnt = cnt, cnt = 0;
	
	cdq(1, m);
	
	for (int i = 1; i <= m; ++i)
		ans[nd[i].ans + nd[i].cnt - 1] += nd[i].cnt;
	
	for (int i = 0; i < n; ++i)
		printf("%d\n", ans[i]);
	
	return 0;
}

cdq分治套cdq分治：

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 7, V = 2e5 + 7;

struct Node {
	int a, b, c, *ans, flag;
	
	inline bool operator == (const Node &rhs) const {
		return a == rhs.a && b == rhs.b && c == rhs.c;
	}
	
	inline bool operator < (const Node &rhs) const {
		return a == rhs.a ? (b == rhs.b ? c < rhs.c : b < rhs.b) : a < rhs.a;
	}
} a[N], b[N], c[N];

int ans[N], f[N];

int n, vlim;

template <class T = int>
inline T read() {
	char c = getchar();
	bool sign = (c == '-');
	
	while (c < '0' || c > '9')
		c = getchar(), sign |= (c == '-');
	
	T x = 0;
	
	while ('0' <= c && c <= '9')
		x = (x << 1) + (x << 3) + (c & 15), c = getchar();
	
	return sign ? (~x + 1) : x;
}

void cdq2(int l, int r) {
	if (l == r)
		return;
	
	int mid = (l + r) >> 1;
	cdq2(l, mid), cdq2(mid + 1, r);
	
	for (int i = l, j = l, k = mid + 1, res = 0; i <= r; ++i)
		if ((k > r || b[j].c <= b[k].c) && j <= mid)
			c[i] = b[j++], res += c[i].flag;
		else {
			c[i] = b[k++];
			
			if (!c[i].flag)
				*c[i].ans += res;
		}
	
	for (int i = l; i <= r; ++i)
		b[i] = c[i];
}

void cdq1(int l, int r) {
	if (l == r)
		return;
	
	int mid = (l + r) >> 1;
	cdq1(l, mid), cdq1(mid + 1, r);
	
	for (int i = l, j = l, k = mid + 1; i <= r; ++i)
		if ((k > r || a[j].b <= a[k].b) && j <= mid)
			b[i] = a[j++], b[i].flag = 1;
		else
			b[i] = a[k++], b[i].flag = 0;
	
	for (int i = l; i <= r; ++i)
		a[i] = b[i];
	
	cdq2(l, r);
}

signed main() {
	n = read(), vlim = read();
	
	for (int i = 1; i <= n; ++i)
		a[i].a = read(), a[i].b = read(), a[i].c = read(), a[i].ans = ans + i;
	
	sort(a + 1, a + 1 + n);
	
	for (int i = n - 1; i; --i)
		if (a[i] == a[i + 1])
			*a[i].ans = *a[i + 1].ans + 1;
	
	cdq1(1, n);
	
	for (int i = 1; i <= n; ++i)
		++f[ans[i]];
	
	for (int i = 0; i < n; ++i)
		printf("%d\n", f[i]);
	
	return 0;
}

P3157 [CQOI2011] 动态逆序对

给出一个 \(1 \sim n\) 的排列，按给出顺序依次删除 \(m\) 个元素，求每次删除一个元素之前整个序列的逆序对数。

\(n \leq 10^5, m \leq 5 \times 10^4\)

逆序对本质就是二维偏序，这里再引入一个时间维即可转化为三维偏序。注意处理逆序对的时候前后都要统计贡献。

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 2e5 + 7;

struct Node {
    int x, k, t;
} nd[N];

ll ans[N];
int pos[N];

int n, m;

template <class T = int>
inline T read() {
	char c = getchar();
	bool sign = (c == '-');
	
	while (c < '0' || c > '9')
		c = getchar(), sign |= (c == '-');
	
	T x = 0;
	
	while ('0' <= c && c <= '9')
		x = (x << 1) + (x << 3) + (c & 15), c = getchar();
	
	return sign ? (~x + 1) : x;
}

namespace BIT {
int c[N];

inline void update(int x, int k) {
	for (; x <= n; x += x & -x)
		c[x] += k;
}

inline int query(int x) {
	int res = 0;
	
	for (; x; x -= x & -x)
		res += c[x];
	
	return res;
}
} // namespace BIT

void cdq(int l, int r) {
	if (l == r)
		return;

	int mid = (l + r) >> 1;
	cdq(l, mid), cdq(mid + 1, r);
	sort(nd + l, nd + mid + 1, [](const Node &a, const Node &b) { return a.x < b.x; });
	sort(nd + mid + 1, nd + r + 1, [](const Node &a, const Node &b) { return a.x < b.x; });
	int j = l;

	for (int i = mid + 1; i <= r; ++i) {
		for (; j <= mid && nd[j].x < nd[i].x; ++j)
			BIT::update(nd[j].k, 1);

		ans[nd[i].t] += BIT::query(n) - BIT::query(nd[i].k);
	}

	for (--j; j >= l; --j)
		BIT::update(nd[j].k, -1);

	sort(nd + l, nd + mid + 1, [](const Node &a, const Node &b) { return a.x > b.x; });
	sort(nd + mid + 1, nd + r + 1, [](const Node &a, const Node &b) { return a.x > b.x; });
	j = l;

	for (int i = mid + 1; i <= r; ++i) {
		for (; j <= mid && nd[j].x > nd[i].x; ++j)
			BIT::update(nd[j].k, 1);

		ans[nd[i].t] += BIT::query(nd[i].k - 1);
	}

	for (--j; j >= l; --j)
		BIT::update(nd[j].k, -1);
}

signed main() {
	n = read(), m = read();

    for (int i = 1; i <= n; ++i) {
    	int x = read();
    	nd[x] = (Node) {i, x, m + 1};
    }

    for (int i = 1; i <= m; ++i)
    	nd[read()].t = i;

    sort(nd + 1, nd + 1 + n, [](const Node &a, const Node &b) { return a.t > b.t; });

    cdq(1, n);

    for (int i = m; i; --i)
    	ans[i] += ans[i + 1];

    for (int i = 1; i <= m; ++i)
        printf("%lld\n", ans[i]);

    return 0;
}

四维偏序

主流做法是cdq分治套cdq分治套树状数组，时间复杂度 \(O(n \log^3 n)\) ，实现细节较多。

高维偏序

对于一般 \(k\) 维偏序问题，利用cdq嵌套求解是时间复杂度是 \(O(n \log ^{k - 1} n)\) 。

对于高维偏序，我们一般使用 bitset 解决。

对于每一维（记当前处理维度为 \(i\) ），对于除自己以外的所有元素，把满足第 \(i\) 维偏序的元素编号组成一个集合，把所有集合求交即可。

这个做法是在线的，时间复杂度 \(O(\dfrac{n^2}{\omega})\) 。

优化1D/1D动态规划

以二维最长上升子序列为例，可以列出转移方程：

\[f_i = 1 + \max_{j = 1}^{i - 1} f_j [a_j < a_i] [b_j < b_i] \]

直接转移是 \(O(n^2)\) 的，考虑cdq分治优化，假设当前处理的区间为 \(l, r\) ，流程大致如下：

  • 若 \(l = r\) ，说明 \(f_l\) 已求得，直接返回即可。
  • 递归处理 \([l, mid]\) 。
  • 处理所有 \(j \in [l, mid], i \in [mid + 1, r]\) 的转移关系。
  • 递归处理 \([mid + 1, r]\) 。

注意这里必须按标准顺序处理。

P2487 [SDOI2011] 拦截导弹

有 \(n\) 个导弹，每个导弹有两个参数 \(h, v\) 。求一个最长的序列 \(a\) ，满足 \(h, v\) 不升，输出其长度。

由于可能有多种方案，需要求出对于每个导弹，其成为最长序列中的一项的概率。

\(n \leq 5 \times 10^4\)

第一问和二维LIS是类似的，第二问实际就是包含该导弹的方案数除以总方案数。一个显然的事实是包含该导弹的方案数为前后最长序列的方案数的乘积，于是跑正反两遍cdq优化DP即可。

#include <bits/stdc++.h>
using namespace std;
const int N = 5e4 + 7;

struct Node {
	int h, v, id;
	pair<int, double> f;
};

int n;

template <class T = int>
inline T read() {
	char c = getchar();
	bool sign = (c == '-');
	
	while (c < '0' || c > '9')
		c = getchar(), sign |= (c == '-');
	
	T x = 0;
	
	while ('0' <= c && c <= '9')
		x = (x << 1) + (x << 3) + (c & 15), c = getchar();
	
	return sign ? (~x + 1) : x;
}

namespace Pre {
Node nd[N];

namespace BIT {
pair<int, double> f[N];

inline void update(int x, pair<int, double> k) {
	for (; x; x -= x & -x)
		if (k.first > f[x].first)
			f[x] = k;
		else if (k.first == f[x].first)
			f[x].second += k.second;
}

inline void remove(int x) {
	for (; x; x -= x & -x)
		f[x] = make_pair(0, 0);
}

inline pair<int, double> query(int x) {
	pair<int, double> res = make_pair(0, 0);

	for (; x <= n; x += x & -x)
		if (f[x].first > res.first)
			res = f[x];
		else if (f[x].first == res.first)
			res.second += f[x].second;

	return res;
}
} // namespace BIT

void cdq(int l, int r) {
	if (l == r) {
		++nd[l].f.first;
		return;
	}

	int mid = (l + r) >> 1;
	sort(nd + l, nd + r + 1, [](const Node &a, const Node &b) { return a.id < b.id; });
	cdq(l, mid);
	sort(nd + l, nd + mid + 1, [](const Node &a, const Node &b) { return a.h > b.h; });
	sort(nd + mid + 1, nd + r + 1, [](const Node &a, const Node &b) { return a.h > b.h; });
	int j = l;

	for (int i = mid + 1; i <= r; ++i) {
		for (; j <= mid && nd[j].h >= nd[i].h; ++j)
			BIT::update(nd[j].v, nd[j].f);

		pair<int, double> res = BIT::query(nd[i].v);

		if (res.first > nd[i].f.first)
			nd[i].f = res;
		else if (res.first == nd[i].f.first)
			nd[i].f.second += res.second;
	}

	for (--j; j >= l; --j)
		BIT::remove(nd[j].v);

	cdq(mid + 1, r);
}
} // namespace Pre

namespace Suf {
Node nd[N];

namespace BIT {
pair<int, double> f[N];

inline void update(int x, pair<int, double> k) {
	for (; x <= n; x += x & -x)
		if (k.first > f[x].first)
			f[x] = k;
		else if (k.first == f[x].first)
			f[x].second += k.second;
}

inline void remove(int x) {
	for (; x <= n; x += x & -x)
		f[x] = make_pair(0, 0);
}

inline pair<int, double> query(int x) {
	pair<int, double> res = make_pair(0, 0);

	for (; x; x -= x & -x)
		if (f[x].first > res.first)
			res = f[x];
		else if (f[x].first == res.first)
			res.second += f[x].second;

	return res;
}
} // namespace BIT

void cdq(int l, int r) {
	if (l == r) {
		++nd[l].f.first;
		return;
	}

	int mid = (l + r) >> 1;
	sort(nd + l, nd + r + 1, [](const Node &a, const Node &b) { return a.id < b.id; });
	cdq(mid + 1, r);
	sort(nd + l, nd + mid + 1, [](const Node &a, const Node &b) { return a.h < b.h; });
	sort(nd + mid + 1, nd + r + 1, [](const Node &a, const Node &b) { return a.h < b.h; });
	int j = mid + 1;

	for (int i = l; i <= mid; ++i) {
		for (; j <= r && nd[j].h <= nd[i].h; ++j)
			BIT::update(nd[j].v, nd[j].f);

		pair<int, double> res = BIT::query(nd[i].v);

		if (res.first > nd[i].f.first)
			nd[i].f = res;
		else if (res.first == nd[i].f.first)
			nd[i].f.second += res.second;
	}

	for (--j; j >= mid + 1; --j)
		BIT::remove(nd[j].v);

	cdq(l, mid);
}
} // namespace Suf

signed main() {
	n = read();
	vector<int> vec;

	for (int i = 1; i <= n; ++i) {
		Pre::nd[i].h = Suf::nd[i].h = read();
		vec.emplace_back(Pre::nd[i].v = Suf::nd[i].v = read());
		Pre::nd[i].id = Suf::nd[i].id = i;
	}

	sort(vec.begin(), vec.end());
	vec.erase(unique(vec.begin(), vec.end()), vec.end());

	for (int i = 1; i <= n; ++i) {
		Pre::nd[i].v = lower_bound(vec.begin(), vec.end(), Pre::nd[i].v) - vec.begin() + 1;
		Pre::nd[i].f = make_pair(0, 1);
		Suf::nd[i].v = lower_bound(vec.begin(), vec.end(), Suf::nd[i].v) - vec.begin() + 1;
		Suf::nd[i].f = make_pair(0, 1);
	}

	Pre::cdq(1, n), Suf::cdq(1, n);
	sort(Pre::nd + 1, Pre::nd + 1 + n, [](const Node &a, const Node &b) { return a.id < b.id; });
	sort(Suf::nd + 1, Suf::nd + 1 + n, [](const Node &a, const Node &b) { return a.id < b.id; });
	pair<int, double> ans = make_pair(0, 1);

	for (int i = 1; i <= n; ++i)
		if (Pre::nd[i].f.first > ans.first)
			ans = Pre::nd[i].f;
		else if (Pre::nd[i].f.first == ans.first)
			ans.second += Pre::nd[i].f.second;

	printf("%d\n", ans.first);

	for (int i = 1; i <= n; ++i)
		if (Pre::nd[i].f.first + Suf::nd[i].f.first - 1 == ans.first)
			printf("%.5lf ", Pre::nd[i].f.second * Suf::nd[i].f.second / ans.second);
		else
			printf("0.00000 ");

	return 0;
}

将动态问题转化为静态问题

一类问题形如：

  • 带修改与查询。
  • 可以离线。
  • 每一个修改均与之后的询问操作相关。

那么可以将所有操作会按照时间cdq分治。假设现在处理的时间区间为 \([l, r]\) ，先递归处理 \([l, mid]\) 与 \([mid + 1, r]\) 的修改-询问关系，再处理修改 \(\in [l, mid]\) 、询问 \(\in [mid + 1, r]\) 的修改-询问关系，统计这部分修改对询问的贡献。

如果修改之间相互独立，则三部分顺序无所谓，否则必须按标准顺序处理。

P4390 [BalkanOI2007] Mokia 摩基亚

给出一个 \(W \times W\) 的网格，\(n\) 次操作，每次操作为下面两种操作中的一种：

  • 给某个格子加上 \(x\) 。
  • 询问一个矩形中的所有数的和。

\(n \leq 10^5, W \leq 10^6\)

比较板，按上述思路分治即可。

#include <bits/stdc++.h>
using namespace std;
const int N = 2e6 + 7;

struct Node {
	int x, y, k, t, id;
} nd[N];

int ans[N];

int W, n, cntu, cntq;

template <class T = int>
inline T read() {
	char c = getchar();
	bool sign = c == '-';
	
	while (c < '0' || c > '9')
		c = getchar(), sign |= c == '-';
	
	T x = 0;
	
	while ('0' <= c && c <= '9')
		x = (x << 1) + (x << 3) + (c & 15), c = getchar();
	
	return sign ? (~x + 1) : x;
}

namespace BIT {
int c[N];

inline void update(int x, int k) {
	for (; x <= W; x += x & -x)
		c[x] += k;
}

inline int query(int x) {
	int res = 0;
	
	for (; x; x -= x & -x)
		res += c[x];
	
	return res;
}
} // namespace BIT

void cdq(int l, int r) {
	if (l == r)
		return;
	
	int mid = (l + r) >> 1;
	cdq(l, mid), cdq(mid + 1, r);
	sort(nd + l, nd + mid + 1, [](const Node &a, const Node &b) { return a.x < b.x; });
	sort(nd + mid + 1, nd + r + 1, [](const Node &a, const Node &b) { return a.x < b.x; });
	int j = l;

	for (int i = mid + 1; i <= r; ++i) {
		for (; j <= mid && nd[j].x <= nd[i].x; ++j)
			if (!nd[j].id)
				BIT::update(nd[j].y, nd[j].k);

		if (nd[i].id > 0)
			ans[nd[i].id] += BIT::query(nd[i].y);
		else if (nd[i].id < 0)
			ans[-nd[i].id] -= BIT::query(nd[i].y);
	}

	for (--j; j >= l; --j)
		if (!nd[j].id)
			BIT::update(nd[j].y, -nd[j].k);
}

signed main() {
	int op = read();
	W = read() + 1;
	
	while ((op = read()) != 3) {
		if (op == 1) {
			int x = read() + 1, y = read() + 1, k = read();
			++cntu, nd[++n] = (Node) {x, y, k, cntu, 0};
		} else {
			int x = read() + 1, y = read() + 1, xx = read() + 1, yy = read() + 1;
			++cntq;
			nd[++n] = (Node) {xx, yy, 0, cntu, cntq};
			nd[++n] = (Node) {x - 1, yy, 0, cntu, -cntq};
			nd[++n] = (Node) {xx, y - 1, 0, cntu, -cntq};
			nd[++n] = (Node) {x - 1, y - 1, 0, cntu, cntq};
		}
	}
    
	cdq(1, n);
	
	for (int i = 1; i <= cntq; ++i)
		printf("%d\n", ans[i]);
	
	return 0;
}

P4169 [Violet] 天使玩偶/SJY摆棋子

在平面直角坐标系上维护 \(n\) 次操作，每次操作为下面两种操作中的一种：

  • 加入一个点 \((x, y)\) 。
  • 询问与 \((x, y)\) 曼哈顿距离最小的点。

\(n \leq 3 \times 10^5\)

分情况把绝对值拆开就行了，如对于一个 \(j \leq i, x_j \leq x_i, y_j \leq y_i\) 的情况，曼哈顿距离即为 \((x_i + y_i) - (x_j + y_j)\) ，不难发现限制条件为三维偏序，于是cdq分治处理即可。剩下情况也是类似的。

#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
const int N = 3e5 + 7, V = 2e6 + 7;

struct Node {
	int x, y, id;
} nd[4][N << 1];

int ans[N];

int n, m, tot, cntq;

template <class T = int>
inline T read() {
	char c = getchar();
	bool sign = (c == '-');
	
	while (c < '0' || c > '9')
		c = getchar(), sign |= (c == '-');
	
	T x = 0;
	
	while ('0' <= c && c <= '9')
		x = (x << 1) + (x << 3) + (c & 15), c = getchar();
	
	return sign ? (~x + 1) : x;
}

namespace BIT {
int c[V];

inline void prework() {
	fill(c, c + V, -inf);
}

inline void update(int x, int k) {
	for (; x < V; x += x & -x)
		c[x] = max(c[x], k);
}

inline void remove(int x) {
	for (; x < V; x += x & -x)
		c[x] = -inf;
}

inline int query(int x) {
	int res = -inf;
	
	for (; x; x -= x & -x)
		res = max(res, c[x]);
	
	return res;
}
} // namespace BIT

void solve(int l, int r, Node *nd) {
	if (l == r)
		return;
	
	int mid = (l + r) >> 1;
	solve(l, mid, nd), solve(mid + 1, r, nd);
	sort(nd + l, nd + mid + 1, [](const Node &a, const Node &b) { return a.x < b.x; });
	sort(nd + mid + 1, nd + r + 1, [](const Node &a, const Node &b) { return a.x < b.x; });
	int j = l;

	for (int i = mid + 1; i <= r; ++i) {
		for (; j <= mid && nd[j].x <= nd[i].x; ++j)
			if (!nd[j].id)
				BIT::update(nd[j].y, nd[j].x + nd[j].y);

		if (nd[i].id)
			ans[nd[i].id] = min(ans[nd[i].id], nd[i].x + nd[i].y - BIT::query(nd[i].y));
	}
	
	for (--j; j >= l; --j)
		BIT::remove(nd[j].y);
}

signed main() {
	n = read(), m = read();
	
	for (int i = 1; i <= n; ++i) {
		int x = read(), y = read() + 1;
		nd[0][i] = (Node) {x, y, 0};
		nd[1][i] = (Node) {V - x, y, 0};
		nd[2][i] = (Node) {x, V - y, 0};
		nd[3][i] = (Node) {V - x, V - y, 0};
	}
	
	for (int i = n + 1; i <= n + m; ++i) {
		int op = read(), x = read(), y = read() + 1;
		
		if (op == 1) {
			nd[0][i] = (Node) {x, y, 0};
			nd[1][i] = (Node) {V - x, y, 0};
			nd[2][i] = (Node) {x, V - y, 0};
			nd[3][i] = (Node) {V - x, V - y, 0};
		} else {
			++cntq;
			nd[0][i] = (Node) {x, y, cntq};
			nd[1][i] = (Node) {V - x, y, cntq};
			nd[2][i] = (Node) {x, V - y, cntq};
			nd[3][i] = (Node) {V - x, V - y, cntq};
		}
	}
	
	memset(ans + 1, inf, sizeof(int) * cntq);
	BIT::prework();
	
	for (int i = 0; i < 4; ++i)
		solve(1, n + m, nd[i]);
	
	for (int i = 1; i <= cntq; ++i)
		printf("%d\n", ans[i]);
	
	return 0;
}

标签：Node,const,int,分治,nd,mid,cdq
From： https://www.cnblogs.com/wshcl/p/18338717/cdq

相关文章

  • 解密编程的八大法宝（四）（附二分查找、分治法和图论算法（深度和广度优先搜索、最短路径、最
    算法题中常见的几大解题方法有以下几种：：暴力枚举法（BruteForce）：这是最基本的解题方法，直接尝试所有可能的组合或排列来找到答案。这种方法适用于问题规模较小的情况，但在大多数情况下效率不高。贪心算法（GreedyAlgorithm）：贪心算法在每一步都选择当前看起来最优的解，希望最终能......
  • 点分治板子
    #define_CRT_SECURE_NO_WARNINGS#include<iostream>#include<vector>#include<algorithm>#include<math.h>#include<sstream>#include<string>#include<string.h>#include<iomanip>#include<stdlib.h>#inc......
  • 线段树分治小结
    一般来说，这种题目是给定一些信息，比如说边，然后这些信息会在一个时间段内出现。一般来说需要离线，然后建立一棵以维护每个时刻信息的线段树，具体来说就是在每个节点维护一个vector。#121.「离线可过」动态图连通性以经典例题来说，我们根据每条边出现的时刻将它插入到线段树上对应时......
  • 树分治、动态树分治学习笔记
    点分治点分治适合处理大规模的树上路径信息问题，选取重心，将当前的树拆分为几颗子树，然后递归子树求解问题，但是今天的重点不在这里边分治与点分治类似，选取一条边，均匀地将树分成两个部分，但是对于一个点有多个儿子时，时间复杂度就会非常大，于是我们可以将其转化，这里有两种方法\(1.\)......
  • 归并分治_小和问题
    归并分治原理：1）思考一个问题在大范围上的答案，是否等于，左部分的答案+右部分的答案+跨越左右产生的答案2）计算“跨越左右产生的答案”时，如果加上左、右各自有序这个设定，会不会获得计算的便利性3）如果以上两点都成立，那么该问题很可能被归并分治解决4）求解答案的过程中只需......
  • C141 线段树分治+线性基 P3733 [HAOI2017] 八纵八横
    视频链接：C141线段树分治+线性基P3733[HAOI2017]八纵八横_哔哩哔哩_bilibili   P3733[HAOI2017]八纵八横-洛谷|计算机科学教育新生态(luogu.com.cn)//线段树分治+线性基O(q*logq*logL*logL)#include<iostream>#include<cstring>#include<algorithm>......
  • cdq分治 提高篇
    优化动态规划序列首先要会最长上升子序列的转移，这里就不说了。我们\(i\)位置的初始值为\(a_i\)，可能变成的最大值为\(mx_i\)，可能变成的最小值为\(mn_i\)。然后如果\(j\)要转移到\(i\)，则需要满足：\(j<i,mx_j\lea_i,a_j\lemn_i\)。然后考虑把\([l,mid]\)按照\(mx\)......
  • cdq分治
    简介前置芝士：归并排序。\(cdq\)分治是个离线算法，可以解决三维偏序或者优化\(dp\)。题目直接上个题目：陌上花开。维护三维偏序有个口诀：一维排序，二维归并，三位数据结构。考虑第一维直接排序解决掉，然后还剩两维。我们考虑第二维用归并排序解决掉。然后假设当前区间\([l,r]\)，......
  • 离线分治算法：cdq 分治
    \(\texttt{0x00}\)：前置芝士归并排序；树状数组；重载运算符（这个大概都会吧）。\(\texttt{0x01}\)：介绍cdq分治是一种离线分治算法，可用来处理以下几种问题：解决和点对有关的问题。1D动态规划的优化与转移。通过CDQ分治，将一些动态问题转化为静态问题。它们的本质都是通过一......
  • 分治法 -----归并排序、逆序对、最大子数组和
    一分治法概念分治（divide-and-conquer），顾名思义分而治之。分治的核心是将原问题分解为同类型的规模更小的子问题，子问题往往可以求解或者求解比较简单，通过整合子问题的解得到原来问题的解。分治的过程可以用如下图来表示：由上述图示可发现整个分治过程是一颗树，而且子问题的处......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99