BuringStraw

BuringStraw

CDQ Divide and Conquer Summary

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.