自动搬运

查看原文

来自洛谷，原作者为

	Ireliaღ 逝去的是刀锋，不变的是意志

搬运于2025-08-24 22:21:30，当前版本为作者最后更新于2020-05-04 19:19:03，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

比赛中思考过程最短的一道题。

考虑转化一下题意，每次修改相当于添加一条从$l$到$r$的线段，每次查询就是询问贯穿区间$[l, r]$的线段个数。

把每条线段的左端点当做第一维，右端点当做第二维，那么这条线段可以对应坐标系中的一个点，查询就可以看做询问$x \in [1, l]$且$y \in [r, n]$的矩形上的点数，剩下的就是一个kd-tree的模板了。

代码如下

#include <algorithm>
#include <iostream>
#include <cstdio>

using namespace std;
const int MAXN = 1e5 + 5;
const double A = 0.7;

struct Data{
	int x[2];
	
	Data(int a, int b) {
		x[0] = a;
		x[1] = b;
	}
	
	Data() {}
};

int operator == (const Data &a, const Data &b) {
	return a.x[0] == b.x[0] && a.x[1] == b.x[1];
}

struct Node{
	Data pos;
	Node *ch[2];
	int cnt, sum, cov;
	int mn[2], mx[2];
	
	Node(Data pos, int cnt) : pos(pos), cnt(cnt) {
		cov = 1;
		sum = cnt;
		for (int i = 0; i < 2; i++) mn[i] = mx[i] = pos.x[i];
		ch[0] = ch[1] = NULL;
	}
	
	Node() {}
}npool[MAXN];

int Comp0(Node *a, Node *b) {
	if (a->pos.x[0] != b->pos.x[0]) return a->pos.x[0] < b->pos.x[0];
	else return a->pos.x[1] < b->pos.x[1];
}

int Comp1(Node *a, Node *b) {
	if (a->pos.x[1] != b->pos.x[1]) return a->pos.x[1] < b->pos.x[1];
	else return a->pos.x[0] < b->pos.x[0];
}

int n, m;
int ncnt;
Node *rt;
Node *tree[MAXN];
int tcnt;

Node *New(Data pos, int cnt) {
	npool[ncnt] = Node(pos, cnt);
	return &npool[ncnt++];
}

void Update(Node *now) {
	now->cov = 1 + (now->ch[0] ? now->ch[0]->cov : 0) + (now->ch[1] ? now->ch[1]->cov : 0);
	now->sum = now->cnt + (now->ch[0] ? now->ch[0]->sum : 0) + (now->ch[1] ? now->ch[1]->sum : 0);
	for (int i = 0; i < 2; i++) now->mn[i] = now->mx[i] = now->pos.x[i];
	for (int i = 0; i < 2; i++) {
		if (now->ch[i]) {
			for (int j = 0; j < 2; j++) {
				now->mn[j] = min(now->mn[j], now->ch[i]->mn[j]);
				now->mx[j] = max(now->mx[j], now->ch[i]->mx[j]);
			}
		}
	}
}

int Bad(Node *now) {
	int ls = now->ch[0] ? now->ch[0]->cov : 0;
	int rs = now->ch[1] ? now->ch[1]->cov : 0;
	return 1.0 * ls > A * now->cov || 1.0 * rs > A * now->cov;
}

void DFS(Node *now) {
	if (!now) return;
	DFS(now->ch[0]);
	DFS(now->ch[1]);
	tree[++tcnt] = now;
	now->ch[0] = now->ch[1] = NULL;
	Update(now);
}

void Rebuild(Node *&now, int l, int r, int d) {
	if (l > r) return;
	int mid = l + r >> 1;
	if (d) nth_element(tree + l, tree + mid, tree + r + 1, Comp1);
	else nth_element(tree + l, tree + mid, tree + r + 1, Comp0); 
	now = tree[mid];
	Rebuild(now->ch[0], l, mid - 1, (d + 1) % 2);
	Rebuild(now->ch[1], mid + 1, r, (d + 1) % 2);
	Update(now);
}

void Maintain(Node *&now, int d) {
	if (Bad(now)) {
		tcnt = 0;
		DFS(now);
		Rebuild(now, 1, tcnt, d);
	}
}

void Insert(Node *&now, Data pos, int cnt, int d) {
	if (!now) {
		now = New(pos, cnt);
		return;
	}
	if (pos == now->pos) {
		now->cnt += cnt;
		Update(now);
		return;
	}
	if (pos.x[d] < now->pos.x[d]) Insert(now->ch[0], pos, cnt, (d + 1) % 2);
	else Insert(now->ch[1], pos, cnt, (d + 1) % 2);
	Update(now);
	Maintain(now, d);
}

int Inside(Node *now, int mn[], int mx[]) {
	for (int i = 0; i < 2; i++) {
		if (now->pos.x[i] < mn[i] || now->pos.x[i] > mx[i]) return 0;
	}
	return 1;
}

int AllIn(Node *now, int mn[], int mx[]) {
	for (int i = 0; i < 2; i++) {
		if (now->mn[i] < mn[i] || now->mx[i] > mx[i]) return 0;
	}
	return 1;
}

int AllOut(Node *now, int mn[], int mx[]) {
	for (int i = 0; i < 2; i++) {
		if (now->mn[i] > mx[i] || now->mx[i] < mn[i]) return 1;
	}
	return 0;
}

int Query(Node *now, int mn[], int mx[]) {
	if (!now) return 0;
	if (AllIn(now, mn, mx)) return now->sum;
	if (AllOut(now, mn, mx)) return 0;
	return (Inside(now, mn, mx) ? now->cnt : 0) + Query(now->ch[0], mn, mx) + Query(now->ch[1], mn, mx);
}

int main() {
	ios::sync_with_stdio(false); cin.tie(NULL);
	int op, x, y;
	int mn[2], mx[2];
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		cin >> op >> x >> y;
		if (op == 1) {
			Insert(rt, Data(x, y), 1, 0);
		} else {
			mn[0] = 1; mx[0] = x;
			mn[1] = y; mx[1] = n;
			cout << Query(rt, mn, mx) << '\n';
		}
	}
	return 0;
}