题解--超越维度

· · 题解

吐槽自己，出这么偏的题。
但部分分还是给足了的。
但为什么比赛时没几个人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;
}