[牛客]Magnificent Tree （CDQ分治）

原题

思路

cdq分治，三维偏序问题(x, y, id)。第一维用sort排，第二维归并排序同时根据第三维树状数组统计贡献，手动交换会T，先sort再统计贡献，node数组要开4倍。

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <list>
#include <map>
#include <iostream>
#include <iomanip>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>
#define LL long long
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f
#define PI 3.1415926535898
#define F first
#define S second
#define endl '
'
#define lson  rt << 1
#define rson  rt << 1 | 1
#define lowbit(x) (x &(-x))
#define f(x, y, z) for (int x = (y), __ = (z); x < __; ++x)
#define _rep(i, a, b) for (int i = (a); i <= (b); ++i)
using namespace std;
const int maxn = 2e5 + 7;
const int mod = 1e9 + 7;
int n, m, tot;

int c[maxn], ans[maxn];

LL read()
{
	LL x = 0, f = 1;char ch = getchar();
	while (ch < '0' || ch>'9') { if (ch == '-')f = -1;ch = getchar(); }
	while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0';ch = getchar(); }
	return x * f;
}

struct node
{
	int x, y, h, kind, id, sg;
}s[maxn * 4];

bool cmp1(node a, node b)
{
	if(a.x != b.x) return a.x < b.x;
	if (a.y != b.y) return a.y < b.y;
	return a.id < b.id;
}

bool cmp2(node a, node b)
{
	if(a.y != b.y) return a.y < b.y;
	return a.id < b.id;
}

void update(int x, int y)
{
	for (; x <= tot; x += lowbit(x)) c[x] += y;
}
int sum(int x)
{
	int ans = 0;
	for (; x; x -= lowbit(x)) ans += c[x];
	return ans;
}

void cdq(int l, int r)
{
	if (l == r) return;
	int mid = (l + r) >> 1;
	cdq(l, mid);
	cdq(mid + 1, r);
	sort(s + l, s + mid + 1, cmp2);
	sort(s + mid + 1, s + r + 1, cmp2);
	int i = l, j = mid + 1, tot = l;
	for(; j <= r; j++)
	{
		while (i <= mid && s[i].y <= s[j].y)
		{
			if (s[i].kind == 1) update(s[i].id, s[i].h);
			i++;
		}
		if(s[j].kind == 2)ans[s[j].id] += s[j].sg * sum(s[j].id);
	}
	f(j, l, i)
	{
		if(s[j].kind == 1)update(s[j].id, -s[j].h);
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	n = read(), m = read();
	int op, x1, y1, x2, y2, h;
	vector<int> q;
	_rep(i, 1, n)
	{
		op = read();
		if (op == 1)
		{
			x1 = read(), y1 = read(), h = read();
			s[++tot] = { x1, y1, h, 1, i, 0 };
		}
		else
		{
			q.push_back(i);
			x1 = read(), y1 = read(), x2 = read(), y2 = read();
			s[++tot] = { x1 - 1, y1 - 1, 0, 2, i, 1 };
			s[++tot] = { x1 - 1, y2, 0, 2, i, -1 };
			s[++tot] = { x2, y2, 0, 2, i, 1 };
			s[++tot] = { x2, y1 - 1, 0, 2, i, -1};
		}
	}
	sort(s + 1, s + tot + 1, cmp1);
	cdq(1, tot);
	f(i, 0, q.size())
	{
		cout << ans[q[i]] << endl;
	}
}