自动搬运

查看原文

来自洛谷，原作者为

	abruce I won't feel lonely, nor will I be sorrowful... not before everything is buried.

搬运于2025-08-24 22:26:39，当前版本为作者最后更新于2020-06-24 16:55:09，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

吐槽自己，出这么偏的题。
但部分分还是给足了的。
但为什么比赛时没几个人A啊？

10pts

乱搞就可以了，入门难度。

30pts

建一个二维线段树，区块赋值，区块查询，然后就相当于模板了。

60pts

建一个三维线段树，其他和30pts做法一样。

100pts

介绍一下这个题所用的冷门算法：矩形切割。
矩形切割，就是将它有相交部分的矩形分割成若干个小矩形，从而消除重叠的部分，方便计算面积。当然，其它维度也是一样的。由于每次插入和查询时都要遍历一遍已经存在的所有矩形，所有时间复杂度是 $\text{O}(n^2k\sim n^3k)$ 的。常数与维度和矩形密集程度有关，且较大。
为了方便，就以二维的情况为进行一次模拟操作，其它维度也是一个道理。
假设这里有一个矩形 A 和一个矩形 B，它们是相交的（不相交的情况直接忽略）

所谓的矩形切割，就是删除原来的 A，替换成全新的 A1 和 A2，这样，每一个矩形之间就没有相交的部分，所以计算面积就可以直接把所有的矩形的面积加起来，就可以得到答案。

接下来就可以看代码了。

#include <bits/stdc++.h>
using namespace std;
namespace io {
	inline long long read() {
		long long __x=0,__f=1;
		char __c=getchar();
		while(__c<'0'||__c>'9') {
			if(__c=='-')__f=-1;
			__c=getchar();
		}
		while(__c>='0'&&__c<='9') {
			__x=__x*10+__c-'0';
			__c=getchar();
		}
		return __x*__f;
	}
	char __F[200];
	inline void write(long long __x) {
		if(__x==0) {
			putchar('0');
			return;
		}
		long long __tmp,__cnt=0;
		if(__x>0) {
			__tmp=__x;
		} else {
			__tmp=-__x;
		}
		if(__x<0) {
			putchar('-');
		}
		while(__tmp>0) {
			__F[__cnt++]=__tmp%10+'0';
			__tmp/=10;
		}
		while(__cnt>0) {
			putchar(__F[--__cnt]);
		}
	}
}
using namespace io;//快速读入，可忽略。
struct square {
	long long x[10],y[10];//x=左上每个维度坐标，y=右下每个维度坐标
} s[1000005];
long long n,k,cnt;
long long ans,mod=1919810;
bool pd(square a,square b) {
	for(register long long i=1; i<=k; i++) {
		if(a.x[i]>=b.y[i]||a.y[i]<=b.x[i]) {
			return 0;//只要有一个维度上它们最多在边界擦过，那它们就不相交了，直接忽略。
		}
	}
	return 1;
}
void add(square q) {
	cnt++;
	for(register long long i=1; i<=k; i++) {
		s[cnt].x[i]=q.x[i];
		s[cnt].y[i]=q.y[i];
	}//加入一个新k维体。
}
void del(int now) {
	s[now]=s[cnt--];//把最后一个替换成当前这一个，再删除最后一个，相当于删除了now上的k维体。
}
void cut(square a,square b,int i) {
	if(i==k+1)return;
	long long k1,k2;
	square q;
	k1=max(a.x[i],b.x[i]);
	k2=min(a.y[i],b.y[i]);
	if(k1>a.x[i]) {
		q=a;
		q.y[i]=k1;
		add(q);//这个维度相交的话，加一个新的。
	}
	if(k2<a.y[i]) {
		q=a;
		q.x[i]=k2;
		add(q);//同理。
	}
        a.x[i]=k1;
	a.y[i]=k2;//记录切到哪里了。
	cut(a,b,i+1);//往下一个维度走。
}
long long sum(long long j,square q) {
	long long m=1;
	for(register long long i=1; i<=k; i++) {
		m=m*(min(s[j].y[i],q.y[i])-max(s[j].x[i],q.x[i]));//计算k维体积。
		m%=mod;
	}
	return m;
}
int main() {
	long long a[10],w,x;
	square q;
	n=read(),k=read();
	for(register long long i=1; i<=n; i++) {
		x=read();
		for(register long long j=1; j<=k; j++) {
			a[j]=read();
		}
		w=read();
		for(register long long j=1; j<=k; j++) {
			q.x[j]=a[j]-w;
			q.y[j]=a[j]+w;
		}
		if(x==1) {
			for(register long long j=1; j<=cnt; j++) {
				if(pd(q,s[j])) {
					cut(s[j],q,1);
					del(j);
					j--;//切完之后再删除。
				}
			}
			add(q);
		} else {
			ans=0;
			for(register long long j=1; j<=cnt; j++) {
				if(pd(q,s[j])) {
					ans+=sum(j,q);//与它相交的话才加相交部分
					ans%=mod;
				}
			}
			write(ans);
			putchar('\n');
		}
	}
	return 0;
}