BuringStraw

BuringStraw

HomeArchives

CDQ Divide and Conquer Summary

#分治29
AI Translation
This post is translated from Chinese into English through AI.View Original
AI-generated summary
The summary discusses the CDQ divide and conquer method for handling partial order problems, where the left and right sides are treated as complete problems and their impacts are merged. It includes example problems like "Gardener's Troubles" and "Teleportation" for static point counting in a two-dimensional partial order scenario.

After a week of slacking off, I finally understood the CDQ divide and conquer.

In general, the CDQ divide and conquer approach to handling partial order problems is:

  • First, treat the left and right sides as a complete problem.
  • Then merge the influence of the left side on the right side into the right side.

Example Problems#

Gardener's Trouble#

Portal

Find the number of points in a static area, a two-dimensional partial order template problem.

#include<cstdio> 
#include<algorithm>

const int MAXN = 500000 * 5 + 5;

//x,y: horizontal and vertical coordinates
//type: operation type
//add: to calculate the area of the rectangular region using several rectangles, so add indicates the sign
//id: the id of the query, because one query is split into several
//ans: stores the answer corresponding to the current query
struct node {
	int x, y, type, add, id, ans;
} a[MAXN], tmp[MAXN];

int n, m, newp;
int ans[MAXN];

void add (int x, int y, int type, int add, int id, int ans) {
	a[++newp] = (node){x, y, type, add, id, ans};
}

bool cmp1 (node x, node y) {
	if (x.x == y.x) {
		if (x.y == y.y) {// stop when finding a y larger than itself
			return x.type < y.type;// modify before the query
		}
		return x.y < y.y;
	}
	return x.x < y.x;
}

void cdq (int l, int r) {
	if (l == r) {
		return;
	}
	int mid = (l + r) >> 1;
	cdq(l, mid);
	cdq(mid + 1, r);
    // After processing the left half, add all modifications from the left half to the queries in the right half
	int newl = l, newr = mid + 1, pos = l, ans = 0;
    // For the upper interval of this range, the x on the left must be less than that on the right, so sort by y and put back into a
	while (newl <= mid && newr <= r) {// cannot go out of bounds
		if (a[newl].y <= a[newr].y) {// ensure the operation of newl is within the range of newr
			if (a[newl].type == 1) {
				++ans;// it's a point, accumulate the answer
			}
			tmp[pos++] = a[newl++];
		}
		else {
			if (a[newr].type == 2) {
				a[newr].ans += ans;// it's a query, add the previously counted points
			}
			tmp[pos++] = a[newr++];
		}
	}
    // Don't leave any unprocessed
    while (newl <= mid) {
        tmp[pos++] = a[newl++];
    }
    while (newr <= r) {
        if (a[newr].type == 2) {
            a[newr].ans += ans;
        }
        tmp[pos++] = a[newr++];
    }
    // Fill a with the results sorted by y
	for (int i = l; i <= r; ++i) {
		a[i] = tmp[i];
	}
}

int main (void) {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; ++i) {
		int x, y;
		scanf("%d%d", &x, &y);
		add(x, y, 1, 0, 0, 0);
	}
	for (int i = 1; i <= m; ++i) {
		int x1, y1, x2, y2;
		scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
		add(x2, y2, 2, 1, i, 0);
		add(x1 - 1, y2, 2, -1, i, 0);
		add(x2, y1 - 1, 2, -1, i, 0);
		add(x1 - 1, y1 - 1, 2, 1, i, 0);
	}
	
	std::sort(a + 1, a + 1 + newp, cmp1);
	cdq(1, newp);
	
	for (int i = 1; i <= newp; ++i) {
		if (a[i].type == 2) {
			ans[a[i].id] += a[i].add * a[i].ans;
		}
	}
	
	for (int i = 1; i <= m; ++i) {
		printf("%d\n", ans[i]);
	}
	return 0;
}

Binary Indexed Tree 1#

Portal

Treat the time of operation occurrence as the first dimension.

Subsequent number modifications will not affect the prefix sum of the previous numbers.

#include <cstdio> 

const int MAXN = 500000 + 5;

struct node {
	int x, y, id, type;
	friend bool operator <(node x, node y) {
		return x.x == y.x ? x.type < y.type :x.x < y.x;
	}
} a[MAXN * 3], tmp[MAXN * 3];

int n, m, newp;
int ans[MAXN * 2];

void cdq(int l, int r) {
	if (l == r) {
		return;
	}
	
	int mid = (l + r) >> 1;
	cdq(l, mid);
	cdq(mid + 1, r);
	
	int i = l, j = mid + 1, p = l, sum = 0;
	while (i <= mid && j <= r)	 {
		if (a[i] < a[j]) {
			if (a[i].type == 1) sum += a[i].y;
			tmp[p++] = a[i++];
		}
		else {
			if (a[j].type == 2) {
				ans[a[j].id] += sum;
			}
			tmp[p++] = a[j++];
		}
	}
	while (i <= mid) {
		tmp[p++] = a[i++];
	}
	while (j <= r) {
		if (a[j].type == 2) {
			ans[a[j].id] += sum;
		}
		tmp[p++] = a[j++];
	}
	for (int i = l; i <= r; ++i) {
		a[i] = tmp[i];
	}
}

int main (void) {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; ++i) {
		scanf("%d", &a[++newp].y);
		a[newp].x = i;
		a[newp].type = 1;
	}
	int opt, x, y, z, anscnt = 0;
	for (int i = 1; i <= m; ++i)  {
		scanf("%d", &opt);
		if (opt == 1) {
			scanf("%d%d", &x, &y);
			a[++newp].x = x;
			a[newp].y = y;
			a[newp].type = 1;
		}
		else {
			++anscnt;
			scanf("%d%d", &x, &y);
			a[++newp].x = x - 1;
			a[newp].id = anscnt * 2 - 1;
			a[newp].type = 2;
			a[++newp].x = y;
			a[newp].id = anscnt * 2;
			a[newp].type = 2;
		}
	}
	cdq(1, newp);
	for (int i = 1; i <= anscnt; ++i) {
		printf("%d\n", ans[i * 2] - ans[i * 2 - 1]);
	}
	return 0;
}

Flowers Blooming on the Path#

Why did I write "Flowers Blooming on the Path" first? Because it looks cooler this way

Sort by the first dimension, compare the second dimension as before, and then use a value range binary indexed tree to count the third dimension in the range of 0 to x.

Need to remove duplicates

#include <cstdio>
#include <algorithm>

const int MAXN = 200000 + 5;
namespace sz {
	int n;
	int lowbit (int x){return x & (-x);}
	int c[MAXN * 2];
	void add (int x, int k) {
	    while (x <= n) {
	        c[x] += k;
	        x += lowbit(x);
	    }
	}
	int query (int x) {
	    int ans = 0;
	    while (x > 0) {
	        ans += c[x];
	        x -= lowbit(x);
	    }
		return ans;
	}
}

struct node {
	int a, b, c, id;
} a[MAXN], tmp[MAXN];

int n, k, newp;
int size[MAXN], ans[MAXN], num[MAXN];

bool cmp1 (node x, node y) {
	return x.a == y.a ? (x.b == y.b ? x.c < y .c : x.b < y.b) : x.a < y.a;
}

void cdq(int l, int r) {
	if (l == r) return;
	int mid = (l + r) >> 1;
	cdq(l, mid);
	cdq(mid + 1, r);
	int i = l, j = mid + 1, p = l;
	while (i <= mid && j <= r) {
		if (a[i].b <= a[j].b) {
			sz::add(a[i].c, size[a[i].id]);
			tmp[p++] = a[i++];
		}
		else {
			ans[a[j].id] += sz::query(a[j].c);
			tmp[p++] = a[j++];
		}
	}
	while (j <= r) {
		ans[a[j].id] += sz::query(a[j].c);
		tmp[p++] = a[j++];
	}
	for (int h = l; h < i; ++h) {
		sz::add(a[h].c, -size[a[h].id]);
	}
	while (i <= mid) {
		tmp[p++] = a[i++];
	}
	for(int i = l; i <= r; ++i) {
		a[i] = tmp[i];
	}
}

int main (void) {
	scanf("%d%d", &n, &k);
	sz::n = k;
	for (int i = 1; i <= n; ++i) {
		scanf("%d%d%d", &a[i].a, &a[i].b, &a[i].c);
	}
	std::sort(a + 1, a + 1 + n, cmp1);
	for (int i = 1; i <= n; ++i) {
		if (a[i].a != a[i - 1].a || a[i].b != a[i - 1].b || a[i].c != a[i - 1].c) {
			tmp[++newp] = a[i];
		}
		++size[newp];
	}
	for (int i =1; i <= newp; ++i) {
		a[i] = tmp[i];
		a[i].id = i;
	}
	cdq(1, newp);
	for (int i = 1; i <=newp; ++i) {
		num[ans[a[i].id] + size[a[i].id] - 1] += size[a[i].id];// besides the count in ans, also add the count of completely identical ones
	}
	for (int i = 0; i < n; ++i) {
		printf("%d\n", num[i]);
	}
	return 0;
}

Mokia#

Portal

Actually, this is Nokia

Originally a two-dimensional problem, adding time order makes it three-dimensional.

The index of the binary indexed tree cannot be 0

#include <cstdio>
#include <algorithm>

const int MAXN = 1700000 + 5;
namespace sz {
	int n;
	int lowbit (int x){return x & (-x);}
	int c[MAXN * 2];
	void add (int x, int k) {
	    while (x <= n) {
	        c[x] += k;
	        x += lowbit(x);
	    }
	}
	int query (int x) {
	    int ans = 0;
	    while (x > 0) {
	        ans += c[x];
	        x -= lowbit(x);
	    }
		return ans;
	}
	void clear (int x) {
	    while (x <= n) {
	        c[x] = 0;
	        x += lowbit(x);
	    }		
	}
}
struct node {
	int x, y, id, type, val;
	friend bool operator <(node x, node y) {
		return x.x == y.x ? x.y == y.y ? x.type < y.type : x.y < y.y : x.x < y.x;
	}
} a[MAXN], tmp[MAXN];

int n, newp, newq;
int ans[MAXN];

void cdq(int l, int r) {
	if (l == r) {
		return;
	}
	
	int mid = (l + r) >> 1;
	cdq(l, mid);
	cdq(mid + 1, r);
	int i = l, j = mid + 1, p = l;
	
	while (i <= mid && j <= r) {
		if (a[i].x <= a[j].x) {
			if(a[i].type == 1)sz::add(a[i].y, a[i].val);	
			tmp[p++] = a[i++];
		}
		else {
			if (a[j].type == 2)ans[a[j].id] += sz::query(a[j].y);
			tmp[p++] = a[j++];
		}
	}
	while (i <= mid) {
		tmp[p++] = a[i++];
	}
	while (j <= r) {
		if (a[j].type == 2) {
			ans[a[j].id] += sz::query(a[j].y);
		}
		tmp[p++] = a[j++];
	}
	for (int k = l; k <= mid; ++k) {
		if (a[k].type == 1) sz::clear(a[k].y);
	}
	for (int i = l; i <= r; ++i) {
		a[i] = tmp[i];
	}
}

void read (int &x) {
	x = 0;
	int k = 1;
	int t = getchar();
	while (t > '9' || t < '0') {
		if (t == '-') k = -1;
		t = getchar();
	}
	while (t >= '0' && t <= '9') {
		x *= 10;
		x += (t - '0');
		t = getchar();
	}
	x *= k;
}

int main (void) {
	read(n);read(n);
	++n;
	sz::n = n;
	int opt;
	read(opt);
	while (opt != 3) {
		if (opt == 1) {
			++newp;
			read(a[newp].x);read(a[newp].y);read(a[newp].val);
			++a[newp].x;++a[newp].y;
			a[newp].type = 1;
		}
		else {
			int x1, x2, y1, y2;
			read(x1);read(y1);read(x2);read(y2);
			++x1;++x2;++y1;++y2;
			a[++newp].x = x2;a[newp].y = y2;a[newp].type = 2;a[newp].id = ++newq;
			a[++newp].x = x1 -1;a[newp].y = y2;a[newp].type = 2;a[newp].id = ++newq;
			a[++newp].x = x2;a[newp].y = y1 - 1;a[newp].type = 2;a[newp].id = ++newq;
			a[++newp].x = x1 - 1;a[newp].y = y1 - 1;a[newp].type = 2;a[newp].id = ++newq;
		}
		read(opt);
	}
	//std::sort(a + 1, a + 1 + newp, cmp1);
	cdq(1, newp);
	for (int i = 1; i <= newq; i += 4) {
		printf("%d\n", ans[i] - ans[i + 1] - ans[i + 2] + ans[i + 3]);
	}
	return 0;
}
Loading...
Ownership of this post data is guaranteed by blockchain and smart contracts to the creator alone.